Robitex's Blog

Ideas in the web

Sudoku in java Parte 2


Il codice completo

Il codice seguente implementa un applicazione java con output nella console, per la risoluzione del gioco del Sudoku con una funzione ricorsiva, completando il post precedente.

Questa soluzione fa uso di classi enum, costrutto di Java 5 (JDK 1.5) e di operazioni bitmask per incrementare le performance (bit 0 = valore ammesso nella cella, bit =1 valore non ammesso). Infatti potenzialmente passando al codice la griglia vuota, vengono trovate TUTTE le soluzioni possibili del gioco. Peccato che occorrano circa 10.000 anni di lavoro per un PC desktop per terminare il compito…

/*
 * Sudoku.java
 * Solve the game Sudoku with a recursive function.
 * 
 * Versione base: 0.1.0.0
 * Date: 10/11/2005 - Start date: 22/08/2005
 * 
 * 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.
 */
 
/**
 * The new class Sudoku implements new java feature enum
 * to manage the grid game symbols.
 * Not filled cells are treatment with null reference.
 * Another change to original Sudoku code is bitwise operation
 * for indicates the possible values in an empty cell.
 *
 * Conception: 18 novembre 2005
 * Author: Roberto Giacomelli
 * @param v is an array of int that represent start grid of game
 */
public class Sudoku {
    
    public enum      gridSymbol {
    // non è possibile inserire l'enum in grid
   // perché in una inner class non sono
   // ammessi metodi static.
        A, B, C, D, E, F, G, H, I ;
    }

    private Grid  startGame;
    public  int   solutionsCount;
    
    /**
     * Costruttore unico della classe Sudoku
     */
    public Sudoku(int[] v) {
        startGame = new Grid( v );
    }
    
    /**
     * Wrapper method to calling recursive function
     */
    public void solve() {
            solutionsCount = solveRecursive( startGame );
    }
    
    /**
     * Solve game with a recursive method
     * and return the number of grid's solutions.
     */
    private int solveRecursive( Grid PlayGame ) {
        if ( !(PlayGame.isCoherence() ) ) {
            return 0 ;
        }
        
        PlayGame.fillOnes();
        
        if (PlayGame.isSolution()) {
            PlayGame.print();
            return 1 ;
        }
        
        int posMinCell = PlayGame.minPossibilityCell();
        int cellPossibility = PlayGame.avalaibleValues[ posMinCell ]; 
        int solCount = 0;
        
        for (int val = 0; val < 9; ++val) {
            if ( ( cellPossibility & 1 ) == 0 ) {
               Grid Game1 = new Grid( PlayGame );
               Game1.setCell(posMinCell , gridSymbol.values()[val]);
               Game1.updatePossibility( posMinCell );
                solCount += solveRecursive( Game1 );
            }
            cellPossibility = cellPossibility >> 1;
        }
        return solCount;
    }
    
    public void printGrid() {
        startGame.print();
    }
    
    
    /**
    * Grid inner class:
    * store data game and esposed essential methods
    * to solve game in a recursive manner.
    */
    private class Grid {
        // store grid values (enum type)
        private gridSymbol[] Cells;
      // store not empty cell count of possibility values
        private int[] avalaibleValuesCount;

      // zero is 'possible all values'
      // eight is 'possible only one value'
        private int[] avalaibleValues;
       // store not empty cell possibility values
      // an int is bitwise intended
        
        public Grid( int[] vector ) {
        // costruttore standard
            Cells = new gridSymbol[ 81 ];
            avalaibleValuesCount = new int[81];
            avalaibleValues = new int[81];
       // zero are default value
            
            for (int i=0 ; i<81 ; ++i ) {
                if ( vector[ i ] != 0 ) {
                    Cells[i] = gridSymbol.values()[vector[i] - 1];
                }
            }
            
            // build array avalaible...
            for (int i = 0; i<81; ++i){
               if (Cells[ i ] != null) {
                   updatePossibility( i );
               }
            }
        }
        
        public Grid( Grid BaseGame ) {
          // costructor overload
            Cells = new gridSymbol[ 81 ];
            avalaibleValuesCount = new int[ 81 ];
            avalaibleValues = new int[ 81 ];
            
            //~ Cells = ( gridSymbol[] ) BaseGame.Cells.clone();
        // cast from object to array
            //~ avalaibleValuesCount = ( int[] ) BaseGame.avalaibleValuesCount.clone();
            //~ avalaibleValues = ( int[] ) BaseGame.avalaibleValues.clone();
            
            // code equivalent to clone() array method
            for (int i=0 ; i<81 ; ++i){
                Cells[ i ] = BaseGame.Cells[ i ];
           // copy grid values
                avalaibleValuesCount[ i ] = BaseGame.avalaibleValuesCount[ i ];
                avalaibleValues[ i ] = BaseGame.avalaibleValues[ i ];
            }
        }
        
