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.
, dunque la crescita è esponenziale! All’ottava iterazione il numero dei punti è 65536!
la copia del disegno deve esser fatta ad una distanza di 
, poichè ogni volta che si sale di un livello, il lato del triangolo raddoppia (il doppio asterisco significa quindi elevamento a potenza).
), rendetegli i permessi di esecuzione e lanciatelo da terminale.