Sudoku

Il tormentone dell'estate 2005

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.

Sudoku n 19 pubblicato su The Guardian, 30 maggio 2005

Un Sudoku è una griglia di 9x9 quadretti in ognuno dei quali si dovrà scrivere un numero, da 1 a 9. La griglia è a sua volta divisa in 9 regioni di 3x3 quadretti. C'è una sola regola per comporre un Sudoku: in ogni colonna, in ogni riga e in ogni regione, ogni numero deve comparire una volta sola. Per fare un Sudoku potete cominciare da una griglia vuota, ma allora Nobuhiko Kanamoto che lo ha inventato e gli editori che lo pubblicano non ci guadagnerebbero niente. Perciò i Sudoku che trovate sulle riviste sono già parzialmente compilati e il vostro compito è quello di completarli. I Sudoku da manuale enigmistico devono soddisfare tre requisiti: 1) i numeri iniziali devono formare uno schema simmetrico rispetto al centro della griglia; 2) deve esistere una unica soluzione; 3) i numeri iniziali dovrebbero essere meno di 30.

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.

S'è detto del Sudoku
La parabola del Sudoku in Italia attraverso alcune citazioni.

• Sudoku? Ah no, io non lo pratico, nella mia palestra non c'è.
• Che cos'è, un piatto sardo?.
• Il Sudoku è come un "virus", che si trasmette di persona in persona superando confini politici e culturali.
• Il Sudoku dà assuefazione.
• Il Sudoku dà dipendenza, la Sudokudipendenza.
• Se non riesco a completare un Sudoku prima di mezzogiorno, rimango in una depressione da suicidio per il resto della giornata.
• Se il Sudoku non vi riesce, vi sentirete irrimediabilmente poco intelligenti.
• Giocare con costanza a Sudoku può ridurre fino al 33% il rischio del morbo di Alzheimer, nei soggetti predisposti.
• Il Sudoku, sul lungo periodo, aiuta a migliorare le capacità logiche.
• Con il Sudoku la matematica non c'entra nulla.
• Per risolvere un Sudoku serve la logica laterale.
• I Sudoku fatti "a mano" sono migliori di quelli creati con il computer.
• Se ne sono viste tante, e passerà anche il Sudoku.
• Il mondo prima del Sudoku era molto migliore.

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.

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 ha 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. Si pensa che l'Universo sia 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.

Sudoku Googling
Se andate su Google e digitate "Sudoku", scoprirete che nel Web ci sono più di un milione di pagine in cui si parla di questo gioco. Potete farvi una Sudokultura immensa.
Ma se guardate bene, vedrete che anche il potente Google ha un piccolo dubbio, infatti scrive, in cima alla pagina:
Forse cercavi "sodoku"?
Ho ignorato molte volte questo messaggio, ma alla fine non mi sono più sentito di continuare a vivere con questa grave lacuna: che cosa diavolo è il sodoku?
Mi è bastato un clic per scoprire che il sodoku è una malattia infettiva dovuta ad uno spirillo. Spesso è trasmessa con il morso di ratti o di altri roditori. L'incubazione dura tra 7 e 21 giorni. La ferita comincia ad ulcerarsi e sopravviene una febbre ricorrente che continua per settimane o mesi. Niente panico! In genere la malattia guarisce spontaneamente ma si consiglia di prendere qualche antibiotico.
L'epidemia, questa volta di Sudoku, ha iniziato a diffondersi in Italia nel maggio del 2005. Ora siamo tutti vaccinati e possiamo riporre i nostri Sudoku nella vetrina, assieme al cubo di Erno Rubik e al gioco del 15, di Samuel Loyd.

Ultimo aggiornamento: luglio 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

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

Sudoku pettegolezzi

Riporto l'incipit dell'articolo di Stefano Bartezzaghi pubblicato nella rubrica "Lessico e nuvole", laRepubblica.it, 3 giugno 2005.

"Avete fatto judo alle medie, avete imparato a mangiare il sushi al liceo, avete avuto in regalo una Kawasaki per la maturità, avete comprato un tatami all'Università, avete letto haiku e tanka al vostro matrimonio, avete incontrato il tamagotchi con il primo figlio, avete letto Banana Yoshimoto facendo del feng shui assieme a una geisha - o a un samurai - e ascoltando Ryuichi Sakamoto nel periodo della vostra separazione. Prima dell'inevitabile harakiri o - se siete aggiornati - seppuku mi sa che vi toccherà imparare cosa sia il Sudoku."

Il quotidiano di Genova IL SECOLO XIX pubblica un Sudoku al giorno dal 9 maggio 2005.
Questo che vedete qui sotto è il Sudoku n° 39 del 27 giugno 2005. E' considerato di livello facile.

Ecco la soluzione:

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

Ed infine, spero, la copertina (parziale) del N° 1 della rivista mensile LOGIC Art, della nonzero Edizioni, in edicola dal 18 maggio 2005. E' dedicata ai Crucipixel, ai Pixelink e ai Sudoku

Ai posteri l'ardua sentenza.

Il tormentone continua...

Il Corriere della sera pubblica Sudoku che chiama diabolici. Ecco un esempio.
(tratto dal sito: Le terre di Pietro, http://pietrob.net/)

Sudoku dal Corriere della Sera del 2/7/05

Ecco la soluzione:

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

L'analizzatore JAVA ha trovato la soluzione unica in circa 1 secondo, elencando i seguenti ragionamenti: (le coordinate (a,b) indicano rispettivamente riga e colonna)

START
1. Il valore 6 è l'unico candidato per la cella (2,2).
2. Il valore 4 è l'unico candidato per la cella (3,1).
3. La cella (3,7) è l'unico candidato per il valore 7 nella colonna 7.
4. La cella (6,5) è l'unico candidato per il valore 2 nella riga 6.
5. La cella (3,8) è l'unico candidato per il valore 9 nella riga 3.
6. Il valore 6 è l'unico candidato per la cella (6,8).
7. La cella (2,8) è l'unico candidato per il valore 5 nella regione [1,3].
8. Il valore 1 nella regione [3,3] deve stare nella colonna 8.
La cella (9,4) è l'unico candidato per il valore 1 nella riga 9.
9. La cella (1,7) è l'unico candidato per il valore 1 nella riga 1.
10. Il valore 8 è l'unico candidato per la cella (3,9).
11. Il valore 3 è l'unico candidato per la cella (7,9).
12. Il valore 1 è l'unico candidato per la cella (5,9).
13. La cella (5,3) è l'unico candidato per il valore 3 nella riga 5.
14. Il valore 2 è l'unico candidato per la cella (3,3).
15. Il valore 5 è l'unico candidato per la cella (3,4).
16. Il valore 9 è l'unico candidato per la cella (4,2).
17. Il valore 7 è l'unico candidato per la cella (6,2).
18. Il valore 4 è l'unico candidato per la cella (6,3).
19. Il valore 5 è l'unico candidato per la cella (4,3).
20. Il valore 4 è l'unico candidato per la cella (4,5).
21. Il valore 6 è l'unico candidato per la cella (9,3).
22. Il valore 5 è l'unico candidato per la cella (7,1).
23. Il valore 7 è l'unico candidato per la cella (7,3).
24. Il valore 8 è l'unico candidato per la cella (4,7).
25. Il valore 6 è l'unico candidato per la cella (7,7).
26. Il valore 8 è l'unico candidato per la cella (7,5).
27. Il valore 7 è l'unico candidato per la cella (2,5).
28. Il valore 4 è l'unico candidato per la cella (2,6).
29. Il valore 5 è l'unico candidato per la cella (5,5).
30. Il valore 1 è l'unico candidato per la cella (7,8).
31. Il valore 2 è l'unico candidato per la cella (7,2).
32. Il valore 9 è l'unico candidato per la cella (7,6).
33. Il valore 7 è l'unico candidato per la cella (5,6).
34. Il valore 6 è l'unico candidato per la cella (8,5).
35. Il valore 8 è l'unico candidato per la cella (1,3).
36. Il valore 2 è l'unico candidato per la cella (1,4).
37. Il valore 3 è l'unico candidato per la cella (1,6).
38. Il valore 9 è l'unico candidato per la cella (5,4).
39. Il valore 5 è l'unico candidato per la cella (8,6).
40. Il valore 8 è l'unico candidato per la cella (2,4).
41. Il valore 3 è l'unico candidato per la cella (3,2).
42. Il valore 1 è l'unico candidato per la cella (3,5).
43. Il valore 6 è l'unico candidato per la cella (3,6).
44. Il valore 3 è l'unico candidato per la cella (4,8).
45. Il valore 6 è l'unico candidato per la cella (5,1).
46. Il valore 4 è l'unico candidato per la cella (5,7).
47. Il valore 9 è l'unico candidato per la cella (6,7).
48. Il valore 4 è l'unico candidato per la cella (7,4).
49. Il valore 1 è l'unico candidato per la cella (8,2).
50. Il valore 7 è l'unico candidato per la cella (8,4).
51. Il valore 8 è l'unico candidato per la cella (8,8).
52. Il valore 2 è l'unico candidato per la cella (9,6).
53. Il valore 5 è l'unico candidato per la cella (9,7).

Cosa c'era di diabolico?

Pare che la Repubblica pubblichi Sudoku che non sono veri Sudoku perché hanno soluzioni multiple.
Ecco un esempio: il Sudoku de la Repubblica del 26 Giugno 2005.
(tratto dal sito: Le terre di Pietro, http://pietrob.net/)

Soluzione secondo
la Repubblica 

1 6 2 8 4 9 3 7 5
7 3 8 5 1 6 4 2 9
4 5 9 3 2 7 8 6 1
6 1 3 9 8 4 7 5 2
2 4 5 7 3 1 6 9 8
8 9 7 2 6 5 1 4 3
9 2 1 6 7 8 5 3 4
5 7 4 1 9 3 2 8 6
3 8 6 4 5 2 9 1 7

Soluzione secondo
il risolutore 1 

9 1 2 8 5 6 3 7 4
7 3 6 4 1 9 8 5 2
4 5 8 3 2 7 9 6 1
1 6 3 9 8 4 7 2 5
2 4 5 7 3 1 6 9 8
8 9 7 2 6 5 1 4 3
6 2 1 5 7 8 4 3 9
5 7 9 1 4 3 2 8 6
3 8 4 6 9 2 5 1 7

Soluzione secondo
il risolutore 2

1 3 2 6 5 8 4 7 9
7 6 8 4 1 9 3 2 5
4 5 9 3 2 7 8 6 1
6 1 3 9 8 4 7 5 2
2 4 5 7 3 1 6 9 8
8 9 7 2 6 5 1 4 3
9 2 1 8 4 6 5 3 7
5 7 4 1 9 3 2 8 6
3 8 6 5 7 2 9 1 4

Buon Sudoko ... Un grazie Particolare a Gianfranco Bo autore dell'articolo old