Sudoku

Sudoku



Se siete appassionati di Sudoku ecco alcuni link che potrebbero interessarvi.





Sudoku




Sudoku
Da Wikipedia, l'enciclopedia libera.
(Rimando da Sudoku)

Sudoku (sign: "numero solitario") è 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.

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

Descrizione matematica
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.

È 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 ben 6.670.903.752.021.072.936.960 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.

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 sorprendenti legami tra Sudoku e Quadrati magici.[1]

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)

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

Per eliminazioni successive (Naked Single)
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 3*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.

Per "zone proibite" (Hidden Single)
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 (clicca qui) 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ì.

Vedi anche: