Il Sudoku

Bene, anche io sono stato preso da una piccola "febbre da Sudoku", ovviamente la mia è una febbre da informatico...
Quindi mi sono buttato a capofitto nella creazione di un programmino Excel, che risolvesse da solo anche i Sudoku più complicati.
Per farlo, ovviamente, ho dovuto pensare ad alcune semplici regolette di risoluzione, quindi mi sono detto: perchè non pubblicarle?

Ecco fatto !

Il Sudoku si compone di una tabella, di solito composta di 9x9 caselle, a sua volta divisa in 9 quadrati (che chiamerò "box") di dimensione 3x3 caselle.
Ci sono in giro anche versioni di 16x16 caselle, suddivise in 16 box da 4x4 caselle ...
Lo scopo del sudoku è semplicissimo: bisogna riempirlo di numeri (ma andrebbero bene anche simboli a caso). Quanti numeri ? La risposta è semplice: tanti quanto è la dimensione del sudoku.
Quindi se lo schema è un 9x9, con 9 box da 3x3, dovrò posizionare 9 simboli diversi, di solito le cifre dall'1 al 9... Se fosse lo schema da 16x16, che è diviso in box da 4x4, dovrò posizionare 16 simboli diversi (o i numeri da 1 a 16, che facciamo prima)
E COME vanno posizionati? Semplice ! L'unica regola è questa: ogni riga, ogni colonna e ogni box dello schema deve contenere TUTTI i numeri, ma ognuno deve essere ripetuto UNA VOLTA SOLA.
Una volta sola in ogni riga, una volta sola in ogni colonna e una volta sola in ogni box, tanto per essere chiari !
Normalmente nello schema sono già messi alcuni numeri, e sono cavoli nostri completare lo schema.

Vi tranquillizzo subito: nonostante quello che leggerete in giro il sudoku è di una semplicità disarmante, e la sua soluzione si trova semplicemente applicando una serie di ragionamenti standard, uno di seguito all'altro, finchè ci si trova due casi: o si è risolto, o si deve METTERE UN NUMERO A CASO, e proseguire.

Vediamo ora cosa serve per risolvere uno schema di sudoku:

• Matita, facile da cancellare
• gomma
• biro
• pazienza
• tempo libero

