Sudoku FlowCome i computer risolvono il Sudoku
Aggiornato il 2026-10-05
Backtracking
Il risolutore prova una cifra ammessa in una cella vuota e prosegue. Se nessuna cifra porta a una soluzione, annulla una scelta precedente e ne prova un'altra. Scegliere prima la cella con il minor numero di cifre possibili spesso rende la ricerca molto più breve.
Fonti: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Copertura esatta e Dancing Links
Il Sudoku può essere riformulato come un problema di copertura esatta: scegliere le assegnazioni in modo che ogni cella e ogni cifra in ogni riga, colonna e riquadro siano coperte esattamente una volta. In un articolo del novembre 2000, Donald Knuth descrisse Dancing Links, un modo efficiente per eseguire il suo Algorithm X basato sul backtracking; applicato al modello di copertura esatta del Sudoku, trova rapidamente tutte le soluzioni di un rompicapo.
Fonti: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Ricerca casuale
Alcuni programmi riempiono la griglia in modo casuale e poi riordinano i numeri per ridurre il numero di conflitti, con metodi come la ricottura simulata o gli algoritmi genetici. Sono stati studiati come approcci alternativi; la loro efficacia dipende dal programma e dal rompicapo.
Fonti: Wikipedia: Sudoku solving algorithms
Risolutori che ragionano come le persone
Un motore di suggerimenti ha un compito diverso: oltre a trovare la risposta, deve mostrare il passo successivo che una persona può seguire. Il motore della nostra app prova le tecniche umane in un ordine fisso, dalle più semplici, come il Singolo nascosto, alle più difficili, come le catene e gli insiemi quasi bloccati, e usa la prima che porta all'inserimento di una cifra; quelle più difficili funzionano eliminando prima i candidati. La tecnica più difficile che usa per un rompicapo determina il livello di quel rompicapo nell'app.
Fonti: Cosa richiede ogni livello di difficoltà del Sudoku
