In questa pagina
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.
Ricalcola i candidati legali e inserisci ripetutamente i valori forzati.
Un solver può codificare esplicitamente tecniche come Singles, subset, Fish o Chains.
Prova un'alternativa, propaga le conseguenze e torna indietro in caso di contraddizione.
Usa i risultati della ricerca per contare soluzioni, stimare la difficoltà o validare l'obiettivo di un costruttore.
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.