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.