Sudoku

Da Wikipedia, l'enciclopedia libera.

Sudoku (giapponese: 数独, sūdoku, nome completo 数字は独身に限る Sūji wa dokushin ni kagiru) è 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 va considerata divisa 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 senza ripetizioni tutte le cifre da 1 a 9.

Indice 1 Storia del gioco 2 Descrizione matematica 3 Metodologie risolutive 3.1 Per eliminazioni successive (Naked Single) 3.2 Per "zone proibite" (Hidden Single) 3.3 Naked Pair 4 Sudoku intrecciati 5 Versioni di pubblico dominio 6 Bibliografia 7 Voci correlate 8 Collegamenti esterni

[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)

[modifica] Descrizione matematica

Questa descrizione ha lo scopo di mostrare che, come tutti i giochi logici, anche Sudoku può essere descritto completamente mediante nozioni matematiche di base, in particolare per questo gioco mediante nozioni trattate dalla combinatoria.

Il gioco del Sudoku riguarda 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 B_h,k con h,k = 1,2,3; il blocco B_h,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 Sudoku incompleta, è una matrice Sudoku che presenta alcune celle bianche. Scopo del gioco è la trasformazione della griglia proposta in una matrice Sudoku completa, cioè in una matrice Sudoku 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 iniettive.

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.

È da notare che mentre una matrice "semplice" (con 35 numeri già inseriti) possiede una sola soluzione, una matrice "difficile", (con 20 numeri) può possedere più soluzioni: d'altra parte, una "matrice vuota", con soli spazi, ha sicuramente un numero elevatissimo (6,670,903,752,021,072,936,960) di soluzioni.

Le soluzioni di una qualsiasi altra matrice incompleta sono un sottoinsieme delle soluzioni della matrice vuota. Un sistema relativamente semplice, anche se prettamente teorico, per risolvere il Sudoku è quello di generare tutte le soluzioni con la matrice vuota (con un programma per computer) e poi sovrapporre una matrice incompleta per vedere quali tra queste coincidono.

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.

Vale la pena precisare che, al contrario di quanto si trova spesso affermato, il sudoku è un gioco di logica ma non propriamente di matematica, né tanto meno il gioco 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 sorprendenti legami tra Sudoku e Quadrati magici (è degno di nota, ad esempio, il sito dell'informatico francese Christian Boyer [[1]])

Killer Sudoku La variante del 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. E' 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)

[modifica] Metodologie risolutive

Esistono diverse metodologie risolutive per questo gioco, tutte poco legate alla logica ed alla matematica ma strettamente connesse all'operatività manuale ed alla pazienza.

Alcune tecniche mirano a trovare la soluzione della cella analizzando le righe, colonne e sottogriglie e calcolando tutti i possibili candidati delle caselle. Altre teniche 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. 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

[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 3x3 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.

[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}

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 elimanerli 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.

[modifica] Sudoku intrecciati

Nell'esempio a destra abbiamo un Sudoku con 9 griglie intrecciate. Il metodo di risoluzione è lo stesso che si applica ai Sudoku classici. La soluzione di questo Sudoku la trovate cliccando sull'immagine all'interno della pagina.

[modifica] Versioni di pubblico dominio

• KSudoku Generatore e risolutore open source per KDE (progetto italiano).
• Versione di Sudoku per Microsoft Excel di pubblico dominio preparata per wikipedia: Sudoku.xls
• Contrada Poggiolo Generatore di sudoku in formato Adobe Flash con codice sorgente aperto.

[modifica] Bibliografia

• Jean-Paul Delahaye, "La scienza del Sudoku", Le Scienze, agosto 2006

[modifica] Voci correlate

• Quadrato magico

[modifica] Collegamenti esterni

• BorSudoku Generatore online di Sudoku.
• logicando Gioca a Sudoku gratis, parla nei forum, accetta le sfide.
• sudoku.fremsoft.it Scarica la versione pdf della tabella risolutiva e gioca senza usare la gomma.
• ksudoku – Generatore e risolutore open source per kde (progetto italiano).
• Sudoku Online – Generatore online di Sudoku, risolutore e aiuto (EN)
• Analizzatore automatico di Sudoku
• Sudoku online – Molti schemi da giocare direttamente online (con Flash player)
• The Sudoku Big List – Elenco di link riguardanti il Sudoku
• Sudoku Versione online del Sudoku
• Sudokusol – Libri, Software, Raccolte schemi da scaricare, possibilità di giocare online, Forum.
• Gioco SUDOKU – nuove griglie con differenti livelli ogni giorno, griglie stampabili.