Volete la versione corta o la versione lunga di questo post? Se conoscete già il gioco del Sodoku, potete optare per la versione corta e saltare a questa pagina: www.dotnet2themax.it/sodoku/default.aspx. Altrimenti continuate a leggere.

È probabile che molti di voi conoscano il gioco del Sodoku o abbiano già provato a risolvere uno dei problemi che appaiono ogni giorno su La Repubblica o Il Corriere della Sera. Se invece non ne avete mai sentito parlare, potete leggere le regole e trovare qualche problema di esempio in questa pagina.

Riassumendo, si tratta di un gioco di abilità e pazienza, basato su una griglia di 81 caselle, suddivisa in 9 righe, 9 colonne e 9 sottosezioni di 3x3. Le regole del gioco sono semplicissime: ogni casella può contenere una cifra da 1 a 9, e ogni riga, colonna o sottosezione deve contenere tutte le cifre 1-9, senza alcuna cifra mancante o ripetizione. Un problema di Sodoku consiste in una griglia riempita solo parzialmente, dove il risolutore deve ovviamente riempire le celle vuote in modo che le regole siano rispettate. A seconda del numero e del contenuto delle celle riempite inizialmente il gioco può avere una sola soluzione, oppure più d'una. Ecco ad esempio l'unica soluzione del gioco apparso sulla Repubblica del 25 Giugno:

    +---+---+---+
    |635|247|189|
    |817|935|624|
    |294|186|537|
    +---+---+---+
    |352|869|471|
    |971|524|863|
    |468|371|952|
    +---+---+---+
    |749|653|218|
    |583|412|796|
    |126|798|345|
    +---+---+---+

Il gioco del Sodoku ha spopolato in Giappone, ma anche nel resto del mondo sembra che stia partendo una vera e propria mania del Sodoku, paragonabile forse a quella che anni fa impazzava per il Cubo di Rubik. Sul sito del Corriere è anche disponibile un forum per gli appassionati di Sodoku e recentemente è anche dovuto intervenire il grande Stefano Bartezzaghi per chiarire qualche aspetto del gioco relativo alla unicità delle risposte.

Devo essere sincero: nonostante tutta questa febbre collettiva, non credo che il Sodoku sia poi così interessante. Alla fine si tratta di stabilire una strategia per provare le varie mosse a disposizione nelle celle e continuare così fino a quando non si cade in contraddizione (non vi sono valori disponibili per una cella) oppure si trova una soluzione. Insomma, alla fine tutti i problemi Sodoku si assomigliano e cambia solo il tempo necessario per risolverli. Non mi stupisce che il gioco stia conoscendo un periodo fortunato proprio in estate, quando la gente non sa bene cosa fare sotto l'ombrellone

Facevo queste riflessioni, mentre mi prendevo una pausa dopo aver completato il capitolo 15 del mio librone su Visual Basic 2005. Un programma per risolvere uno schema di Sodoku non è difficile da scrivere: basta applicare le solite tecniche di esplorazione di un albero di soluzioni e di backtracking quando si arriva a una contraddizione. Questo dovrebbe provare tra l'altro che non sono richieste particolari doti di intuizione o esperienza: insomma, niente di paragonabile non dico a dama e scacchi, ma neanche semplicemente a un solitario con le carte.

Per farla breve, mi sono armato di Visual Basic 2003 e dopo un paio di ore avevo il mio bel Sodoku Solver funzionante! Non è stato neanche necessario ricorrere a chissà quali tecniche di ottimizzazione, dato che sul mio Pentium 4 il programma risolve un problema con oltre 100mila soluzioni (e le elenca tutte!) in meno di una decina di secondi! Il passo successivo è stato creare una versione Web, che possa essere giocabile da chiunque senza dover installare tutto il .NET Framework. La potete trovare su questo sito a questo indirizzo: www.dotnet2themax.it/sodoku/default.aspx.

La cosa interessante è che il programma mostra non soltanto le soluzioni ma descrive anche la strategia adottata per arrivare al risultato. In questo modo il programma può funzionare anche come strumento didattico per insegnare a risolvere il Sodoku con carta e penna. Sulla pagina troverete anche qualche problema di esempio. Si può usare il programma anche per creare nuovi problemi: basta inserire un po' di celle a casaccio e cliccare sul pulsante "Risolvi", aggiungendo caselle fino a quando non si arriva ad una soluzione unica, oppure svuotandone qualcuna se il programma indica che lo schema corrente non porta ad alcuna soluzione.

La strategia che applica il programma è così semplice da poter essere riassunta in poche righe, almeno per chi è pratico degli algoritmi di backtracking:

1. Partendo dalla griglia corrente, si riempiono tutte le caselle obbligate, dove una "casella obbligata" è quella per cui non esistono alternative in quanto vi è solo una cifra nell'intervallo 1-9 che NON appare nella riga, colonna e sottosezione a cui la cella appartiene.
2. Si esplorano tutte le celle libere, tenendo traccia di quante mosse alternative vi sono per ciascuna di esse.
3. Si sceglie la cella con il numero minimo di alternative (di solito vi sono molte celle con due sole alternative) e si ipotizza di assegnare la prima di queste alternative alla cella. Quando questo accade si dice che si sta passando al livello di ipotesi successivo (N+1), si ottiene un nuovo schema e si ripete il ciclo dal passo 1.
4. se l'ipotesi corrente porta a una contraddizione, ossia porta a una situazione in cui non vi è alcuna alternativa valida per una delle celle libere, allora evidentemente l'ipotesi al livello corrente non è corretta: occorre tornare al livello precedente (N-1) e provare un'altra mossa per la cella scelta al passo 3.

OK, questo è tutto. Se siete interessati ad altri dettagli sul gioco o del mio programma , lasciate pure un commento.