Cosa rende un nonogramma facile o difficile

Una griglia più grande significa davvero più linee da tenere d'occhio e più controlli incrociati, quindi i rompicapi grandi richiedono più tempo. Ma la lunghezza da sola non rende difficile una linea — una riga larga 20 con una singola sequenza grande è banale, mentre una riga corta piena di piccole sequenze e spazi stretti può richiedere vera riflessione. La dimensione influisce molto più su quanto tempo richiede un rompicapo che su quanto è difficile ogni passo.

La misura più fedele della difficoltà è che tipo di ragionamento richiede il rompicapo. I più facili sono "risolvibili per linea": puoi finirli guardando una riga o una colonna alla volta, riempiendo ciò che quella singola linea forza, senza mai dover tenere due linee in testa contemporaneamente. La maggior parte dei rompicapi leggeri è esattamente così.

Quelli più difficili richiedono di combinare le informazioni — notare che lo stato di una casella diventa forzato solo quando consideri una riga e una colonna insieme, o un piccolo gruppo di linee alla volta. Più in profondità deve andare quella combinazione prima che la casella successiva sia forzata, più difficile appare il rompicapo, indipendentemente dalla sua dimensione.

Ecco la parte rassicurante. Il lavoro accademico sulla risoluzione dei nonogrammi (Batenburg and Kosters, 2012) ha misurato quanto ragionamento richiedano davvero i rompicapi a soluzione unica. Oltre alla semplice risoluzione linea per linea, il passo successivo è una tecnica ben definita e ancora deterministica — combinare coppie di linee — e la loro enumerazione esaustiva ha rilevato che il 93.8–95.5% dei rompicapi non semplici è risolvibile esattamente con quella, senza alcun tentativo alla cieca.

Ancora più sorprendente: solo circa lo 0.06–0.14% di tutti i rompicapi a soluzione unica ha bisogno di qualcosa oltre quel ragionamento sulle coppie di linee. In altre parole, la stragrande maggioranza dei nonogrammi ben formati — inclusi tutti quelli difficili che incontrerai nel gioco normale — può essere risolta con logica pura e limitata. Il vero tentativo ed errore è estremamente raro in un rompicapo corretto, ed è per questo che "non tirare mai a indovinare" è un consiglio così affidabile.

Sotto tutto questo c'è un risultato teorico. Decidere se un insieme arbitrario di indizi di righe e colonne abbia una qualsiasi soluzione è stato dimostrato NP-completo (Ueda and Nagao, 1996) — la stessa classe di complessità di problemi notoriamente ostinati come quello del commesso viaggiatore. In parole povere: nessuno conosce un metodo che risolva rapidamente ogni nonogramma concepibile, e nei casi peggiori il lavoro necessario esplode al crescere della griglia.

Sembra allarmante finché non noti la differenza tra "ogni nonogramma concepibile" e "i nonogrammi che le persone pubblicano davvero". Il risultato di NP-completezza riguarda insiemi di indizi arbitrari e ostili — molti dei quali non hanno soluzione, o ne hanno diverse. Un rompicapo reale è costruito al contrario: parte da un'immagine, e viene pubblicato solo se ha esattamente una soluzione che la logica può davvero raggiungere. Ecco perché i numeri della sezione precedente reggono nella pratica, ed ecco perché il rompicapo davanti a te è quasi certamente corretto, anche quando sembra brutale.

Oltre alla profondità della deduzione, un paio di caratteristiche superficiali spostano la difficoltà. Le immagini molto rade (per lo più vuote) e quelle molto dense (per lo più piene) tendono a essere più facili, perché gli estremi offrono molte caselle forzate fin da subito. I rompicapi più insidiosi di solito stanno nel mezzo, con un mix equilibrato di pieno e vuoto e tante sequenze corte e spezzate che resistono alle rapide mosse di apertura. Un soggetto pulito e riconoscibile aiuta inoltre il solutore a restare orientato, anche se non cambia la logica sottostante.

Su questo sito, la valutazione di un rompicapo deriva da quanto in profondità va il ragionamento per risolverlo, combinato con statistiche di forma come quanto è piena la griglia. I rompicapi risolvibili per linea finiscono in facile; quelli che richiedono una vera combinazione tra linee si spostano verso difficile; tutto ciò che richiederebbe di tirare a indovinare viene respinto senza appello anziché pubblicato. L'intero processo è descritto nella pagina "come creiamo i nostri nonogrammi" — ma la versione breve è che qui la difficoltà si misura, non si indovina.