Sudoku
Da Wikipedia, l'enciclopedia libera.
Sudoku (giapponese: 数独, sūdoku, nome completo 数字は独身に限る Sūji wa dokushin ni kagiru) (sign: "sono consentiti solo numeri solitari") è un gioco di logica nel quale al giocatore o solutore 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 e, pertanto, senza ripetizioni.
Indice |
[modifica] Storia del gioco
Il primo campionato mondiale di Sudoku si è tenuto a Lucca dal 10 al 12 marzo 2006, vinto da Jana Tylova (Repubblica Ceca). La selezione italiana è avvenuta sempre a Lucca, il 4 marzo 2006, ed è stata vinto da Giulia Franceschini (Venezia). Secondo posto per Gabriele Quaresima (Cori, LT) e terzo posto per Gabriele Simionato (Torviscosa, UD). La prima nazionale italiana di sudoku contava sei membri: oltre ai tre già citati ne facevano parte Francesco Aricò (FI), Anna Magagni (MO), Martino Nacca (Atripalda, AV).
Vincitori del campionato italiano:
- 2006 Giulia Franceschini
- 2007 Elena Mazzini
- 2008 Gabriele Simionato
- 2009 Gabriele Simionato
Vincitori del campionato mondiale
- 2006 (torneo svolto a Lucca, Italia) Jana Tylova (Repubblica Ceca)
- 2007 (Praga, Repubblica Ceca) Thomas Snyder (U.S.A.)
- 2008 (Goa, India) Thomas Snyder (U.S.A.)
- 2009 (Zilina, Slovacchia) Jan Mrozowski (Polonia)
[modifica] Descrizione matematica e descrizione delle varianti
Come tutti i giochi logici, Sudoku può essere descritto completamente mediante nozioni di logica, in questo caso si applica la combinatoria.
Il gioco si svolge in matrici, che chiamiamo matrici Sudoku di aspetto 9×9 (le griglie) le cui caselle possono contenere un elemento di un insieme di 9 oggetti distinguibili, oppure un ulteriore oggetto diverso dai precedenti. Per fissare i discorsi conveniamo che le righe e le colonne delle matrici siano individuate dagli interi da 1 a 9, che i nove oggetti siano gli interi dell'insieme '9' := {1, 2, 3, 4, 5, 6, 7, 8, 9}, che l'oggetto ulteriore sia denotato con la lettera b e che una casella contenente b sia detta casella bianca o vuota. Una matrice Sudoku M viene considerata suddivisa in 9 blocchi di aspetto 3×3 che denotiamo Bh,k con h,k = 1, 2, 3; il blocco Bh,k riguarda le righe relative agli indici 3h-2, 3h-1 e 3h e le colonne relative agli indici 3k-2, 3k-1 e 3k. 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 greco-latini". 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 volta ed una volta sola, dove n è la dimensione del quadrato (nel caso del Sudoku n=9). Inoltre occorre sovrapporre n soluzioni di questo tipo (dette quadrati latini) in modo che ciascuna casella abbia una n-upla distinta.
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.[1]
[modifica] 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). [esempio: http://www.killersudoku.it/wp-content/uploads/due_schemi.jpg]
Per la soluzione di un Killer Sudoku può essere utile la tabella riportata alla voce Kakuro.
[modifica] 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 gande 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. [esempio: http://www.killersudoku.it/wp-content/uploads/2008/06/080608%20Simionato1.gif]
[modifica] 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. [esempio: http://www.xsudoku.it/strategie/contenuti_file/image006.jpg]
[modifica] 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. [esempio Jigsaw: http://autonomoussource.com/blog/mt-static/pics/js1.jpg] [esempio Toroidal: http://www.stanford.edu/~tsnyder/toroidal.jpg]
[modifica] 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. [esempio: http://www2.polito.it/didattica/polymath/htmlS/probegio/GAMEMATH/Sudoku/Img/EvenOddSudoku.gif]
[modifica] Sudoku Tris
Il 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. [esempio:http://www.knightfeatures.com/KFWeb/content/features/kffeatures/puzzlesandcrosswords/KF/Sudoku/Sudoku_147/Sudoku147_001.jpg]
[modifica] 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. Il più volte campione mondiale di sudoku, Thomas Snyder, ha prodotto alcune pubblicazioni destinate a diffondere questa variante del gioco. [esempio: http://www.stanford.edu/~tsnyder/battleshipsudoku.jpg]
[modifica] Sudoku Samurai
È una variante che include due o più griglie di sudoku. Ciascuna griglia è sovrapposta ad almeno un'altra, solitamente condividendo uno dei settori, ma sono possibili più configurazioni. Il "samurai" vero e proprio è composto da 5 griglie disposte ad X. Ciascuna delle griglie di un samurai può rappresentare a sua volta una differente variante. [esempio:http://www.math.jmu.edu/newsletter/samuraiX.gif]
[modifica] 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. [esempio: http://www.brainfreezepuzzles.com/main/puzzles/Brainfreeze_Pyramids.jpg]
[modifica] 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. [esempio: http://www.xsudoku.it/serbatoio/sudokudragons/difficult.png]
[modifica] 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. [esempio: http://www.sudoku.it/images/stories/sudokuvar/sudoku_esterno_start.png]
[modifica] Metodologie risolutive
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.
[modifica] Per eliminazioni successive (Naked Single)
Questa metodologia prevede che si possa cancellare il contenuto delle celle. Si inizia scrivendo in ogni quadretto libero tutti i numeri ammessi e non ammessi, dopo aver eliminato dalle nove cifre quelle già presenti nella riga, nella colonna e nella regione 3 x 3 a cui il quadretto appartiene; si esamina poi la tabella alla ricerca di scelte obbligate e si procede alla cancellazione successiva delle scelte effettuate dalle corrispondenti celle della colonna, della riga e della regione. In altre parole si va ad inserire la soluzione in una cella quando questa ha un solo possibile candidato.
Esistono in rete delle tabelle risolutive per il sudoku precompilate con tutti i numeri dall'uno al nove per ogni casella. L'utilizzo di queste tabelle risolutive consente la risoluzione dello schema senza dover eseguire cancellature. Esistono anche programmi che implementano queste tabelle in forma interattiva come il sudoku minato.
[modifica] Per "zone proibite" (Hidden Single)
Questa tecnica da sola non è sufficiente a risolvere completamente un Sudoku (a meno che non sia molto facile), ma è un valido complemento nella risoluzione di tutti gli schemi, e accelera di molto la ricerca della soluzione. Si tratta di esaminare la disposizione di uno dei numeri nelle varie regioni per controllare se, in regioni dove non è presente, impedisce tutte le altre posizioni meno una, che quindi deve essere quella giusta per quel numero.
In figura accanto si riporta un esempio per il numero sei: i tre "sei" considerati (in giallo) impediscono la presenza di altri sei nelle caselle vuote evidenziate in violetto. Nella regione centrale sinistra rimane una sola casella "permessa" per il sei (evidenziata in verdino): e poiché deve esistere un sei per ogni regione, si deduce che il sei di quella regione è proprio lì.
[modifica] Naked Pair
A differenza delle precedenti due tecniche, questa si applica a tutti i gruppi possibili (colonne, righe e sottogriglie). Prendiamo come esempio la lista completa dei candidati possibili in una sottogriglia (possiamo escludere dalla lista le celle che hanno gia assegnata la soluzione).
{4, 5}, {4, 7, 9}, {4, 5}, {7, 9}, {4, 5, 9, 1}
La tecnica afferma che se ci sono due celle che hanno due identici candidati, è possibile rimuovere i due candidati dalle altre celle del gruppo preso. Nell'esempio due celle hanno come candidati il 4 e il 5: in questo caso possiamo andare ad eliminarli nelle altre celle e semplificare così l'insieme delle soluzioni possibili. Il 4 e il 5 sono obbligati ad essere nelle due celle trovate; se infatti uno di essi fosse in una cella, si arriverebbe ad una posizione con una cella senza candidati. La soluzione si può pertanto semplificare così:
{4, 5}, {7, 9}, {4, 5}, {7, 9}, {9, 1}
Semplificando le soluzioni abbiamo trovato due nuove celle che hanno gli stessi due candidati {7,9}. Usiamo nuovamente la stessa tecnica sul solito gruppo:
{4, 5}, {7, 9}, {4, 5}, {7, 9}, {1}
Abbiamo appena trovato una soluzione.
La tecnica vale anche per triplette, quadruple e così via e non già solo coppie di numeri (sebbene queste ultime siano quasi le uniche che si possano incontrare nei sudoku "classici"). Modificando leggermente l'esempio precedente, poniamoci nel caso
{4, 5, 7}, {4, 5, 7}, {4, 5, 7}, {1, 4, 5, 7, 9}, {1, 4, 5, 7, 9}
In questo caso, è evidente che le prime tre celle presentano tutte i medesimi candidati (4, 5 e 7) e dunque questi possono essere solo in queste tre celle. Di conseguenza, semplificando avremo:
{4, 5, 7}, {4, 5, 7}, {4, 5, 7}, {1, 9}, {1, 9}
Se vi sono due numeri che compaiono insieme ad altri solo in due celle, questi possono essere isolati. Nell'esempio che segue il 5 ed il 9 compaiono solo nella prima e quarta cella.
{4, 5, 8, 9}, {2 ,3, 4, 6, 8}, {2, 3, 4, 6, 8}, {2, 3, 4, 5, 9}
diventa
{5, 9}, {2, 3, 4, 6, 8}, {2, 3, 4, 6, 8}, {5, 9}.
Se all'interno di una sottogriglia vi sono numeri che appaiono solo in una stessa riga o colonna, è possibile cancellare gli stessi numeri che sono nella stessa riga o colonna ma di un'altra sottogriglia.
Ad esempio, nello schema che compare all'inizio di questa pagina e in cui sono stati già stati scritti in verde i numeri ammessi, si vede che nella terza colonna della prima sottogriglia in alto a sinistra si ha:
{4, 8, 9}, {2, 4, 8, 9}.
Si può cancellare il 9 che compare sempre nella terza colonna ma di altre sottogriglie.
{1, 2, 4, 8, 9} si semplifica in {1, 2, 4, 8}.
[modifica] Sudoku intrecciati
Esistono Sudoku con, ad esempio, 9 griglie intrecciate. Il metodo di risoluzione è lo stesso che si applica ai Sudoku classici.
[modifica] Note
- ^ È degno di nota, ad esempio, il sito dell'informatico francese Christian Boyer: http://cboyer.club.fr/multimagie/English/SudokuBimagic.htm.
[modifica] Bibliografia
- Jean-Paul Delahaye, "La scienza del Sudoku", Le Scienze, agosto 2006
[modifica] Voci correlate
[modifica] Collegamenti esterni
- (EN) Puzzles free
- (IT) Puzzles gratuiti
- (IT) Sudoku Diagonali
- (IT) Applicazione della tecnica dei Dancing Links al problema della soluzione di un Sudoku
- (IT) Sudoku in Flash
- (EN) Sudoku Flash Game
- (IT) Sudoku classico
- (IT) Solutore sudoku in linea
- (IT) Sudoku
