Il Sudoku (o Sodoku) è il nuovo gioco-mania dell'Europa, diventato famoso dopo l'enorme successo avuto in Giappone.

Sudoku (giapponese: 数独, sūdoku) è un gioco solitario 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 o bianca; la griglia va considerata divisa in 9 "sottogriglie", chiamate regioni, di 3×3 celle contigue. Nella griglia proposta al giocatore le celle che contengono dei numeri sono da 20 a 35.

Lo scopo del gioco è quello di riempire le caselle bianche con numeri da 1 a 9, in modo tale che ogni riga, colonna e regione contenga tutte le cifre da 1 a 9 (ciascuna una sola volta).

Esiste, ovviamente, un'unica soluzione per completare il gioco.

Storia del gioco

Il gioco è nato in Giappone nel 1984 e il suo nome deriva dall'abbreviazione di una frase in lingua giapponese che ha un significato simile a "sono ammessi solo numeri singoli" (suji wa dokushin ni kagiru).

Il gioco è oggi enormemente diffuso, presente su quotidiani di oltre 20 nazioni diverse.

Il primo campionato mondiale di Sudoku si è tenuto a Lucca dal 10 al 12 marzo 2006.

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 colonna delle matrici sono 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.

È 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, ma comunque finito, 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).

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.

Per eliminazioni successive

Uno schema con le annotazioni dei possibili numeri in ogni casella

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.

Per "zone proibite"

Uno schema in cui si sta cercando il numero sei

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

Dal sito: http://it.wikipedia.org