Un solver informatico di Nonogrammi alterna normalmente due lavori: risolvere singole linee sotto i vincoli correnti e propagare ogni nuova casella forzata nelle linee che la incrociano. Se questo processo raggiunge un punto fisso prima che la griglia sia completa, solver più forti possono fare probing su ipotesi o ramificare tra le possibilità rimaste.
I diversi programmi implementano i dettagli in modi differenti, ma la struttura analisi di linea → propagazione → ricerca è un buon modello per comprenderli.
1. Rappresentare il puzzle come insieme di vincoli
Il solver memorizza:
- le sequenze di indizi delle righe;
- le sequenze di indizi delle colonne;
- lo stato corrente di ogni casella: piena, vuota o indeterminata.
Ogni riga e colonna è un problema unidimensionale: trovare le disposizioni dei propri blocchi di indizio compatibili con tutte le caselle già note.
Una griglia completa è valida soltanto quando ogni linea possiede almeno una disposizione compatibile e tutte le caselle concordano nei punti di intersezione riga-colonna.
2. Risolvere una linea
Un solver di linea prova a determinare quali caselle sono forzate dagli indizi della linea e dagli stati già noti.
Esistono diverse strategie di implementazione.
Una strategia pratica, documentata da pbnsolve di WebPBN, trova una collocazione legale con i blocchi spinti il più possibile verso un'estremità e un'altra collocazione verso l'estremità opposta. Le caselle occupate dallo stesso blocco in entrambe le collocazioni estreme possono essere segnate come piene; le caselle dimostrate tra gli stessi blocchi possono essere segnate come vuote.
Solver di linea più completi possono enumerare o calcolare dinamicamente tutti i pattern di linea validi compatibili con lo stato corrente e poi intersecarli.
3. Rimettere nella lista di lavoro le linee incrociate interessate
Supponiamo che il solver di una riga dimostri che la casella R4C7 è piena.
La colonna 7 ora possiede una nuova informazione. Una buona implementazione non deve ricominciare alla cieca da tutta la griglia: può pianificare quella colonna per una nuova elaborazione.
Se la colonna forza poi caselle nelle righe 2 e 8, quelle righe diventano candidate a essere elaborate di nuovo.
È la forma programmatica dello stesso ritmo riga-colonna usato dai giocatori umani.
4. Continuare finché la propagazione raggiunge un punto fisso
Il solver continua a elaborare le linee utili finché si verifica una delle seguenti condizioni:
- ogni casella è determinata;
- compare una contraddizione;
- nessuna linea può produrre un'altra casella forzata.
Il terzo stato è un punto fisso rispetto al metodo di risoluzione corrente. Non significa automaticamente che il puzzle abbia più soluzioni o nessuna soluzione logica. Significa che quel particolare motore inferenziale non riesce a fare altro progresso diretto.
Un solver di linea più forte potrebbe ancora trovare uno stato forzato sfuggito a uno più economico.
5. Rilevare le contraddizioni
Una contraddizione compare quando le ipotesi correnti rendono impossibile qualche vincolo.
Esempi:
- una linea non ha alcuna collocazione valida;
- un blocco confermato è più lungo del proprio indizio;
- un blocco obbligatorio non entra più da nessuna parte;
- una casella è stata forzata sia piena sia vuota attraverso rami incompatibili.
In termini di pattern, una linea con zero pattern validi è impossibile.
Questo rende il rilevamento delle contraddizioni utile sia per validare gli stati del giocatore sia per gli algoritmi di ricerca.
6. Usare probing o ricerca quando la logica diretta si blocca
Un solver generale completo può dover esplorare alternative.
Un semplice approccio depth-first può:
- scegliere una casella indeterminata o una decisione relativa a un blocco;
- assumere uno stato legale;
- eseguire di nuovo la propagazione;
- continuare se il ramo rimane possibile;
- fare backtracking se raggiunge una contraddizione.
Una strategia di probing esplora temporaneamente ipotesi candidate e ne misura le conseguenze prima di decidere quale ramo impegnare. pbnsolve di WebPBN documenta questo approccio in dettaglio.
La distinzione importante è che un computer può usare la ricerca per garantire completezza anche quando la logica pensata per l'uso umano si è fermata.
7. Verificare l'unicità
Per validare un puzzle, trovare una soluzione non basta.
Un solver può continuare a cercare dopo la prima soluzione e chiedere se esista un secondo completamento distinto.
Gli esiti sono:
- zero soluzioni → insieme di indizi incoerente;
- una soluzione → unica;
- due o più → ambiguo.
Per questo i solver automatici sono preziosi non solo per giocare, ma anche nei flussi di costruzione e pubblicazione dei puzzle.
Non tutti i solver usano lo stesso algoritmo
I Nonogrammi possono essere modellati con diversi framework computazionali.
Le implementazioni possono combinare:
- solver di linea personalizzati;
- programmazione dinamica;
- programmazione per vincoli;
- vincoli booleani in stile SAT;
- programmazione intera;
- ricerca depth-first;
- ricerca euristica;
- probing e caching.
La ricerca ha confrontato solver specializzati e proposto formulazioni matematiche alternative. Non esiste una sola architettura obbligatoria.
Ciò che definisce la correttezza è che l'algoritmo rispetti gli indizi e i vincoli delle caselle e che, quando dichiara completezza o unicità, esplori una parte sufficiente dello spazio delle soluzioni da giustificare quell'affermazione.
Logica di linea veloce e logica di linea completa
Un compromesso sottile di implementazione è che una routine di linea molto veloce può non derivare tutte le caselle forzate disponibili su quella linea.
WebPBN osserva esplicitamente che la propria routine di sovrapposizione sinistra/destra è veloce ma non completa, perciò pbnsolve può eseguire un controllo più esaustivo dopo che la normale risoluzione di linea si blocca.
È una distinzione simile a quella umana:
- una tecnica visiva economica può rivelare rapidamente molte caselle;
- l'analisi completa dei pattern validi può rivelare altre caselle forzate a un costo maggiore.
Come un solver può valutare la difficoltà
Quando un solver registra il proprio lavoro, può produrre caratteristiche come:
- numero di risoluzioni di linea;
- numero di round di propagazione;
- inferenza più forte richiesta;
- numero di pattern considerati;
- numero di probe o rami;
- profondità massima della ricerca.
Queste caratteristiche possono alimentare un modello di difficoltà, anche se continueranno a descrivere la difficoltà relativa a quella specifica architettura di solver.
Perché la risoluzione generale può comunque essere difficile
Un solver specializzato può rendere banali molti Nonogrammi da rivista, ma non è noto alcun metodo in tempo polinomiale che risolva tutte le possibili istanze di Nonogrammi a meno di conseguenze profonde per le assunzioni standard della teoria della complessità.
È un'affermazione sul caso peggiore, non l'idea che il tuo Nonogramma quotidiano 15×15 richieda un supercomputer.
Cosa imparare dopo
Per la teoria dietro la difficoltà nel caso peggiore, continua con Perché i Nonogrammi Sono Computazionalmente Difficili. Per l'analogo umano delle ipotesi temporanee, torna a Ragionamento per Contraddizione.
FAQ
I solver di Nonogrammi provano semplicemente ogni griglia con forza bruta?
I buoni solver non ne hanno bisogno. Usano vincoli di linea e propagazione per eliminare enormi quantità di possibilità prima della ricerca, e molti puzzle pubblicati si risolvono senza ramificazioni profonde.
Un solver può dimostrare che un puzzle è unico?
Sì, se esegue una ricerca sufficientemente completa da escludere ogni soluzione alternativa.
I metodi di risoluzione umani e informatici sono uguali?
Si sovrappongono concettualmente, soprattutto nella logica di linea e nella propagazione, ma i computer possono tenere traccia di molti più stati candidati e usare una ricerca sistematica che sarebbe tediosa per una persona.