Robitex's Blog

Ideas in the web

Archivi Categorie: Java

Numeri in lettere


Scarica l’articolo in formato pdf per la stampa

Un problema antico: tradurre numeri in lettere

Molti anni fa acquistai un libro che proponeva una serie di esempi, di esercizi, tutti risolti con il linguaggio Basic.
Nonostante il fatto che quel libro una volta prestato non venne più restituito (ebbene l’interessato/a ovunque esso/a sia, è ancora in tempo per restituire quel libro e, già che c’é, anche gli altri libri di storia dell’arte, grazie), ricordo che verso la fine esso presentava il problema di tradurre un numero in lettere, per esempio, se l’input fosse stato 123 allora l’output del programma avrebbe dovuto essere “centoventitre”.

Soluzione in Java

Malauguratamente il linguaggio Java non è in grado di far “ritrovare” i libri “perduti” ai legittimi lettori (anche se credo che Oracle stia lavorando a funzionalità del genere), ma è comunque in grado di dare soddisfazione a chi volesse tradurre vaghi e primordiali ricordi, in una pagina web di un pugno di bit.

Cominciamo allora con qualcosa di molto più sofisticato di quello che si trovava nel codice Basic di quel libro notando che il numero 123 si può tradurre in lettere in tempi successivi scrivendo prima “cento” e continuando con il numero rimanente 23, scrivendo poi “venti” e continuando ancora con il numero 3, traducendolo in “tre”. Se pensiamo di unire le tre parole avremo ottenuto “centoventitre”.

Se il numero da tradurre in parole fosse invece 6123, dapprima scriveremmo “seimila” e poi ritrovando ancora il numero 123 applicherei la stessa procedura precedente ed alla fine otterrei la sequenza “seimilacentoventitre”.

Adotteremo quindi un approccio ricorsivo per cui elaborata la cifra più significativa si lancia la procedura stessa con il numero restante. Il codice che compare di seguito evita i casi di doppia vocale. Applicando strettamente la procedura ricorsiva, il numero 41 diventerebbe “quarantauno” invece di “quarantuno”. Inoltre, grazie all’overloading dei metodi, il programma è in grado di elaborare numeri decimali traducendoli nel formato letterale previsto per gli importi in euro.

import java.util.Scanner;

public class Traduci {
    // aggiunto il metodo in overloading che fa
    // corrispondere una cifra in euro alla stringa convenzionale
    // es.: 58,45 -> "cinquantotto/45"

    public static void main(String[] args) {
        System.out.print("Digita il numero da tradurre: ");
        Scanner in = new Scanner(System.in);
        if (in.hasNextInt()) {
            System.out.println("in lettere: " +
                               Traduci.NumberToText(in.nextInt()));
        } else if (in.hasNextDouble()) {
            System.out.println("in lettere: " +
                               Traduci.NumberToText(in.nextDouble()));
        } else {
            System.out.println("Errore nei dati immessi.");
        }
    }

    static String NumberToText(int n) {
    // metodo wrapper
        if (n == 0) {
            return "zero";
        } else {
            return NumberToTextRicorsiva(n);
        }
    }
    
    static String NumberToText(double importo) {
        // metodo wrapper
        int n = (int) Math.round(importo * 100);
        int parteIntera = n/100;
        String parteDecimale = String.format("%02d", n%100);

        if (parteIntera == 0) {
            return "zero/" + parteDecimale;
        } else {
            return NumberToTextRicorsiva(parteIntera) + "/" + parteDecimale;
        }
    }

