Un computer può affrontare il Sudoku con obiettivi diversi: trovare una soluzione, contare quante soluzioni esistono oppure imitare un percorso umano. Backtracking, exact cover, Algorithm X e DLX sono strumenti per la completezza; un solver human-style è invece progettato per spiegare deduzioni riconoscibili.
Sudoku come problema di vincoli
Ogni cella deve scegliere una cifra mentre righe, colonne e box impongono vincoli di esclusione. Un solver completo cerca una assegnazione che soddisfi tutti questi vincoli, non necessariamente nello stesso modo in cui ragiona una persona.
Propagazione dei candidati
La propagazione aggiorna i domini delle celle ogni volta che una cifra viene fissata. Quando un dominio o una posizione di unità diventa singola, il solver può applicare una nuova conseguenza senza ramificare.
Backtracking
Il backtracking sceglie una alternativa, propaga i vincoli e torna indietro se il ramo diventa impossibile. Con buone euristiche è estremamente efficace per trovare o contare soluzioni.
Conteggio delle soluzioni
Per verificare unicità, il solver non deve soltanto trovare una soluzione: deve dimostrare che non ne esiste una seconda. In pratica si esegue una ricerca completa con arresto anticipato appena vengono trovate due soluzioni; 0, 1 e 2+ sono stati distinti.
Sudoku come exact cover
Il Sudoku classico può essere rappresentato come exact cover: ogni assegnazione riga-colonna-cifra copre esattamente quattro vincoli, uno di cella e tre di unità/cifra.
Algorithm X
Algorithm X è l’algoritmo di Knuth per cercare soluzioni a un problema exact-cover scegliendo ricorsivamente righe che coprono le colonne di vincolo ancora aperte.
Dancing Links (DLX)
Dancing Links, o DLX, implementa efficientemente le operazioni di rimozione e ripristino delle righe/colonne della matrice exact-cover durante Algorithm X.
Constraint programming e modelli in stile SAT
Il Sudoku può essere espresso come un insieme di variabili e vincoli e affidato a solver generali CSP/SAT. Questi sistemi usano propagazione e ricerca altamente ottimizzate; sono eccellenti per validazione, anche se il loro percorso interno non coincide con una spiegazione umana.
Solver human-style
Un solver human-style applica tecniche nominate e produce un percorso spiegabile. È utile per hint e rating; non deve sostituire il solver completo che verifica il numero di soluzioni.
Perché solver completi e human-style dovrebbero essere separati
Un solver human-style applica tecniche nominate e produce un percorso spiegabile. È utile per hint e rating; non deve sostituire il solver completo che verifica il numero di soluzioni.
Come un generatore usa i solver
Un generatore usa un solver completo per validità e unicità e può usare un secondo solver human-style per difficoltà e percorso. Separare questi ruoli evita di confondere “non so risolverlo con la mia libreria di tecniche” con “il puzzle non ha una soluzione unica”.
I computer indovinano?
Algoritmi come backtracking esplorano alternative, ma lo fanno sistematicamente e tornano indietro quando un ramo viola i vincoli. Chiamarlo “guessing” può essere intuitivo, ma è più preciso parlare di ricerca completa; non è la stessa esperienza della risoluzione logica umana.
FAQ
Qual è l’algoritmo più veloce per il Sudoku?
Dipende dall’obiettivo e dall’implementazione. Backtracking con buona propagazione, Algorithm X/DLX e solver CSP/SAT possono tutti essere estremamente rapidi sul 9×9; non esiste un vincitore universale per ogni carico di lavoro.
Quali sono i 324 vincoli exact-cover?
Nel modello exact-cover standard ci sono 81 vincoli di cella, 81 cifra-riga, 81 cifra-colonna e 81 cifra-box: in totale 324 colonne di vincolo.
Perché ci sono 729 righe candidate?
Ogni possibile assegnazione riga-colonna-cifra è una riga candidata: 9×9×9 = 729 possibilità prima di applicare gli indizi.
Algorithm X e Dancing Links sono la stessa cosa?
No. Algorithm X è l’algoritmo generale per exact cover; Dancing Links è una struttura dati e tecnica di implementazione particolarmente efficiente per eseguirlo.
I solver human-style usano backtracking?
Un solver human-style puro normalmente no: applica tecniche spiegabili. Un sistema completo può però affiancare un motore di backtracking per verificare soluzioni e unicità senza mostrarlo come passo umano.
Cosa imparare dopo
Per collegare gli algoritmi alla produzione, passa a come vengono generati i Sudoku e a come si costruisce un puzzle con unicità e difficoltà controllate.