Il problema generale dei Nonogrammi è computazionalmente difficile: risultati formali mostrano la NP-completezza per formulazioni decisionali standard, mentre lavori successivi descrivono comunemente la risoluzione generale dei Nonogrammi come NP-hard.
Questo non significa che ogni Nonogramma sia difficile, che i computer non possano risolverli o che un puzzle 10×10 richieda in pratica tempo esponenziale. La teoria della complessità descrive il comportamento delle istanze più difficili mentre la dimensione dei puzzle cresce.
Quale problema sta analizzando la teoria della complessità?
Un risultato di complessità richiede una domanda computazionale precisa.
Una versione decisionale semplificata è:
Dati gli indizi di riga e colonna di un Nonogramma, esiste almeno una griglia piena/vuota che li soddisfa tutti?
Una griglia completa proposta può essere verificata in modo efficiente: basta scansionare ogni riga e colonna e confrontare le lunghezze dei blocchi con gli indizi.
La parte difficile è trovare una soluzione o decidere se esiste, considerando tutti i possibili insiemi di indizi.
Cosa significa NP-completo in questo contesto?
In modo informale, un problema decisionale è NP-completo quando:
- una soluzione proposta può essere verificata efficientemente;
- il problema è almeno difficile quanto ogni problema della classe di complessità NP attraverso riduzioni in tempo polinomiale.
Il rapporto tecnico di Ueda e Nagao del 1996 ha stabilito risultati di NP-completezza per i Nonogrammi usando riduzioni parsimoniose. La ricerca successiva sui Nonogrammi cita questo risultato quando discute la difficoltà del problema generale.
Non serve conoscere la teoria della complessità per giocare. Il risultato è importante perché spiega perché non possiamo aspettarci che una semplice raccolta di trucchi locali risolva efficientemente ogni possibile istanza.
NP-completo non significa «sempre difficile»
È l'equivoco più importante da evitare.
Sudoku, SAT e molti altri problemi NP-completi possiedono famiglie enormi di istanze facili. I Nonogrammi sono uguali.
Gli editori progettano deliberatamente puzzle con struttura utile:
- indizi informativi;
- sovrapposizioni forti;
- propagazione produttiva tra righe e colonne;
- colli di bottiglia controllati;
- spesso un percorso logico adatto agli esseri umani.
Batenburg e Kosters mettono esplicitamente a confronto i normali Nonogrammi da libro, spesso risolvibili mediante ragionamento locale ripetuto sulle linee, con il problema generale difficile.
Perché lo spazio di ricerca può diventare enorme?
Ogni linea può ammettere più disposizioni legali. Sull'intera griglia, queste scelte interagiscono attraverso le caselle condivise.
Una decisione che sembra legale in una riga può restringere diverse colonne; quelle colonne restringono altre righe; e una contraddizione può apparire solo dopo una lunga catena.
Nel caso peggiore, un solver può dover distinguere tra molte combinazioni di pattern di linea o ramificare tra alternative.
Il solo numero delle possibili griglie binarie complete è enorme: una griglia r × c ha 2^(r·c) assegnazioni grezze piena/vuota prima che gli indizi ne eliminino la maggior parte.
I buoni solver non enumerano tutte queste assegnazioni alla cieca, ma la cifra mostra perché vincoli e pruning sono importanti.
Perché la logica di linea risolve così tanti puzzle reali
I Nonogrammi progettati manualmente non sono istanze casuali del caso peggiore.
I creatori vogliono spesso un puzzle che riveli un'immagine riconoscibile e possa essere risolto con deduzioni soddisfacenti. Questa pressione di design seleziona strutture che il normale ragionamento di linea riesce a sfruttare.
Un solver può ripetere:
- risolvere righe vincolate;
- trasferire le caselle forzate alle colonne;
- risolvere le colonne modificate;
- propagare ancora.
Per molti puzzle pubblicati è sufficiente.
La teoria della complessità dice soltanto che alcuni input validi sfuggono a ogni strategia universalmente efficiente, assumendo la congettura standard P ≠ NP.
Cosa significa NP-hard rispetto a NP-completo?
Nella letteratura sui Nonogrammi puoi incontrare entrambi i termini.
- NP-hard significa che un problema è almeno difficile quanto i problemi più difficili di NP.
- NP-completo aggiunge che il problema decisionale stesso appartiene a NP.
Per il normale problema decisionale di esistenza, nel risultato citato è appropriata la descrizione più forte NP-completo. I lavori che parlano della risoluzione in senso più ampio usano spesso NP-hard come formulazione ombrello più prudente.
L'unicità rende il problema più facile?
Non automaticamente.
Un puzzle garantito come avente una sola soluzione può comunque essere difficile da risolvere. Stabilire se esista un'altra soluzione è a sua volta strettamente collegato ai difficili problemi di «altra soluzione» studiati nella teoria della complessità.
Per l'editoriale, la conclusione pratica è più semplice:
unico, risolvibile da un essere umano e facile sono tre affermazioni diverse.
Perché i solver informatici funzionano comunque bene
La difficoltà nel caso peggiore non impedisce l'esistenza di algoritmi pratici molto forti.
I solver sfruttano:
- propagazione dei vincoli a livello di linea;
- programmazione dinamica o filtraggio dei pattern;
- pianificazione intelligente delle linee modificate;
- caching;
- controlli di contraddizione;
- euristiche di ramificazione;
- probing;
- tecnologie generali di constraint solving.
Le raccolte di puzzle reali contengono inoltre molta più struttura delle istanze teoriche avversarie.
Di conseguenza, un solver può gestire rapidamente molti grandi puzzle progettati da esseri umani anche se non esiste una garanzia polinomiale per il caso generale.
Perché è importante per il design dei puzzle
I risultati di complessità non sono solo curiosità astratte.
Spiegano perché un generatore deve validare i puzzle invece di presumere che ogni insieme di indizi si comporti bene. Un candidato può essere:
- incoerente;
- ambiguo;
- unico ma pesante in termini di ricerca;
- unico e risolvibile in modo fluido.
I sistemi di costruzione combinano quindi generazione, controlli tramite solver e stime di difficoltà.
Idee sbagliate comuni
«NP-completo significa che nessuno può risolvere i Nonogrammi in modo efficiente»
No. Significa che non conosciamo un algoritmo in tempo polinomiale per tutte le istanze e che un tale algoritmo avrebbe conseguenze importanti per la teoria della complessità.
«Una griglia più grande è esponenzialmente difficile per definizione»
No. La dimensione amplia lo spazio di ricerca possibile, ma la specifica struttura degli indizi può rendere facile anche una grande istanza.
«Se un puzzle è risolvibile senza indovinare, i Nonogrammi non possono essere NP-hard»
Sottoclassi facili possono esistere dentro un problema generale difficile. I puzzle pubblicati vengono spesso scelti intenzionalmente proprio da queste regioni più amichevoli.
«NP significa non-polynomial»
No. NP è il nome di una classe di complessità; viene comunemente caratterizzata da soluzioni verificabili in tempo polinomiale.
Cosa imparare dopo
Per gli algoritmi che rendono pratica la risoluzione, leggi Come Funzionano i Solver Informatici di Nonogrammi. Per i mattoni combinatori dietro le possibilità di linea, leggi Nonogrammi e Matematica.
FAQ
I Nonogrammi sono NP-completi?
La forma decisionale standard del problema generale ha risultati di NP-completezza nella letteratura. Quando si parla più in generale di risoluzione viene anche spesso riassunta come NP-hard.
Questo dimostra che ogni puzzle richiede di indovinare?
No. Molti Nonogrammi pubblicati sono progettati deliberatamente per essere risolti tramite deduzioni logiche locali e propagazione.
Un computer può comunque risolvere Nonogrammi difficili?
Sì. La NP-completezza non impedisce di risolvere efficacemente singole istanze; esclude una garanzia efficiente nota per tutte le istanze sotto le assunzioni standard della teoria della complessità.