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

 

lunedì 26 settembre 2005

Post #3 - Piccolo bug per il Sudoku Solve ricorsivo

 

Si trova nel codice del membro SetCell e consiste in un errato controllo sulla posizione della cella che può assumere i valori da 0 ad 80, mentre l'if esclude sia il valore 0 (prima cella), che il valore 80 (ultima cella), pertanto:

codice con il piccolo ed insidioso bug:

if(CellPosition > 0 && CellPosition < 80)

 

codice corretto:

if(CellPosition > -1 && CellPosition < 81)

 

Ciao a presto!

powered by IMHO 1.2

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.

giovedì 1 settembre 2005

Post #1 - La ricorsione ed il gioco del Sudoku.

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

 

 

Copyright © Roberto Giacomelli