Robitex's Blog

Ideas in the web

Archivi Mensili: settembre 2009

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 …

La mediateca Carré d’Art


La Carré d’Art

Stranamente non avevo ancora visitato un opera di Sir Norman Foster fino a qualche giorno fà quando mi sono imbattuto nella mediateca/museo Carré d’Art. E come è naturale, vi riporto le mie impressioni.

La mediateca Carré d'Art ed il tempio Maison Carré

La mediateca Carré d'Art ed il tempio Maison Carré

La costruzione ed il sito

La mediateca si trova a Nîmes nel sud della Francia nella bella regione del Gard, e si affaccia sulla piazza della Maison Carré romana.

La foto che vedete testimonia come il nuovo polo culturale si confronti con il tempio romano del I sec. A.C. del tutto ben conservato, non certo con deferenza, ma alla pari: gli steli filiformi verso le colonne corinzie del tempio e un involucro di vetro verso i massicci paramenti murari su tre lati del tempio.

L’architettura

Eppure la mediateca non ha alcun potere evocativo quasi a lasciare libero il campo al visitatore che può così immaginare la storia possente al centro della piazza.

Entrando dalle porte girevoli, si assiste ad un attività incessante di persone che studiano o consultano libri o filmati, osservano l’arte presentata alla mostra o prendono qualcosa al ristorante della terrazza.

Le colonne in calcestruzzo armato dalla maglia regolare e gli impalcati dalle solette continue sono gli elementi evidenti ed essenziali che formano l’edificio. Rimane solo qualche riferimento leggero quasi grafico come quello dei brise soleil delle facciate in vetro, o quello del tepore colorato delle superfici levigate della pietra della gradinata esterna anche questa spesso affollata di giovani, ma niente di più a turbare la scarnezza del linguaggio.

Così, una tecnica moderna che gioca con la luce, accoglie le pensose attività culturali dei suoi indaffarati occupanti e dialoga, osando, con il tempio romano.

L'interno della mediateca

L'interno della mediateca

Alla prossima. Ciao.

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