Co sprawia, że nonogram jest łatwy lub trudny

Większa siatka rzeczywiście oznacza więcej linii do śledzenia i więcej porównań krzyżowych, więc duże łamigłówki zajmują więcej czasu. Ale sama długość nie czyni linii trudną — wiersz o szerokości 20 pól z jednym dużym ciągiem jest trywialny, podczas gdy krótki wiersz wypełniony małymi ciągami i ciasnymi przerwami może wymagać prawdziwego namysłu. Rozmiar wpływa na to, ile czasu zajmuje łamigłówka, znacznie bardziej niż na to, jak trudny jest każdy krok.

Najprawdziwszą miarą trudności jest to, jakiego rodzaju rozumowania wymaga łamigłówka. Najłatwiejsze łamigłówki są „rozwiązywalne liniowo”: możesz je ukończyć, patrząc na jeden wiersz lub kolumnę naraz, wypełniając to, co wymusza dana linia, i nigdy nie musząc trzymać dwóch linii w głowie jednocześnie. Większość łagodnych łamigłówek jest właśnie taka.

Trudniejsze łamigłówki wymagają łączenia informacji — zauważenia, że stan pola staje się wymuszony dopiero wtedy, gdy rozważysz wiersz i kolumnę razem albo mały zbiór linii naraz. Im głębiej musi sięgać to łączenie, zanim następne pole zostanie wymuszone, tym trudniejsza wydaje się łamigłówka, niezależnie od jej rozmiaru.

Oto uspokajająca część. Praca naukowa o rozwiązywaniu nonogramów (Batenburg and Kosters, 2012) zmierzyła, ile rozumowania faktycznie wymagają jednoznacznie rozwiązywalne łamigłówki. Poza prostym rozwiązywaniem linia po linii, kolejny krok to dobrze zdefiniowana, wciąż deterministyczna technika — łączenie par linii — a ich wyczerpujące wyliczenie wykazało, że 93.8–95.5% niebanalnych łamigłówek jest rozwiązywalnych dokładnie tą metodą, bez żadnego zgadywania.

Jeszcze bardziej uderzające: tylko około 0.06–0.14% wszystkich jednoznacznie rozwiązywalnych łamigłówek potrzebuje czegokolwiek poza tym rozumowaniem par linii. Innymi słowy, przytłaczająca większość poprawnie skonstruowanych nonogramów — w tym każdy trudny, jaki spotkasz w normalnej grze — daje się rozwiązać czystą, ograniczoną logiką. Prawdziwa metoda prób i błędów jest znikomo rzadka w uczciwej łamigłówce, dlatego „nigdy nie zgaduj” to tak niezawodna rada.

Pod tym wszystkim kryje się wynik teoretyczny. Rozstrzygnięcie, czy dowolny zestaw podpowiedzi wierszy i kolumn ma w ogóle jakiekolwiek rozwiązanie, zostało udowodnione jako NP-zupełne (Ueda and Nagao, 1996) — ta sama klasa złożoności co słynny problem komiwojażera. Mówiąc prosto: nikt nie zna metody, która szybko rozwiąże każdy wyobrażalny nonogram, a w najgorszych przypadkach nakład obliczeń rośnie lawinowo wraz z rozmiarem siatki.

Brzmi to niepokojąco, dopóki nie zauważysz różnicy między „każdym wyobrażalnym nonogramem” a „nonogramami, które faktycznie się publikuje”. Wynik o NP-zupełności dotyczy dowolnych, wrogo dobranych zestawów podpowiedzi — z których wiele nie ma rozwiązania wcale albo ma ich kilka. Prawdziwą łamigłówkę tworzy się odwrotnie: zaczyna się od obrazka i trafia ona do publikacji tylko wtedy, gdy ma dokładnie jedno rozwiązanie, do którego logika naprawdę potrafi dojść. Dlatego liczby z poprzedniej sekcji sprawdzają się w praktyce — i dlatego łamigłówka przed Tobą jest niemal na pewno uczciwa, nawet gdy wydaje się brutalna.

Poza głębią wnioskowania kilka cech powierzchownych przesuwa trudność. Bardzo rzadkie obrazki (w większości puste) i bardzo gęste (w większości wypełnione) bywają łatwiejsze, bo skrajności dają wiele wymuszonych pól już na początku. Najtrudniejsze łamigłówki zwykle leżą pośrodku, z wyważoną mieszanką wypełnionych i pustych pól oraz mnóstwem krótkich, porozrywanych ciągów, które opierają się szybkim ruchom otwarcia. Czytelny, rozpoznawalny motyw również pomaga rozwiązującemu zachować orientację, nawet jeśli nie zmienia leżącej u podstaw logiki.

Na tej stronie ocena łamigłówki wynika z tego, jak głębokie jest rozumowanie potrzebne do jej rozwiązania, w połączeniu ze statystykami kształtu, takimi jak stopień wypełnienia siatki. Łamigłówki rozwiązywalne liniowo trafiają do łatwych; te wymagające prawdziwego łączenia między liniami przesuwają się ku trudnym; wszystko, co wymagałoby zgadywania, jest odrzucane od razu, a nie publikowane. Pełny proces opisano na stronie „jak tworzymy nasze nonogramy” — ale w skrócie: trudność jest tu mierzona, a nie zgadywana.