Post #1 - La ricorsione ed il gioco del Sudoku.
Day:30 agosto
2005
Scorrendo il codice scritto da Francesco Balena sul blog in dotnet2themax
riguardante il famigerato Sudoku, mi è venuta la curiosità di provare a cercare
un metodo che facesse uso della ricorsione per trovare le soluzioni del
gioco.
Semplice ed elegante.
Il gioco come forse saprete, si svolge su una tavola di 9 x 9 celle da
riempire con un numero compreso tra 1 e 9 (è possibile riferirsi a nove diversi
simboli, ma i numeri offrono una comprensione più immediata), in base ad una
semplice regola d'esclusione: per ciascuna riga, colonna o riquadro (9 sotto
tavole 3 x 3 ) ciascun valore compare una sola volta (vedi l'articolo di
Piergiorgio Odifreddi su "Le Scienze" di Agosto 2005 pag. 109 per notizie
sostanziose sul gioco).
In una data cella, applicando la regola base, si escludono tra i nove
possibili valori quelli già presenti nella corrispondente riga, colonna o
riquadro, ottenendo le uniche possibili alternative.
Inserendo questi valori nella cella dello schema uno per volta, si hanno
altrettanti schemi figli che possono portare a soluzioni.
Ripetendo l'operazione di determinazione delle altenative e d'inserimento
dei valori possibili nelle celle, si costruisce un albero di schemi le cui
foglie o sono soluzioni, o sono schemi incoerenti (uno schema è incoerente se vi
sono violazioni alla regola base).
Questo metodo per tentativi e verifiche è anche il più banale, ma
permette di sperimentare la ricorsione ed i costrutti del linguaggio.
Veniamo al codice.
La struttura del codice è organizzata in due classi, la prima ( Board )
rappresenta lo schema del gioco ed espone i metodi base per determinare le
alternative dei valori nelle celle e verificare la coerenza dello
schema.
La seconda classe ( Sudoku ) rappresenta il gioco con il metodo ricorsivo
di soluzione che quindi esplora un albero di possibili schemi.
Tale metodo procede in questo modo:
1 – riempire le celle dello schema che hanno un'unica alternativa tra i
nove valori ( FillOnes )
2 – verificare se lo schema è ancora coerente ( IsCoherence )
3 – verificare se lo schema è soluzione ( IsSolution )
4 – altrimenti inserire in una cella i valori possibili e ricominciare
dal punto 1
Il linguaggio scelto per la scrittura del codice è C#. Molti nomi che si
trovano nel listato di Francesco Balena sono stati mantenuti, come pure
l'utilizzo di array monodimensionali per non decrementare le performance, ed il
valore zero per rappresentare una cella vuota, mentre alcuni campi sono stati
invece eliminati ( GroupInfo ). Ringrazio Francesco Balena e tutti quelli che
vorranno segnalare errori o dar seguito ad ulteriori sviluppi.
Ecco la funzione ricorsiva di soluzione (sotto licenza GPL):
private
void
SolveR(
Board
PlayGame ,
int
PosCell
,
int
CellValue
)
{
if(
CellValue
!=
0
){
PlayGame.SetCell(
PosCell
,
CellValue
);
PlayGame.UpdatePossibility(
PosCell
);
}
PlayGame.FillOnes();
if(
!(PlayGame.IsCoherence()
) ){
return;
}
if( PlayGame.IsSolution() ){
PlayGame.Print();
return;
}
int
PosMinCell
=
PlayGame.MinPossibilityCell();
bool[]
Key
=
PlayGame.PossibilityValues(
PosMinCell
);
for(int
Value
=
0
;
Value
<
9;
++Value)
if(
Key[
Value
]
){
Board
Game1 =
new
Board(
PlayGame
);
SolveR(
Game1
,
PosMinCell
,
Value
+
1
);
}
}
Prossimamente pubblicherò il listato completo con qualche modifica: a
presto... bye, è ora di una vacanza!