        public boolean isCoherence() {
            for (int valueCount : avalaibleValuesCount ) {
                if ( valueCount>8) {
                    return false;
                }
            }
            
            // array booleaneani per il controllo
            // di congruenza base (applicazione delle regole base)
            boolean[] h = new boolean[9];
            boolean[] v = new boolean[9];
            boolean[] q = new boolean[9];
            
            int rowIndex ;
            int colIndex ;
            int squareIndex ;
            int CellValue;
            
            // check di coerenza sulle regole base
            for ( int i = 0 ; i<9 ; ++i) {
                for ( int j = 0 ; j<9 ; ++j) {
                    rowIndex = i*9 + j;
                    colIndex = i + 9*j;
                    squareIndex = (i/3)*27 + i*3 -(i/3)*9 + j + (j/3)*6;
                    
                    if ( Cells[ rowIndex ] != null ) {                 // per le righe
                        CellValue = Cells[ rowIndex ].ordinal();
                        if ( h[ CellValue ] ) {
                            return false;
                        } else {
                            h[ CellValue ] = true;
                        }
                    }
                    
                    if ( Cells[ colIndex ] != null ) {                 // per le colonne
                        CellValue = Cells[ colIndex ].ordinal();
                        if ( v[ CellValue ] ) {
                            return false;
                        } else {
                            v[ CellValue ] = true;
                        }
                    }
                    
                    if ( Cells[ squareIndex ] != null ) {                 // per i quadri
                        CellValue = Cells[ squareIndex ].ordinal();
                        if ( q[ CellValue ] ) {
                            return false;
                        } else {
                            q[ CellValue ] = true;
                        }
                    }
                }
                
                java.util.Arrays.fill( h , false );
                java.util.Arrays.fill( v , false );
                java.util.Arrays.fill( q , false );
            }
            
            // se tutti i controlli hanno dato esito positivo:
            return true;
        }
            
        public void updatePossibility( int PosCell ) {   // shift bitwise operator
            final int BITMASK = 1 << Cells[ PosCell ].ordinal();
           // initial cell pos in row
            final int H = PosCell / 9;
          // initial cell pos in column
            final int V = PosCell - H * 9;
          // initial cell pos in square
            final int Q = (H/3)*27 + (V/3)*3;
            
            // cell position in row
            int row;
            // cell position in column
            int column;
            // cell position in square
            int square;
            
            for ( int t = 0 ; t<9 ; ++t){
                row = H*9 + t;
                column = V + t*9;
                square = Q + t + (t/3)*6;
                
                if (Cells[ row ] == null) {
                    if ( ( avalaibleValues[ row ] & BITMASK ) == 0 ) {
                        avalaibleValues[ row ] = ( avalaibleValues[ row ] | BITMASK );
                        avalaibleValuesCount[ row ] += 1;
                    }
                }
                if (Cells[ column ] == null) {
                    if ( ( avalaibleValues[ column ] & BITMASK ) == 0 ) {
                        avalaibleValues[ column ] = ( avalaibleValues[ column ] | BITMASK );
                        avalaibleValuesCount[ column ] += 1;
                    }
                }
                if (Cells[ square ] == null) {
                    if ( ( avalaibleValues[ square ] & BITMASK ) == 0) {
                        avalaibleValues[ square ] = ( avalaibleValues[ square ] | BITMASK );
                        avalaibleValuesCount[ square ] += 1;
                    }
                }
            }
        }
            
        public void fillOnes() {
            int index = 0;          // cycle index
            int i = 0;              // inner counter
            int temp;               // temp variable shifted to right
            
            while (index<81) {
                if ( Cells[ index ] == null ) {
                    if ( avalaibleValuesCount[ index ] == 8 ) {
                        temp = avalaibleValues[ index ];
                        while ( (temp & 1) == 1 ) {
                            temp = temp >> 1 ;
                            ++i;
                        }
                        Cells[ index ] = gridSymbol.values()[ i ];
                        i = 0 ;
                        updatePossibility( index );
                        index = 0;
                    }
                }
               ++index;
            }
        }
        
        public boolean isSolution() {
            for ( gridSymbol index : Cells ) {
                    if ( index == null) {
                        return false;
                    }
            }
            return true;
        }
        
