[HOME - BASE Cinque - Appunti di Matematica ricreativa]

Sudoku informazioni

Il tormentone dell'estate 2005

Nota Bene: questa pagina è aggiornata spesso, perciò quello che trovate ora magari è un po' diverso da quello che c'era una settimana fa...

Grazie a Marco Cagnazzo per avermi segnalato il Sudoku (o Su-Doku), un gioco molto diffuso in Giappone.
Paola de Carolis, nel Corriere della Sera del 22 maggio 2005, lo definisce il nuovo gioco-mania d'Europa e dichiara che in Gran Bretagna ha conquistato milioni di persone. E in Italia arriva anche un mensile intitolato Logic Art. In futuro potrebbe sbarcare sui cellulari. Per capire di cosa si tratta, proviamo a risolverne uno.

Il metodo che presento qui è a cancellazioni successive. E' facile da capire ma non è sempre efficace ed efficiente.
Se vi interessa un metodo molto più furbo, visitate la pagina Sudoku Zen.

Primo passaggio
Un primo possibile passaggio per risolvere il Sudoku potrebbe essere quello di scrivere in ogni quadretto TUTTI i numeri ammessi, dopo aver eliminato dalle nove cifre quelle già presenti nella riga, nella colonna e nella regione 3x3 a cui il quadretto appartiene.

Secondo passaggio
Il passaggio successivo consiste nell'esaminare attentamente la tabella alla ricerca di scelte obbligate.

Ad esempio:

• nella riga A, la cifra 1 compare solo in A1; si scrive 1 in A1 e si cancella la cifra 1 nelle corrispondenti colonna, riga e regione.
• nella riga E, la cifra 3 compare solo in E2; si scrive 3 in E2 e si cancella la cifra 3 nelle corrispondenti colonna, riga e regione.
• la regione GHI-123 contiene la cifra 3 solo in H3; scrive 3 in H3 e si cancella la cifra 3 nelle corrispondenti colonna, riga e regione.
• nella riga I, la cifra 3 compare solo in I9; si scrive 3 in I9 e si cancella la cifra 3 nelle corrispondenti colonna, riga e regione.
• e così via...

Procedendo per esclusioni successive si arriva alla soluzione finale, che è:

1 6 9 | 4 2 3 | 7 5 8
2 4 8 | 5 7 9 | 3 1 6
3 7 5 | 8 1 6 | 4 9 2
- - - + - - - + - - -
9 1 4 | 3 6 8 | 2 7 5
6 3 2 | 7 5 1 | 8 4 9
8 5 7 | 9 4 2 | 6 3 1
- - - + - - - + - - -
7 2 1 | 6 3 5 | 9 8 4
5 8 3 | 2 9 4 | 1 6 7
4 9 6 | 1 8 7 | 5 2 3

Ecco un Sudoku un po' più difficile

Sudoku n 23
pubblicato su The Guardian,
2 giugno 2005

Se devo essere sincero, ho qualche difficoltà a trovare il Sudoku interessante dal punto di vista matematico. Mi sembra soltanto un rompicapo da affrontare con strategie fisse.
Per fortuna mi rimanda ai Quadrati Latini e Greco-latini studiati dal grande matematico Euler.

Ho anche qualche altra domanda:

• Come si può fare per costruire un Sudoku partendo da un foglio bianco?
• I Sudoku possibili sono un numero finito: quanti?
• Quali sono le condizioni affinché un Sudoku iniziato possa andare a buon fine?
• E abbia una sola soluzione?
• Esistono software per creare e/o risolvere Sudoku?
  Troverete un solutore automatico didattico nella pagina: Risolutore di Sudoku.
  Troverete invece un analizzatore professionale nella pagina: Analizzatore automatico di Sudoku

Number place, il papà del Sudoku
La società Nikoli, che ha brevettato il Sudoku in Giappone, dichiara di essersi ispirata, nel lontano 1984, ad un gioco chiamato Number place, pubblicato negli Stati Uniti dall'editrice Dell.
Il primo nome giapponese del Sudoku era "Suuji wa dokushin ni kagiru". Significa che i numeri da scrivere in ogni casella sono single, cioè scapoli. Ma questo nome era troppo lungo, perciò fu abbreviato in Sudoku. "Su" significa numero e "Doku" significa solitario.
Il Sudoku all'inizio non era popolare. Il suo successo cominciò nel 1986, quando la Nikoli introdusse una nuova regola non presente nel Number place: i numeri di partenza dovevano esser disposti in uno schema simmetrico.

Un esempio di Number place pubblicato da Dell nel febbraio 1998.
Non è difficile risolverlo perché ci sono ben 36 numeri.
E' evidente che la loro disposizione non è simmetrica.