    private static String NumberToTextRicorsiva(int n) {
        if (n < 0) {
            return "meno " + NumberToTextRicorsiva(-n);
        } else if (n == 0){
            return "";
        } else if (n <= 19){
            return new String[] { "uno", "due", "tre", "quattro", "cinque", 
                                  "sei", "sette", "otto", "nove", "dieci", 
                                  "undici", "dodici", "tredici", 
                                  "quattordici", "quindici", "sedici", 
                                  "diciassette", "diciotto", "diciannove" }[n-1];
        } else if (n <= 99) {
            String[] vettore = 
            { "venti", "trenta", "quaranta", "cinquanta", "sessanta", 
              "settanta", "ottanta", "novanta" };
            String letter = vettore[n / 10 - 2];
            int t = n % 10; // t è la prima cifra di n
            // se è 1 o 8 va tolta la vocale finale di letter
            if (t == 1 || t == 8 ) {
                letter = letter.substring(0, letter.length() - 1);
            }
            return letter + NumberToTextRicorsiva(n % 10);
        } else if (n <= 199){
            return "cento" + NumberToTextRicorsiva(n % 100);
        } else if (n <= 999){
            int m = n % 100;
            m /= 10; // divisione intera per 10 della variabile
            String letter = "cent";
            if (m != 8){
              letter = letter + "o";
            }
            return NumberToTextRicorsiva(n / 100) + letter + 
                NumberToTextRicorsiva(n % 100);
        }
        else if (n <= 1999){
            return "mille" + NumberToTextRicorsiva(n % 1000);
        }  else if (n <= 999999){
            return NumberToTextRicorsiva(n / 1000) + "mila" + 
                NumberToTextRicorsiva(n % 1000);
        }
        else if (n <= 1999999){
            return "unmilione" + NumberToTextRicorsiva(n % 1000000);
        } else if (n <= 999999999){
            return NumberToTextRicorsiva(n / 1000000) + "milioni" + 
                NumberToTextRicorsiva(n % 1000000);
        } else if (n <= 1999999999){
            return "unmiliardo" + NumberToTextRicorsiva(n % 1000000000);
        } else {
            return NumberToTextRicorsiva(n / 1000000000) + "miliardi" + 
                NumberToTextRicorsiva(n % 1000000000);
        }
    }
}

Una volta inserito il codice in un file di testo chiamato “Traduci.java”, procedete alla sua compilazione utilizzando uno JDK 5.0 o successivo con il comando (installate eventualmente da voi un JDK scelto tra le varie alternative):

javac Traduci.java

Per lanciare il programma che consiste nel file contenente il bytecode per la macchina virtuale Java ed ha per estensione .class, date il comando:

java Traduci

ed inserite il numero intero o decimale da tradurre in parole. Nell’immagine seguente potete consultare la sessione di compilazione ed esecuzione.

The compile session of the java program

The compile session of the java program

Soluzione in Lua

Vogliamo adesso scrivere lo stesso programma in Lua, non tanto per confrontarlo con la versione Java, quanto per predisporne l’uso con LuaTeX. Il codice in Lua è molto meno strutturato di quello in Java e ha un sapore, diciamo così, più artigianale ma è più semplice, eccolo:

#!/usr/bin/lua

-- script di traduzione di numeri in lettere
-- nella lingua italiana
-- traduce un numero in lettere

-- funzione ricorsiva
local function NumberToTextRicorsiva(n)
    if n < 0 then 
        return "meno " .. NumberToTextRicorsiva(-n)
    elseif n == 0 then
        return ""
    elseif n <= 19 then
        local ventina = { "uno", "due", "tre", "quattro", "cinque", 
                          "sei", "sette", "otto", "nove", "dieci", 
                          "undici", "dodici", "tredici", 
                          "quattordici", "quindici", "sedici", 
                          "diciassette", "diciotto", "diciannove" }
        return ventina[n]

    elseif n <= 99 then
        local decine = { "venti", "trenta", "quaranta",
                         "cinquanta", "sessanta", 
                         "settanta", "ottanta", "novanta" }
        local letter = decine[math.floor(n/10)-1]
        local t = n % 10
        if t == 1 or t == 8 then
            letter = string.sub(letter,1,-2)
        end
        return letter .. NumberToTextRicorsiva(n % 10)
    elseif n <= 199 then
        return "cento" .. NumberToTextRicorsiva(n % 100)
    elseif n <= 999 then
        local m = n % 100
        m = math.floor(m/10)
        local letter = "cent"
        if m ~= 8 then
           letter = letter .. "o"
        end
        return NumberToTextRicorsiva( math.floor(n / 100)) ..
               letter ..
               NumberToTextRicorsiva(n % 100)
        elseif n<= 1999 then
            return "mille" .. NumberToTextRicorsiva(n % 1000)
        elseif n<= 999999 then
            return NumberToTextRicorsiva(math.floor(n / 1000)) ..
                   "mila" ..
                   NumberToTextRicorsiva(n % 1000)
        elseif n <= 1999999 then
            return "unmilione" .. NumberToTextRicorsiva(n % 1000000)
        elseif n <= 999999999 then
            return NumberToTextRicorsiva(math.floor(n / 1000000))..
                   "milioni" ..
                   NumberToTextRicorsiva(n % 1000000)
        elseif n <= 1999999999 then
            return "unmiliardo" .. NumberToTextRicorsiva(n % 1000000000)
        else return NumberToTextRicorsiva(math.floor(n / 1000000000)) ..
                    "miliardi" ..
                    NumberToTextRicorsiva(n % 1000000000)
    end
end

-- funzione wrapper
local function NumberToText(n)
   if n == 0 then
     return "zero"
  else
     return NumberToTextRicorsiva(n)
  end
end

-- prelevo il valore numerico come argomento dello script
local num = arg[1]

-- gestisco il caso di numero con decimali
local dec = num - math.floor(num)
local tail = ""

if dec ~= 0 then
   dec = dec * 100
   tail = "/" .. string.format("%.0f",dec)
end

print("in lettere: ".. NumberToText(math.floor(num))..tail)

Soluzione in LuaTeX

Adesso vediamo come incorporare il programma in un documento LuaTeX, ovvero in un file di testo che passato come argomento al motore di composizione tipografica LuaTeX, produce un file pdf con il contenuto voluto.

Come per gli altri motori tipografici della famiglia TeX, anche in LuaTeX il testo viene direttamente composto nel documento a meno che non sia preceduto dal carattere di backslash: “\”. Questo particolare carattere viene interpretato come simbolo di escape nei confronti del testo che lo segue. Così se TeX incontra il testo:

Il numero 123456789 in lettere viene scritto come \traduci{123456789}.

allora inserirà nel documento finale tutti i caratteri tranne per \traduci che viene inteso invece come una macro. Questo è il succo di uno dei linguaggi tipografici più noti al mondo.

Dunque basterà associare la corretta definizione della macro \traduci per veder comparire automaticamente nel pdf il numero tradotto in lettere scritto tra parentesi graffe con il significato di argomento. Il codice Lua deve essere leggermente modificato, primo perché l’operatore modulo corrisponde al carattere di commento di TeX per cui lo esprimeremo in termini matematici (si tratta del resto della divisione intera). Secondo, dobbiamo trasformare i simboli di commento Lua nel simbolo di commento TeX e terzo, occorre premettere al simbolo di tilde che compare nell’operatore di disuguaglianza la macro primitiva \string per evitare che venga interpretato diversamente. Ecco il sorgente LuaTeX per intero:

\directlua{
function mod(n,d)
   return n-d*math.floor(n/d)
end
}

\def\traduci#1{%
\directlua{
local function NumberToTextRicorsiva(n)
    if n < 0 then 
        return "meno " .. NumberToTextRicorsiva(-n)
    elseif n == 0 then
        return ""
    elseif n <= 19 then
        local ventina = { "uno", "due", "tre", "quattro", "cinque", 
                          "sei", "sette", "otto", "nove", "dieci", 
                          "undici", "dodici", "tredici", 
                          "quattordici", "quindici", "sedici", 
                          "diciassette", "diciotto", "diciannove" }
        return ventina[n]
    elseif n <= 99 then
        local decine = { "venti", "trenta", "quaranta",
                         "cinquanta", "sessanta", 
                         "settanta", "ottanta", "novanta" }
        local letter = decine[math.floor(n/10)-1]
        local t = mod(n, 10)
        if t == 1 or t == 8 then
            letter = string.sub(letter,1,-2)
        end
        return letter .. NumberToTextRicorsiva(mod(n,10))
    elseif n <= 199 then
        return "cento" .. NumberToTextRicorsiva(mod(n,100))
    elseif n <= 999 then
        local m = mod(n,100)
        m = math.floor(m/10)
        local letter = "cent"
        if m \string~= 8 then
           letter = letter .. "o"
        end
        return NumberToTextRicorsiva( math.floor(n / 100)) ..
               letter ..
               NumberToTextRicorsiva(mod(n,100))
        elseif n<= 1999 then
            return "mille" .. NumberToTextRicorsiva(mod(n,1000))
        elseif n<= 999999 then
            return NumberToTextRicorsiva(math.floor(n / 1000)) ..
                   "mila" ..
                   NumberToTextRicorsiva(mod(n,1000))
        elseif n <= 1999999 then
            return "unmilione" .. NumberToTextRicorsiva(mod(n,1000000))
        elseif n <= 999999999 then
            return NumberToTextRicorsiva(math.floor(n / 1000000))..
                   "milioni" ..
                   NumberToTextRicorsiva(mod(n,1000000))
        elseif n <= 1999999999 then
            return "unmiliardo" .. NumberToTextRicorsiva(mod(n,1000000000))
        else return NumberToTextRicorsiva(math.floor(n / 1000000000)) ..
                    "miliardi" ..
                    NumberToTextRicorsiva(mod(n,1000000000))
    end
end

% funzione wrapper
local function NumberToText(n)
   if n == 0 then
     return "zero"
  else
     return NumberToTextRicorsiva(n)
  end
end

% prelevo il valore numerico come argomento dello script
local num = #1

% gestisco il caso di numero con decimali
local dec = num - math.floor(num)
local tail = ""

if dec \string~= 0 then
   dec = dec * 100
   tail = "/" .. string.format("\%.0f",dec)
end
tex.sprint(NumberToText(math.floor(num))..tail)
}}

Il numero 123456789 in lettere viene scritto come \traduci{123456789}.

Ciao
\bye

Compilatelo dopo averlo inserito in un file chiamato trad.tex e compilatelo con il comando da console: luatex trad (occorre che una distribuzione recente del sistema TeX sia installata sul vostro sistema, per esempio TeX Live).

Se volete potete scaricare da questo link il pdf risultato.

Come breve riferimento, posso aggiungere che nel codice LuaTeX la definizione della macro \traduci si avvale della nuova primitiva \directlua che esegue codice Lua, in cui si possono elaborare argomenti rappresentati con il simbolo #1 (per il primo di essi), proprio come un normalissimo sorgente TeX. Inoltre, la funzione di sostituzione dell’operatore modulo viene caricata in memoria in una prima macro \directlua dimostrando come in LuaTeX le varie porzioni di codice distribuite tra le varie \directlua del sorgente, condividono lo spazio delle variabili globali.

Ci tengo a precisare che l’operazione di traduzione di numeri in lettere è già stata brillantemente risolta per la lingua italiana dal Prof. Enrico Gregorio con il suo pacchetto itnumpar utilizzando esclusivamente codice TeX. Questo pacchetto tiene conto degli accenti delle parole delle cifre e della eventuale necessità dell’iniziale maiuscola. Esso è stato scritto per l’elaborazione dei titoli di capitolo per esempio per far uscire il testo “Capitolo Diciotto” anziché del solito “Capitolo 18”.

Bene. Ho terminato questo post ricco di codice. Come sempre sono aperti i commenti per aggiungere, segnalare o fare domande. Alla prossima.
Ciao.

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.

La ricorsione ed il gioco del Sudoku – Parte 1


Il mio Sudoku

Nel 2005 esplose sulla scena un gioco logico, il Sudoku. Caduto anch’io in quella griglia 9×9, mi dedicai a scrivere un programma in C# (il linguaggio re della piattaforma .NET di Microsoft) per la risoluzione degli schemi utilizzando la tecnica della ricorsione. Il risultato fu pubblicato in due post nel sito dei blogger dello User Group Italiano dot NET, ma qualche mese dopo il sito fu attaccato con una qualche tecnica ed il database fu danneggiato con la conseguente perdita irreparabile non solo dei miei post, ma anche dei commenti provenienti dal Giappone (ovviamente non ho la minima idea di cosa dicessero), dalla Polonia, ecc.

Mi sembra proprio il caso di riproporlo quì, questa volta in versione Java, più brillante che mai…

Il gioco e l’idea della ricorsione: il post originale

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 (metodo 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 è Java. 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):

// 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();
boolean[] 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;
}

Prossimamente pubblicherò il listato completo con qualche modifica: a presto… bye …

%d blogger hanno fatto clic su Mi Piace per questo: