uno schema di gioco e
la sua soluzione
•
Il sudoku (termine giapponese che in italiano vuol dire "sono
consentiti solo numeri solitari") è un gioco di logica nel quale al
giocatore viene proposta una griglia di 9×9 celle, ciascuna delle
quali può contenere un numero da 1 a 9, oppure essere vuota; la
griglia è suddivisa in 9 righe orizzontali, nove colonne verticali e,
da bordi in neretto, in 9 "sottogriglie", chiamate regioni, di 3×3
celle contigue. Le griglie proposte al giocatore hanno da 20 a 35
celle contenenti un numero. Scopo del gioco è quello di riempire
le caselle bianche con numeri da 1 a 9, in modo tale che in ogni
riga, colonna e regione siano presenti tutte le cifre da 1 a 9, senza
ripetizioni.
Storia
Un "quadrato magico diabolico" pubblicato su La France il 6 luglio 1895
I primi giochi di logica basati sui numeri apparvero sui giornali verso la fine del
XIX secolo, quando alcuni enigmisti francesi iniziarono a sperimentarli
rimuovendo opportunamente dei numeri dai quadrati magici. Le Siècle, un
quotidiano parigino, pubblicò nel 1982 un quadrato magico di dimensioni 9×9
parzialmente completo con sottoquadrati di dimensioni 3×3. Non si trattava di un
sudoku così come lo conosciamo oggi, poiché conteneva numeri a doppia cifra
e, per essere risolto, richiedeva l'aritmetica piuttosto che la logica, ma
ammetteva comunque la regola per cui ogni riga, colonna e sottoquadrato
dovesse contenere gli stessi numeri senza ripeterli. Successivamente un
giornale rivale de Le Siècle, La France, ridefinì le regole di questo gioco,
avvicinandosi di molto al sudoku moderno: ogni riga, colonna e sottoquadrato
del quadrato magico doveva essere riempita soltanto con i numeri da 1 a 9,
sebbene i sottoquadrati non fossero marcati all'interno dello schema. Questi
giochi settimanali furono pubblicati anche da altri quotidiani francesi come
L'Echo de Paris per circa un decennio, ma poi scomparvero all'epoca della
Prima Guerra Mondiale.
Secondo l'enigmista statunitense Will Shortz, il sudoku moderno fu realizzato da
Howard Garns, un ex architetto in pensione dell'Indiana (morto nel 1989), e
pubblicato per la prima volta nel 1979 da Dell Magazines con il titolo Numbers in
Place. Il gioco venne introdotto in Giappone dalla casa editrice Nikoli nell'aprile
del 1984. Nel 1986 Nikoli introdusse due novità: il numero massimo di celle già
riempite fu ristretto a 32 e le griglie diventarono "simmetriche" (nel senso che i
numeri già stampati venivano distribuiti su celle simmetriche.
Nell'ottobre del 2004 il sudoku venne importato in Gran Bretagna da un ex
giudice neozelandese, Wayne Gould per poi diffondersi in Europa e nel resto del
mondo nel 2005
Descrizione matematica
Il Sudoku può essere descritto completamente mediante nozioni di logica, in particolare
si applica la logica combinatoria. Il gioco si svolge in matrici (le matrici Sudoku o griglie)
di aspetto 9×9, le cui caselle possono contenere un elemento di un insieme di 9 oggetti
distinguibili. Una matrice Sudoku M viene considerata suddivisa in 9 blocchi di aspetto
3×3. In ogni riga, colonna e regione di una matrice Sudoku i valori interi non possono
essere ripetuti.
Una istanza di Sudoku, detta anche griglia proposta o matrice incompleta, è una matrice
Sudoku che presenta alcune celle bianche. Scopo del gioco è la trasformazione della
griglia proposta in una matrice completa, cioè in una matrice priva di celle bianche e
quindi tale che in ogni sua riga, colonna e regione compaiano tutti gli elementi di '9'
(ciascuno una sola volta). Si osserva che una matrice Sudoku completa è un quadrato
latino di ordine 9 avente per blocchi matrici 3×3 con i nove numeri da 1 a 9.
Affinché una matrice incompleta sia considerata valida, ai fini del gioco, è necessario che
la soluzione sia univoca, ovvero non devono sussistere due o più soluzioni differenti, nei
quali casi il gioco viene considerato non valido. Nei casi di varianti di sudoku (p.es. killer,
jigsaw, x, toroidale, ecc.) ulteriori condizioni devono essere verificate affinché la matrice
risulti valida. La difficoltà di un sudoku non è data dalla quantità di numeri iniziali, bensì
dalla loro disposizione. Le soluzioni di una qualsiasi altra matrice incompleta sono un
sottoinsieme delle soluzioni della matrice vuota.
Storicamente questo gioco è un caso ben più facile da risolvere di un antico e famoso
gioco di logica-matematica a cui si è dedicato anche Eulero; si tratta dei "quadrati grecolatini". In questo caso, a differenza del Sudoku, non vi sono griglie interne e l'unica
condizione da rispettare è che in ogni riga ed in ogni colonna compaiano tutti i numeri da
1 ad n*n una ed una sola volta, dove n è la dimensione del quadrato (nel caso del Sudoku
n=9).
Al contrario di quanto spesso si afferma, il sudoku è un gioco di logica e non di
matematica, né ha a che fare con i numeri. Le proprietà dei numeri non vengono mai
utilizzate e neppure viene mai utilizzato il fatto che siano dei numeri. Per rendersi conto
della cosa basta pensare che il gioco sarebbe esattamente identico se anziché i primi
nove numeri si usassero le prime nove lettere dell'alfabeto oppure nove simboli diversi
tra loro (non c'è nemmeno bisogno che tra i simboli sussista un ordine).
Tuttavia alcuni ricercatori matematici hanno messo in evidenza molti legami tra Sudoku e
quadrati magici.
Varianti
Killer Sudoku
•
Esempio di Killer Sudoku
La variante detta killer sudoku si
presenta
come
una
matrice
(solitamente in base 9, ma la
grandezza può variare) che non
presenta caselle già occupate da
numeri, dunque le 81 caselle della
matrice sono interamente bianche. Gli
indizi dati per risolvere correttamente
la matrice vengono da alcuni gruppi di
celle che riportano la somma che i
singoli elementi di quelle celle devono
totalizzare. È uno dei pochi casi di
sudoku in cui intervengono i valori
nominali dei numeri: le altre varianti
che li utilizzano sono il Sudoku
Moltiplicazione (in cui anziché la
somma è riportato il prodotto di due o
più cifre) e il Sudoku Cornice (nel
quale, lungo il bordo esterno della
matrice sono riportati i valori
corrispondenti alla somma delle tre
cifre più prossime al bordo).
Sudoku X
•
La variante detta "xSudoku" o "Sudoku Diagonale" o anche "Sudoku X" si presenta con
una matrice lungo le quali sono evidenziate le due diagonali maggiori, ciascuna di 9
caselle di lunghezza. La casella centrale della matrice è in comune ad entrambe le
diagonali. Nel risolvere lo schema è necessario tenere presente che anche le due
diagonali debbono contenere senza ripetizioni i numeri dall'1 al 9. Questa condizione
aumenta da 27 a 29 la quantità di ZONE che bisogna verificare (9 righe + 9 colonne + 9
riquadri + 2 diagonali) e permette una grande varietà di strategie aggiuntive per
raggiungere la soluzione desiderata. In talune varianti di xsudoku sono evidenziate
alcune diagonali minori, anziché le due maggiori, ma il principio è il medesimo: le
diagonali evidenziate non devono contenere ripetizioni di numeri, sebbene non
contengano tutto l'insieme di numeri dall'1 al 9.
Sudoku Y
•
È la variante ideata nel 2008 dal campione italiano Gabriele Simionato. Nella griglia sono
evidenziate due zone di nove caselle, disposte in modo da formare la lettera "Y". Il
gambo della Y è composto da 5 caselle che sono in comune tra le due zone, mentre
ciascuno dei due rami è costituito da altre 4 caselle. Si noti che i numeri da inserire lungo
i due rami sono gli stessi.
Jigsaw Sudoku
•
Esempio di Jigsaw Sudoku
In questa variante la matrice si
presenta suddivisa in 9 zone
dalla forma irregolare, che si
incastrano l'una nell'altra per
formare un puzzle. Ciascuna
delle zone conta esattamente 9
caselle, e ogni casella deve
contenere un diverso numero
dall'1 al 9. Il jigsaw sudoku
include la sottovariante del
sudoku "toroidale" in cui le
nove zone non sono limitate al
bordo della matrice del sudoku,
ma
proseguono
ininterrottamente
dal
lato
opposto.
• Sudoku Pari/Dispari
•
Nel sudoku pari/dispari, talune caselle sono marcate con un colore differente, ad
indicare se la casella può contenere un numero pari oppure un numero dispari.
• Sudoku Tris
•
l Sudoku Tris presenta le caselle marcate in 3 modi diversi (vuoto, cerchio, quadrato).
Ciascun marchio può contenere i numeri 1,2,3 (cerchio) 4,5,6 (quadrato) 7,8,9 (vuoto).
Possono naturalmente esistere diverse suddivisioni.
• Sudoku Battleship
•
In questa variante è necessario piazzare nella griglia un set di navi (1 portaerei da 4
caselle, 2 corazzate da 3 caselle, 3 incrociatori da 2 caselle, 4 sottomarini da 1
casella) alle quali corrispondono diverse serie numeriche.
Multi Sudoku
•
Il Multi Sudoku consiste in due
o più griglie di sudoku
sovrapposte
tra
di
loro,
solitamente condividendo uno
dei settori, ma sono possibili
molteplici configurazioni. Il
metodo di risoluzione è lo
stesso che si applica ai Sudoku
classici.
Sudoku Samurai
•
È una variante particolare del
Multi Sudoku ed è composto
da 5 griglie disposte ad X.
Ciascuna delle griglie di un
samurai può rappresentare a
sua volta una differente
variante
• Sudoku a Zone
•
Nella griglia sono evidenziati (solitamente tramite colori) dei settori di nove
caselle, che possono essere contigue o separate tra di loro. Ciascun settore
deve contenere senza ripetizioni i numeri dall'1 al 9. I settori evidenziati in
questo modo sono aggiuntivi rispetto ai nove settori che costituiscono un
sudoku classico.
• Sudoku & Dragons
•
La griglia contiene dei "draghi" in sostituzione dei numeri 9. Talune caselle
sono separate da pareti. Scopo del gioco è riempire la griglia usando cifre dall'1
all'8 in modo che ogni riga, colonna, e riquadro 3x3 contenga un "drago" e tutti
i numeri dall'1 all'8. In aggiunta ciascun "drago" sorveglia, nelle direzioni
ortogonali, 8 caselle le quali debbono contenere tutte le 8 cifre. Le pareti
rappresentano ostacoli alla vista del drago.
• Sudoku Esterno
•
Questa variante è un'ideazione originale di Leo Colovini, esponente della
veneziana Studiogiochi, ed inizialmente si chiamava "Leokuko". La griglia è
solitamente priva di numeri inseriti, mentre all'esterno della griglia sono
presenti degli "indizi". Gli "indizi" vanno inseriti nelle prime tre caselle della
griglia, quindi si può procedere alla soluzione del sudoku con le regole
classiche
Metodologie risolutive
•
Uno schema con le annotazioni dei
possibili numeri in ogni casella
•
Uno schema in cui si sta cercando il
numero 6
•
•
Esempio di interazione tra blocchi
Esistono diverse metodologie risolutive
per questo gioco, tutte poco legate alla
matematica ma strettamente connesse
alla logica. Alcune tecniche mirano a
trovare
la
soluzione
della
cella
analizzando
le
righe,
colonne
e
sottogriglie e calcolando tutti i possibili
candidati delle caselle. Altre tecniche
mirano alla sola cancellazione di alcuni
candidati da alcune celle ben definite.
I candidati di una cella sono i numeri che
sono ammessi come soluzione nella
medesima, ossia è la lista dei 9 numeri
esclusi quelli già presenti nelle righe,
colonne e sottogriglie, e quelli eliminati
da successive elaborazioni. La maggior
parte dei sudoku pubblicati sui quotidiani
possono
essere
risolti
utilizzando
esclusivamente
il
ragionamento
deduttivo. Affinché ciò sia possibile il
sudoku deve avere una soluzione unica e
non deve rendersi necessario procedere
per prove ed errori, in quanto il sudoku è
gioco di logica e non di azzardo.