Ma quanti sono i Sudoku?
Bertram Felgenhauer, Frazer Jarvis e, indipendentemente da loro, Ed Russell, hanno stabilito che l'universo di tutti i possibili Sudoku avrebbe 6.670.903.752.021.072.936.960 abitanti.
Più di 6.670 miliardi di miliardi! Un numero inconcepibile.
Se scrivessimo tutti questi puzzles su dei foglietti da 7x7 cm potremmo coprire una superficie di 32.687.428.384.903.257.391.104 km², circa 113.000 volte la superficie della Terra.
Se un computer ne risolvesse 1.000 al secondo impiegherebbe 211 miliardi di anni per risolverli tutti. E pensare che l'Universo è nato "soltanto" 15 miliardi di anni fa.
Se però i Sudoku fossero piccoli come un atomo di sodio, allora occuperebbero lo spazio di una manciata di sale da cucina.

Sudoku record
Il più piccolo numero di numeri di partenza di un Sudoku è 20.
Invece, se la disposizione iniziale non è simmetrica, come nel Number place, il record è 18.
Ecco, ad esempio, un Sudoku da 21 numeri.

E qui sotto due Sudoku da 20 numeri.

+-----+-----+-----+
|7 - -|- - -|- - 3|
|- 2 -|8 - -|- - -|
|- - 9|- 6 -|1 - -|
+-----+-----+-----+
|- - -|- - 3|- 9 -|
|4 - -|- - -|- - 6|
|- 1 -|7 - -|- - -|
+-----+-----+-----+
|- - 3|- 5 -|8 - -|
|- - -|- - 2|- 1 -|
|8 - -|- - -|- - 7|
+-----+-----+-----+

+-----+-----+-----+
|7 4 -|- - -|- 2 -|
|- - -|- 9 -|- - 1|
|- - 8|- - 3|- - -|
+-----+-----+-----+
|- - -|7 - -|8 - -|
|- 1 -|- - -|- 4 -|
|- - 3|- - 2|- - -|
+-----+-----+-----+
|- - -|8 - -|3 - -|
|1 - -|- 5 -|- - -|
|- 9 -|- - -|- 7 2|
+-----+-----+-----+

+-----+-----+-----+
|- - 5|- - -|- 4 -|
|- - -|8 - -|- - 6|
|3 - 2|- - 1|- - -|
+-----+-----+-----+
|- - -|- - 4|- 2 -|
|- - 9|- - -|5 - -|
|- 6 -|3 - -|- - -|
+-----+-----+-----+
|- - -|- - -|- - 3|
|- - -|- - 5|- - -|
|- 1 -|- - -|6 8 -|
+-----+-----+-----+

+-----+-----+-----+
|- - 5|- - -|- - -|
|- - -|8 - -|- 1 6|
|3 - 2|- - 9|- - -|
+-----+-----+-----+
|- - -|- - 4|- 2 -|
|- - 9|- - -|5 - -|
|- 6 -|3 - -|- - -|
+-----+-----+-----+
|- - -|- - -|- - 3|
|- - -|- - 5|- - -|
|- - -|- - -|6 8 -|
+-----+-----+-----+

Sudoku e computer
"Per risolvere un Sudoku non serve la matematica ma una buona dose di logica laterale."
A mio parere, questi sono due luoghi comuni piuttosto preoccupanti.
E' vero, per risolvere un Sudoku non è necessario eseguire calcoli numerici, ma la matematica non si esaurisce nelle quattro operazioni. Il Sudoku è un classico problema le cui soluzioni devono essere cercate fra un numero più o meno elevato di possibilità o combinazioni. Per questo tipo di problemi esiste una branca della matematica chiamata per l'appunto matematica combinatoria.
Il termine lateral thinking (pensiero laterale) è stato coniato da Edward de Bono per denotare l'abilità di risolvere situazioni molto difficili considerandole sotto un punto di vista completamente nuovo e inaspettato. La soluzione di un Sudoku, in genere, è un lavoro metodico, di pazienza, basato su ragionamenti standardizzati. Il ricorso alla logica laterale è piuttosto scarso.
Il pensiero laterale è un'attività superiore dell'intelligenza umana, almeno per ora non riproducibile da un computer. Eppure esistono programmi per computer capaci di risolvere qualunque Sudoku in una manciata di secondi, e addirittura di elencare tutti i ragionamenti logici (diretti, non laterali) che hanno fatto per giungere alla soluzione. Anche in italiano!
Su BASE Cinque ne trovate due, già linkati sopra.

Luglio 2005 - Agosto 2005

Risposte & riflessioni

Ecco un Sudoku un po' più difficile

Primo passaggio

Soluzione finale

Number place

+-----+-----+-----+
|8 5 4|2 1 9|6 7 3|
|3 1 7|5 8 6|9 2 4|
|2 6 9|7 3 4|1 8 5|
+-----+-----+-----+
|4 3 2|8 9 1|5 6 7|
|1 9 6|4 5 7|8 3 2|
|7 8 5|6 2 3|4 9 1|
+-----+-----+-----+
|6 2 3|9 4 5|7 1 8|
|9 4 1|3 7 8|2 5 6|
|5 7 8|1 6 2|3 4 9|
+-----+-----+-----+

Sudoku da 21 numeri
Un particolare ringraziamento a Piercarlo Baroncelli che ha trovato un errore ed ha inviato la soluzione esatta.

Continua...

Sito Web realizzato da Gianfranco Bo