Un computer può risolvere il sudoku senza semplicemente sostituire i numeri e controllare?

Supponiamo che Sudoku significhi Sudoku ben formato (cioè con una e una sola soluzione).

Semplicemente sostituendo tutti i numeri indecisi e controllando richiederebbe una quantità enorme di tempo.

Il metodo di ricerca più veloce combina la ricerca di profondità (aggiungere i numeri possibili uno per uno) con la propagazione elementare dei vincoli (ECP): ogni volta che si verifica un numero possibile, eliminare tutti i candidati che sono legati ad esso da una contraddizione diretta (secondo le regole).

La ricerca di profondità accetta una soluzione non appena viene trovata. Può trovare più soluzioni, se ce ne sono. Ma se si ferma alla prima soluzione (come si fa generalmente quando si sa che il puzzle è ben formato), non prova l'unicità. In questo senso, la ricerca per profondità permette una qualche forma di indovinare.

Ho dimostrato che un'altra procedura di ricerca molto semplice senza indovinare, Trial-and-Error (T&E), richiede solo due livelli di ipotesi per tutti i Sudoku 9x9 conosciuti (e probabilmente per tutti i Sudoku 9x9) e che un solo livello è sufficiente per tutti i puzzle 9x9 tranne una piccolissima parte (~ 1 su 30.000.000).

Ora, per rispondere alla tua domanda: sì, la maggior parte dei Sudoku 9x9 può essere risolta senza usare la ricerca a priori o anche il T&E, usando un approccio "pattern-based" di soddisfazione dei vincoli. Fondamentalmente, significa usare regole che possono essere usate dai solutori umani. Una questione è, quali tipi di regole si considerano accettabili o meno. Tutti i puzzle a livello 0 o 1 di T&E possono essere risolti da una specie di catena che ho chiamato "treccia".

Per i dettagli, vedi il mio libro "Pattern-Based Constraint Satisfaction and Logic Puzzles" (la prima edizione è gratuita.)