giaconet

Post #3 - Piccolo bug per il Sudoku Solve ricorsivo

Roberto Giacomelli — Mon, 26 Sep 2005 13:35:00 GMT

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!

Post #2 - Il resto del codice

Roberto Giacomelli — Tue, 20 Sep 2005 18:33:00 GMT

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.

Roberto Giacomelli — Thu, 01 Sep 2005 09:15:00 GMT

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!