Da quando ho imparato a fare i Sudoku mi sono sempre chiesto come fare un programma che li risolvesse 😊
La cosa non è difficile, soprattutto per quelli semplici, che ero già riuscito a risolvere con PHP 😊
Tuttavia non ero andato più avanti perché non avevo considerato la risoluzione tramite brute force, invece recentemente, anche per consolidare la mia conoscenza di C++, mi sono messo e ho fatto questo programmino.
In pratica l’algoritmo di risoluzione si divide in due parti: la prima con un loop crea le possibili soluzioni per ogni cella e le inserisce fino a quando il sudoku non viene più modificato. Quindi se ci sono celle ancora vuote (con possibili soluzioni) tenta il brute force, altrimenti esce. Il brute force è implementato tramite ricorsione: prima ordino le soluzioni in modo da partire dalla cella con meno soluzioni possibili, quindi prendo le soluzioni una ad una e provo a vedere se impostandole ce la faccio a risolvere il sudoku. Quando ce l’ho fatta termino il programma.
Se volete il sorgente, eccolo qui: sudoku.cpp.
L’ho provato su Linux e andava.
Penso che si possa migliorare il programma ma per il momento mi va bene così 😊
Aggiornamento 31/05/2012: aggiunto un meccanismo di controllo, perché prima con certi sudoku difficili il brute force falliva.