La prima cosa da fare e applicare un semplice metodo che io chiamo "GIRI" (giro dell'1, giro del 2 .. ecc..)

E' semplicissimo, guardate la figura sopra, guardate i tre box 3x3, a destra, e controllate il numero 6.
Nel primo box è nella colonna a sinistra, nel secondo box è in quella a destra, dunque nel terzo box il 6 può stare solo nella colonna centrale !
Se in quella colonna, nel terzo box, ci fosse stata solo una posizione libera, avrei potuto scriverlo subito.
Visto che non è così, niente panico.... basta vedere che a sinistra, nella riga centrale, c'è un altro 6, quindi il 6 può stare solo nella cella gialla !
Questo metodo va ripetuto, partendo dall'1, per tutti i numeri, e poi ricominciato, e ripetuto, fino a che si fanno tutti i 9 "GIRI" senza mettere più numeri nella giusta posizione. A questo punto, si passa ai prossimi metodi:

Il trucco è ragionare sulla lista dei numeri che sono permessi in ogni singola cella dello schema, cancellandoli via via che il ragionamento vi fa capire che in quella celletta quel particolare numero non ci può stare, finchè, per ogni cella, avrete messo l'UNICO numero che ci va bene.
Eh, lo so, detto così sembra facile... ma vi assicuro che lo è davvero:
Guardate, ora, la figura sotto:(scusate se cambio l'esempio, ma questo ce l'avevo pronto...)

Vedete la celletta gialla? Allora, abbiamo detto che per ogni riga, per ogni colonna e per ogni box i numeri devono ripetersi UNA VOLTA SOLA....
Nel box ci sono già il 2, il 4, il 5 ed il 9.
Nella riga della celletta gialla ci sono già il 3, il 4, il 5 ed il 7.
Nella colonna ci sono già il 3, il 4, il 7 ed il 9.
Allora nella celletta gialla ci possono stare solo 1 o 6 o 8 ! Li scriviamo a matita, così da poter poi modificare la cella quando scopriremo altri numeri che sono vietati per quella cella, e quindi affineremo l'elenco dei numeri permessi...
Vediamo ora la celletta verde... Con lo stesso metodo scopriamo che lì dentro ci può stare SOLO il 6, perchè TUTTI gli altri numeri sono già nella stessa riga, nella stessa colonna o nello stesso box della celletta verde.
Allora scriviamo il 6. Ed ORA che l'abbiamo scritto, lo TOGLIAMO dalle possibilità delle altre celle, quindi, per esempio, la celletta gialla, in cui prima avevamo scritto 1,6,8 come numeri possibili, ora diventa 1,8 e BASTA, perchè il 6 -a questo punto - sta già nella riga (ed anche nel box) a cui appartiene la celletta gialla.
Dopo che abbiamo ripetuto questo ragionamento, che possiamo chiamare "SINGOLI AMMESSI", ci troveremo come nella figura che segue:

Ora si va a caccia di "COPPIE UGUALI": vedete la coppia 1,8 nelle celle gialle? Bene, lo vedete anche voi che stanno sulla stessa colonna, e per di più nello stesso box.
Questo vuol dire PER FORZA che in una cella gialla ci sta 1 e nell'altra PER FORZA 8. Non ci interessa ora in quale sia davvero l'1 o l'8, quello che ci interessa è che se 1 e 8 stanno per forza in una delle celle gialle, allora nel resto del box e nel resto della colonna (perchè sono nella stessa colonna), 1 e 8 NON CI POSSONO STARE, quindi li tolgo dall'elenco delle possibilità per le celle NON GIALLE che stanno nello stesso box e nella stessa colonna delle celle gialle.
Questo crea tutta una serie di mosse concatenate! Intanto vediamo subito che nelle celle verdi, se tolgo l'8, si crea un'altra COPPIA UGUALE: 3,7 che sta sulla stessa riga e nello stesso box. Nel box purtroppo non si semplifica nulla, perchè altri 3 o 7 non ce n'erano più, ma lungo la riga, nelle celle NON VERDI, posso togliere tutti i 3 ed i 7, perchè non ci possono stare, in quanto DEVONO STARE NELLE CELLE VERDI !
Poi vedete in cima alla colonna delle celle gialle ? La prima cella è 6,8 e la seconda è 5,6,8 ed io so che l'8 non ci può stare, quindi lo tolgo dalle possibilità, allora nella prima in alto finisce che ci può stare SOLO IL 6 !!
Ma fissando il 6 in quella cella, automaticamente posso togliere il 6 dalle possibilità per tutte le altre celle di quella riga, di quella colonna e di quel box ! Quindi nella cella che era 5,6,8 e l'8 l'avevo tolto prima, togliendo anche il 6, capisco che lì ci può stare SOLO il 5 !!
Fissando il 5 in quella cella, capisco che nella penultima cella in fondo a quella colonna, che era 2,5 a questo punto ci può stare solo il 2 !!
Dopo avere fatto tutte queste semplificazioni (togliere il 6, 5 e 2 dalle righe, colonne e box, dopo che li ho fissati in una posizione certa) arrivo alla situazione che si vede sotto:

Guardiamo ora la cella gialla: vedete che contiene il 6 ? Vedete che il 6 non compare nelle possibilità di NESSUN'ALTRA cella in tutta la riga?? (N.B. il 6 non compare nemmeno in nessun'altra cella di tutto il box)
Di queste due condizioni, che io chiamo "MONO-POSIZIONE", ne basta anche solo una, per concludere che il 6 può stare SOLO LI' !! Ovviamente valeva anche se quella cella fosse stata l'unica della COLONNA a contenere il 6. E siamo quindi arrivati qui:

Vedete le solite celle gialle ? Sono TRE, e i numeri possibili per quelle celle SONO SOLO TRE, abbiamo la situazione "TRExTRE".
E non badate al fatto che, per caso, le tre celle siano uguali, il ragionamento si applica a TRE CELLE ALLINEATE (riga o colonna) in cui vi possano stare SOLO TRE NUMERI. Per capirci andava bene lo stesso se le tre celle fossero state 2,8 / 8,9 / 2,9 oppure anche 2,8,9 / 8,9 / 2,8 ... sono TRE celle e ci possono stare SOLO TRE numeri.
Quindi quei tre numeri li tolgo dalle possibilità di tutte le ALTRE celle della riga o della colonna (valeva anche per il box, se le tre celle fossero state NON allineate, ma dentro lo stesso box, potevo semplificare il resto del box, ma questo si verifica di rado)

