il Sudoku

Un Sudoku è una griglia di 9x9 celle in ognuna delle quali si dovrà scrivere un numero, da 1 a 9. La griglia è a sua volta divisa in 9 riquadri di 3x3 celle.
In ogni colonna, in ogni riga e in ogni regione, ogni numero deve comparire una volta sola.
Il solitario consiste nel completare uno schema riempito solo parzialmente da 20-30 valori.

Soluzione del Gioco

In prima battuta si cercano le celle in cui inserire con certezza un valore: ogni valore inserito esclude copie di se stesso sulla riga, sulla colonna e nel riquadro di appartenenza; quindi cercheremo celle in cui è possibile inserire un solo valore, oppure valori che su una riga o su una colonna o in un riquadro hanno una sola possibilità di accoglienza.
In questo modo viene trovata la soluzione degli schemi di difficoltà media.

In alcuni casi occorre procedere "per tentativi": in una cella vuota viene inserito un valore possibile, procedendo con le conseguenze "certe" e poi con un'altra ipotesi in un'altra casella vuota; quando si giunge a un punto di incongruenza, si fa marcia indietro.
Nel programma questa operazione è realizzata tramite una funzione ricorsiva.

Struttura dati

La tavola di gioco è allocata in una matrice 9x9. Ogni cella della matrice è in realtà un array di 10 caselle, dove la casella 0 indica se la cella è libera (0) o occupata (1..9), mentre le nove caselle successive indicano ciascuna la possibilità di inserire nella cella il valore corrispondente (Flag 1=inserimento possibile). La matrice è dunque tridimensionale.

int Tav[9][9][10]	Tavola di gioco
int Nvuote	Numero di caselle vuote nella tavola

Algoritmo

Lo schema da completare viene caricato dal file SUDOKU.TXT nella stessa cartella dove risiede l'eseguibile; vengono esaminati solo i primi 9 records del file e, di questi, solo i primi 9 caratteri: il resto del file può essere occupato da commenti. Tutti i caratteri diversi da 1,2,3,4,5,6,7,8 e 9, sono considerati Spazi.
Man mano che i valori sono inseriti nelle celle, vengono azzerate le flag di "disponibilità" di quel valore nelle altre celle della riga, della colonna e del riquadro.
A questo punto si cercano i valori CERTI da inserire sulla tavola di gioco, esaminando le Flag "possibilità" delle celle:

se una cella vuota possiede una sola flag==1, inseriamo quel valore;
per ogni riga, colonna e gruppo, se un valore è disponibile in una sola posizione vuota, inseriamo il valore.

Ogni inserimento può creare nuove certezze, quindi l'operazione viene ripetuta finché è possibile inserire numeri sicuri.
Se non è stato possibile giungere ad una soluzione completa, inizia l'analisi con il metodo Montecarlo, ovvero esaminando tutte le combinazioni possibili, tramite una funzione ricorsiva.

Codice Sorgente in C

Il programma sorgente è per Visual C++ in modalità console, ma può essere rapidamente adattato ad altri compilatori; è possibile scaricare l'eseguibile di 36 Kb.

Considerazioni finali

Il gioco si è rivelato deludente dal punto di vista della complessità computazionale per un computer; tutti gli schemi, anche quelli catalogati "diabolici", vengono risolti da un Athlon 2600 in pochi decimi di secondo!
Se non è disponibile lo schema parziale nel file Sudoku.txt, il programma crea uno schema completo partendo da zero (sempre in pochi decimi di secondo).