Co dělá nonogram snadným nebo těžkým

Větší mřížka skutečně znamená více řádků k sledování a více křížových kontrol, takže velké hlavolamy zaberou déle. Ale samotná délka řádek neztíží — řádek široký 20 s jedinou velkou souvislou řadou je triviální, zatímco krátký řádek nabitý malými řadami a těsnými mezerami může vyžadovat skutečné přemýšlení. Velikost ovlivňuje mnohem víc to, jak dlouho hlavolam trvá, než to, jak těžký je každý krok.

Nejvěrnějším měřítkem obtížnosti je, jaký druh uvažování hlavolam vyžaduje. Nejsnadnější hlavolamy jsou „řešitelné po řádcích“: můžete je dokončit tím, že se díváte vždy na jeden řádek nebo sloupec, vyplňujete, co tato jediná linie vynucuje, a nikdy nemusíte držet v hlavě dvě linie najednou. Většina mírných hlavolamů je přesně taková.

Těžší hlavolamy vyžadují kombinovat informace — všimnout si, že stav políčka se stane vynuceným, teprve když zvážíte řádek a sloupec dohromady nebo malou skupinu linií najednou. Čím hlouběji musí tato kombinace sahat, než se další políčko stane vynuceným, tím těžší se hlavolam zdá, bez ohledu na jeho velikost.

Tady přichází uklidňující část. Akademická práce o řešení nonogramů (Batenburg and Kosters, 2012) změřila, kolik uvažování jednoznačně řešitelné hlavolamy skutečně vyžadují. Kromě prostého řešení řádek po řádku je dalším krokem dobře definovaná, stále deterministická technika — kombinování dvojic linií — a jejich vyčerpávající výčet zjistil, že 93.8–95.5% netriviálních hlavolamů je řešitelných právě tím, zcela bez hádání.

Ještě pozoruhodnější: jen asi 0.06–0.14% všech jednoznačně řešitelných hlavolamů potřebuje cokoli nad rámec tohoto uvažování o dvojicích linií. Jinými slovy, drtivá většina dobře utvořených nonogramů — včetně každého těžkého, na který v běžné hře narazíte — se dá vyřešit čistou, ohraničenou logikou. Skutečné metody pokusu a omylu jsou v poctivém hlavolamu mizivě vzácné, a proto je „nikdy nehádej“ tak spolehlivá rada.

Pod tím vším leží teoretický výsledek. Rozhodnutí, zda libovolná sada nápověd řádků a sloupců má vůbec nějaké řešení, bylo dokázáno jako NP-úplné (Ueda and Nagao, 1996) — stejná třída složitosti jako nechvalně známé tvrdošíjné problémy jako problém obchodního cestujícího. Prostě řečeno: nikdo nezná metodu, která rychle vyřeší každý myslitelný nonogram, a v nejhorších případech potřebná práce exploduje s růstem mřížky.

Zní to znepokojivě, dokud si nevšimnete rozdílu mezi „každým myslitelným nonogramem“ a „nonogramy, které lidé skutečně publikují“. Výsledek o NP-úplnosti se týká libovolných, nepřátelsky volených sad nápověd — z nichž mnohé nemají řešení vůbec, nebo mají několik. Skutečný hlavolam se tvoří obráceně: začíná obrázkem a publikuje se jen tehdy, má-li přesně jedno řešení, k němuž logika skutečně dokáže dojít. Proto čísla z předchozí sekce platí v praxi — a proto je hlavolam před vámi téměř jistě poctivý, i když se zdá brutální.

Kromě hloubky dedukce posouvá obtížnost několik povrchových rysů. Velmi řídké obrázky (převážně prázdné) a velmi husté (převážně zaplněné) bývají snazší, protože extrémy poskytnou brzy mnoho vynucených políček. Nejzáludnější hlavolamy obvykle leží uprostřed, s vyváženou směsí zaplněného a prázdného a spoustou krátkých, roztříštěných řad, které odolávají rychlým zahajovacím tahům. Čistý, rozpoznatelný motiv také pomáhá řešiteli udržet orientaci, i když nemění základní logiku.

Na tomto webu vychází hodnocení hlavolamu z toho, jak hluboko sahá uvažování potřebné k jeho vyřešení, v kombinaci se statistikami tvaru, jako je zaplněnost mřížky. Hlavolamy řešitelné po řádcích spadají do snadných; ty, které vyžadují skutečnou mezilinajovou kombinaci, se posouvají k těžkým; cokoli, co by vyžadovalo hádání, se rovnou odmítne místo publikace. Celý postup je popsán na stránce „jak vytváříme naše nonogramy“ — ale krátká verze zní, že obtížnost se zde měří, nehádá.