Ricapitolando abbiamo 4 metodi di semplificazione:

1. SINGOLI AMMESSI
2. MONO-POSIZIONE
3. COPPIE UGUALI
4. TRExTRE

Questi metodi si possono applicare quante volte si vuole, finchè ci si troverà in uno dei seguenti due casi: o avete risolto il gioco, o non potete più applicare nessuno dei 4 metodi.
(NOTA: Ovviamente il metodo TRExTRE si può generalizzare anche al caso in cui in 4 o 5 celle allineate ci possano stare SOLO 4 o 5 numeri, ovviamente in tale caso posso semplificare quei numeri dalle altre celle della riga o colonna. Per un sudoku 9x9 è abbastanza difficile che possa capitare, mentre per un sudoku 16x16, è più probabile)

Se non avete ancora risolto il sudoku rimane il 5° metodo: "SCOMMESSA"
Anche questo è semplice: prima di procedere scrivete con la biro tutti i numeri di cui avete finora individuato la posizione, e cancellate con la gomma tutti i numeri non possibili in ogni cella, in modo da non avere cancellature con tratti di matita. Questa è la situazione di partenza per la SCOMMESSA.
Ora prendete una COPPIA UGUALE (se ce ne sono, altrimenti va bene anche una cella con solo due numeri possibili) e mettete i due numeri a caso. (O uno dei due numeri a caso, se non avevate coppie).
A questo punto ricominciate ad usare i 4 metodi visti prima, finchè arriverete ad uno di questi tre casi:

• Risolto
• Impossibile
• Non risolto, Non impossibile, i 4 metodi non si possono più applicare

Impossibile vuol dire che per una certa cella NON ci sono numeri permessi.
Se IMPOSSIBILE: dovete tornare indietro e invertire l'ultima scommessa fatta (se avevate messo, per esempio 3 in una cella e 5 in un'altra, dovete invertire questa scelta; se avevate messo UN numero a caso da una cella con due numeri possibili: mettete l'altro). Purtroppo dovete annullare tutte le operazioni di semplificazione che avevate fatto per effetto della scommessa.
Mettete i nuovi numeri, e ricominciate con i 4 metodi.
Se invece siete arrivati al caso 3 dovete solo fare un'altra scommessa.... e ricominciare con i 4 metodi.

Lo so, scommettere in questo modo sembra complicato, e forse lo è, ma io lo trovo più facile che applicare un eventuale altro metodo, che sicuramente esisterà, ma che sarà complicato almeno quanto tirare a caso e proseguire... Questo ovviamente secondo la mia umile opinione...

Ecco un programma, fatto con Visual Basic 6.0, per risolvere i Sudoku

SUDOKU SOLVER (C) Eugy 2005 [V 1.1]

Rispetto alla versione 1.0 ho aggiunto una procedura NON ricorsiva di attacco "a forza bruta", essa si attiva quando è il caso, chiedendovi se partire.
Il 99,99 % dei sudoku che troverete in giro, ovunque essi siano, NON richiedono l'attacco a forza bruta.
Il programma tenta prima con la logica, e se non risolve vi chiede se proseguire a "FORZA BRUTA" o "TIRANDO A CASO".
Ripeto: se avete preso il sudoku da qualche parte, se non si risolve con la sola logica, e quindi arrivate a questa scelta, è sufficiente "tirare a caso".
La Forza Bruta, non è ancora perfezionata, se usata con uno schema 9x9 funziona benissimo, ma se chiamata con un sudoku 16x16, con pochi (ma non pochissimi) numeri, rischia di inchiodarsi senza arrivare ad una soluzione.
Non c'è problema: sotto il menù FILE resta attivo il comando ESCI, che interrompe il programma.

Poichè errori od imprecisioni sono sempre in agguato... se qualcuno notasse qualcosa di sbagliato, per favore, USATE IL MODULO DI CONTATTO (nel menù in alto)
Fate la stessa cosa se fossi stato poco chiaro, e volete ulteriori chiarimenti su questo argomento, ricordandovi di mettere anche la vostra e-mail, affinchè io possa rispondervi