Blog Stats
  • Posts - 3
  • Articles - 0
  • Comments - 157
  • Trackbacks - 1

 

martedì 20 settembre 2005

Post #2 - Il resto del codice

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)
                
ifthis.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
            
forint 
i = 0 ; i<9 ; ++i){
                
forint 
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;
            
forint 
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];
            
forint 
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...
            
forint 
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;
            
            
forint 
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();

            
whiletrue 
) ;
        }
    }
}

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.

 

 

Copyright © Roberto Giacomelli