Nel precedente Post
#1 annunciavo la pubblicazione del listato completo della classe
Sudoku, utile per la risoluzione del gioco, eccolo:
//
// Solve the game Sudoku with a recursive function.
// Copyright (C) 2005 Roberto Giacomelli
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
/* Date: 22/08/2005
* Time: 16.44
*
*/
using System;
namespace MySudoku
{
public class Board
{
// Rappresenta il gioco e contiene alcuni metodi
// essenziali per la soluzione con la tecnica ricorsiva.
// Public field
public int[] Cells;
public int[] AvalaibleValuesCount;
public bool[,] AvalaibleValues;
// Public member
public bool IsCoherence()
{
//check sui possibili valori nelle celle vuote
for(int i = 0 ; i<81 ; ++i)
if( this.AvalaibleValuesCount[ i ] < 1) return false;
// array booleani per il controllo
// di congruenza base (applicazione delle regole base)
bool[] h = new bool[9];
bool[] v = new bool[9];
bool[] q = new bool[9];
int CellValue;
for(int i = 0 ; i<9 ; ++i){
h[i] = false;
v[i] = false;
q[i] = false;
}
// check di coerenza sulle regole base
for( int i = 0 ; i<9 ; ++i){
for( int j = 0 ; j<9 ; ++j){
// per le righe
CellValue = this.Cells[ i*9 + j ];
if( CellValue != 0)
if( h[CellValue - 1] ) return false;
else h[ CellValue - 1 ] = true;
// per le colonne
CellValue = this.Cells[ i + 9*j ];
if( CellValue != 0)
if( v[CellValue - 1] ) return false;
else v[ CellValue - 1 ] = true;
// per i quadri
CellValue = this.Cells[ (i/3)*27 + i*3 -(i/3)*9 + j + (j/3)*6 ];
if( CellValue != 0)
if( q[CellValue - 1] ) return false;
else q[ CellValue - 1 ] = true;
}
for(int g = 0; g<9 ; ++g){
h[ g ] = false;
v[ g ] = false;
q[ g ] = false;
}
}
// se tutti i controlli hanno dato esito positivo...
return true;
}
public bool IsSolution()
{
for(int index = 0; index < 81 ; ++index )
if( Cells[ index ] == 0) return false;
return true;
}
public void Print()
{
int tmp = 0;
for(int i = 0 ; i<81 ; ++i){
Console.Write( Cells[ i ] );
++tmp;
if( tmp == 9 ){
Console.WriteLine();
tmp = 0;
}
}
Console.WriteLine();
}
public void SetCell(int CellPosition , int CellValue)
{
if(CellPosition > 0 && CellPosition < 80)
if(CellValue > 0 && CellValue < 10)
Cells[ CellPosition ] = CellValue;
}
public void FillOnes()
{
int index = 0;
int i = 0;
while(index<81){
if( Cells[ index ] == 0 ){
if( AvalaibleValuesCount[ index ] == 1 ){
while( !(AvalaibleValues[ index , i ]) ) ++i ;
Cells[ index ] = ++i ;
i = 0 ;
UpdatePossibility( index );
index = 0;
}
}
++index;
}
}
public int MinPossibilityCell()
{
int Possibility = 9;
int Position = 0;
for( int i = 0 ; i<81 ; ++i)
if(Cells[i] == 0)
if( AvalaibleValuesCount[ i ] < Possibility ){
Possibility = AvalaibleValuesCount[ i ];
Position = i;
}
return Position;
}
public bool[] PossibilityValues(int Position)
{
// è possibile migliorare questo?
bool[] g = new bool[9];
for( int y = 0 ; y<9 ; ++y)
g[ y ] = AvalaibleValues[ Position , y ];
return g;
}
public Board( Board BaseGame )
{ // costruttore overload
this.Cells = new int[ 81 ];
this.AvalaibleValuesCount = new int[ 81 ];
this.AvalaibleValues = new bool[ 81 , 9 ];
for(int i=0 ; i<81 ; ++i){
this.Cells[ i ] = BaseGame.Cells[ i ];
this.AvalaibleValuesCount[ i ] = BaseGame.AvalaibleValuesCount[ i ];
for(int j = 0 ; j < 9 ; ++j )
this.AvalaibleValues[ i , j ] = BaseGame.AvalaibleValues[ i , j ];
}
}
public Board(int[] vector)
{
// azioni del costruttore (da implementare la
// gestione degli errori con le eccezioni)
Cells = new int[81];
for(int i=0 ; i<81 ; ++i ) Cells[ i ] = vector[ i ];
// controllare se si può direttamente scrivere Cells = vector
AvalaibleValuesCount = new int[81];
AvalaibleValues = new bool[81,9];
for(int i = 0 ; i<81 ; ++i){
for(int r = 0 ; r<9 ; ++r) AvalaibleValues[ i , r ] = true;
AvalaibleValuesCount[ i ] = 9;
}
// costruisce i giusti valori per gli array Avalaible...
for( int i = 0 ; i<81 ; ++i )
if( Cells[ i ] != 0)
UpdatePossibility( i );
}
public void UpdatePossibility(int PosCell)
{
int CellValue = Cells[ PosCell ];
int H = PosCell / 9 ;
int V = PosCell - H * 9;
int Q = (H/3)*27 + (V/3)*3;
for( int t = 0 ; t<9 ; ++t){
if(Cells[ H*9 + t ] == 0)
if( AvalaibleValues[ H*9 + t , CellValue - 1]){
AvalaibleValues[ H*9 + t , CellValue - 1] = false;
AvalaibleValuesCount[ H*9 + t ] -= 1;
}
if(Cells[ V + t*9 ] == 0)
if( AvalaibleValues[ V + t*9 , CellValue - 1]){
AvalaibleValues[ V + t*9 , CellValue - 1] = false;
AvalaibleValuesCount[ V + t*9 ] -= 1;
}
if(Cells[ Q + t + (t/3)*6 ] == 0)
if( AvalaibleValues[ Q + t + (t/3)*6 , CellValue - 1] ){
AvalaibleValues[ Q + t + (t/3)*6 , CellValue - 1] = false;
AvalaibleValuesCount[ Q + t + (t/3)*6 ] -= 1;
}
}
}
}
public class Sudoku
{
private Board StartGame;
public int SolutionsCount;
public void Print()
{
StartGame.Print();
}
public void Solve()
{
this.SolutionsCount = SolveR( StartGame );
}
public Sudoku(int[] v) // costruttore
{
// Check input game coherence
StartGame = new Board( v );
if( StartGame.IsCoherence() ) Console.WriteLine("Gioco coerente");
else Console.WriteLine("Gioco incoerente XXXX ");
}
// Solve game with a recursive method
// and return the number of solutions.
//
private int SolveR( Board PlayGame )
{
PlayGame.FillOnes();
if( !(PlayGame.IsCoherence() ) ){
return 0 ;
}
if( PlayGame.IsSolution() ){
PlayGame.Print();
return 1 ;
}
int PosMinCell = PlayGame.MinPossibilityCell();
bool[] Key = PlayGame.PossibilityValues( PosMinCell );
int SolCount = 0;
for(int Value = 0 ; Value < 9; ++Value)
if( Key[ Value ] ){
Board Game1 = new Board( PlayGame );
Game1.SetCell( PosMinCell , Value + 1 );
Game1.UpdatePossibility( PosMinCell );
SolCount += SolveR( Game1 );
}
return SolCount;
}
}
}
// Ecco come potrebbe essere il metodo main
using System;
namespace MySudoku
{
public class Test
{
public static void Main(string[] args)
{
Console.WriteLine("Inizio gioco...");
int[] diabolic = { 8,0,1,0,0,0,5,0,0,
2,0,0,0,0,9,0,4,0,
5,3,0,0,0,0,0,0,0,
0,0,0,2,9,0,0,0,0,
0,0,4,0,0,0,1,0,0,
0,0,0,0,4,1,0,0,0,
0,0,0,0,0,0,0,9,2,
0,5,0,7,0,0,0,0,8,
0,0,8,0,0,0,4,0,3};
Sudoku Game = new Sudoku( diabolic );
Game.Print();
Game.Solve();
Console.WriteLine("Fatto");
Console.WriteLine("Number of Solution: {0}", Game.SolutionsCount );
Console.WriteLine();
while( true ) ;
}
}
}
Struttura:
La classe Sudoku fa uso della classe Board nella quale sono
implementati i metodi principali per il controllo dei numeri presenti,
la costruzione delle informazioni riguardanti i possibili valori delle
singole celle, ecc oltre che le strutture dati necessarie.
Da notare nel metodo SolveR(), la creazione di una nuova istanza Board
prima della chiamata ricorsiva. Non è infatti possibile
sfruttare il meccanismo di copia locale della variabile essendo gli
oggetti dei tipi reference.
Si potrebbe pensare di utilizzare una struct (tipo valore)
anziché una classe per la definizione di Board, ma al suo
interno non potremmo far uso di array che, in quanto oggetti, non
possono essere semplicemente contenuti in un tipo valore.
Cambiando semplicemente la parola chiave da class a struct per Board,
si otterrebbe lo stesso risultato.
Allo scopo di risolvere il problema, è stato scritto un nuovo
costruttore per la creazione di un oggetto Board passando come
argomento un altro oggetto Board.
Altre particolarità:
Il metodo FillOnes() di Board utilizza un ciclo while, anzichè
un ciclo for su tutte le celle del gioco.
Il motivo è che trovata una cella in cui possiamo sistemare un
solo valore tra quelli possibili, viene successivamente chiamato il
metodo UpdatePossibility() che altera le possibilità per il
resto delle celle, per cui il controllo sull'unicità dei
possibili valori dovrà ricominciare dalla prima cella.
Ultimi commenti al codice:
Poiché si è deciso per motivi di efficienza, di
rappresentare il gioco con un vettore anziché con una matrice
(come sarebbe naturale), nel codice della classe Board si fa massiccio
uso della divisione tra interi.
Da fare:
1 - Gestione errori
2 - Ottimizzare il codice
3 - Fornire un interfaccia grafica al gioco analizzando come deve
essere modificata la classe Sudoku.
Scusate per la brevità di queste note, ma sarò lieto di
discutere eventuali migliorie e fornire ogni delucidazioni su dettagli
e particolari. Non fareste altro che farmi piacere.
Ciao a presto.
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!
powered by IMHO 1.2