        public void setCell(int cellPosition , gridSymbol cellValue) {
            Cells[ cellPosition ] = cellValue;
        }
        
        public int minPossibilityCell() {
            int possibility = 0;
            int pos = 0;
            for (int i = 0; i < 81; ++i) {
                if (Cells[ i ] == null) {
                    if ( avalaibleValuesCount[ i ] > possibility ) {
                        possibility = avalaibleValuesCount[ i ];
                        pos = i;
                    }
                }
            }
            return pos;
        }
        
        public void print() {
            for(int i = 0 ; i<81 ; ++i){
                if ( Cells[ i ] == null ) {
                    System.out.print( 0 );
                } else {
                    System.out.print( Cells[ i ].ordinal() + 1 );
                }
                
                if ( (i+1) % 27 == 0 ){
                    System.out.println();
                    System.out.println();
                } else if ( (i+1) % 9 == 0 ) {
                    System.out.println();
                } else if ( (i+1) % 3 == 0 ) {
                    System.out.print("  ");
                } else {
                    System.out.print(" ");
                }
            }
        }
    }
}

La classe Sudoku può essere utilizzata in questo modo:

// Performance del seguente programma:
// circa 6.000 solutionspersec on T1000 (Athlon 1 GHZ)
// circa 15.000 solutionspersec on Pentium 4 HT 3 GHZ
//
public class TestConsole {
    public static void main( String[] args ) {
        int[] diabolic = {  0,1,4,  0,0,0,  9,5,0,
                                 0,0,8,  0,4,0,  2,0,0,
                                 0,9,0,  5,0,3,  0,6,0,

                                 0,0,0,  3,8,4,  0,0,0,
                                 7,0,0,  0,0,0,  0,0,6,
                                 0,0,0,  6,9,7,  0,0,0,

                                 0,4,0,  2,0,1,  0,8,0,
                                 0,0,1,  0,6,0,  3,0,0,
                                 0,5,2,  0,0,0,  6,1,0};
				 
            System.out.println("Start game...");
            Sudoku Game = new Sudoku( diabolic );
            Game.printGrid();
	    Game.solve();
	    System.out.println("Done");
            System.out.println("First Solution of the game:");
            System.out.println("Number of Solutions: " + Game.solutionsCount );
            System.out.println();
        }
    }

Il codice deve essere compilato installando un JDK versione 1.5 o seguente.
Alla prossima.

3 risposte a “Sudoku in java Parte 2

  1. Midnightmare 07/10/2010 alle 14:36

    Ho dato un’occhiata al sorgente e mi chiedevo come mai usassi gli operatori bitwise. Forse per guardagnare in termini di prestazioni?

    Io ho creato un algoritmo in C++ che però trova un unica soluzione alla griglia dell’esempio.

    Come fa questo algoritmo ad essere così veloce?

    Forse nel mio il problema è la lentezza di certe funzioni di libreria?

    Ecco il sorgente: http://cpp.pastebin.com/yAWeJzAF

    • robitex 07/10/2010 alle 17:45

      Accipicchia, una raffica di argomenti…🙂
      I) Ho usato i bitwise per due motivi: per impararli ad usare e per velocizzare il codice. Faceva quindi parte dell'”esperimento”. Il punto veramente importante a mio avviso è la sequenza di cose che vengono fatte per gestire la ricorsione.
      II) Se ti può confortare, effettivamente quella griglia ha una sola soluzione, perciò se il tuo risultato lo conferma, ciò è un punto a favore sulla correttezza del codice.
      III) La velocità: purtroppo non ho sufficiente tempo per studiare il tuo codice, ma la velocità a mio avviso dipende molto dal cercare di riempire la griglia il più possibile prima di avviare nuovi alberi di soluzioni con la ricorsione.
      Se tu osservi il codice del post, vedrai una funzione chiamata fillOnes(). Il suo compito è individuare le celle ancora vuote in cui è possibile inserire un solo valore. Questa funzione si può ulteriormente migliorare, sempre per riempire più celle possibili della griglia, proprio come si farebbe a mano. Alla fine, quando per le celle vuote rimaste rimangono alternative ugualmente valide, si creano nuove griglie figlie ciascuna con un numero diverso tra quelli possibili in una cella scelta, e si riparte con la ricerca di soluzioni.

      Grazie e buon lavoro.

  2. Midnightmare 07/10/2010 alle 18:37

    Nel mio codice c’e’ una funzione che cerca celle con il minor numero di valori assegnabili possibili, quindi automaticamente vengono considerate per prime quelle che ne hanno solo 1.

    Grazie per la risposta.

    Saluti

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: