Robitex's Blog

Ideas in the web

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 …

Una risposta a “La ricorsione ed il gioco del Sudoku – Parte 1

  1. Pingback:Sudoku in java Parte 2 « Robitex’s Blog

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: