Sudoku

Il sudoku, , nome completo 数字は独身に限る Sūji wa dokushin ni kagiru, che in italiano vuol dire "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, 9 colonne verticali e in 9 "sottogriglie" di 3×3 celle contigue. Queste sottogriglie sono delimitate da bordi in neretto e chiamate regioni. Le griglie proposte al giocatore hanno da 20 a 35 celle contenenti un numero. Lo scopo del gioco è quello di riempire le caselle bianche con numeri da 1 a 9 in modo tale che in ogni riga, in ogni colonna e in ogni regione siano presenti tutte le cifre da 1 a 9, quindi senza ripetizioni. In tal senso lo schema, una volta riempito correttamente, appare come un quadrato latino.

Il gioco fu inventato dal matematico svizzero Eulero da Basilea (1707-1783). La versione moderna del gioco fu pubblicata per la prima volta nel 1979 dall'architetto statunitense Howard Garns all'interno del Dell Magazines con il titolo "Number Place". In seguito fu diffuso in Giappone dalla casa editrice Nikoli nel 1984, per poi diventare noto a livello internazionale soltanto a partire dal 2005, quando fu proposto in molti periodici.

Storia

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 1892 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 all'interno della rivista Dell Pencil Puzzles and Word Games con il titolo Number Place.

Il gioco venne introdotto in Giappone dalla casa editrice Nikoli nella rivista Monthly Nikolist nell'aprile del 1984 con il titolo , successivamente abbreviato da Maki Kaji in Sudoku prelevando soltanto i primi caratteri kanji del nome completo. 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. Sempre nel 2005, "sudoku" venne eletta parola dell'anno dalla Oxford University Press.

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 descriverle 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, per la matrice M, 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: il gioco viene infatti considerato non valido se sussistono due o più soluzioni differenti (cosa comunque non rarissima, sui media non specializzati in enigmistica). Nei casi di varianti di sudoku (per esempio killer, jigsaw, x, toroidale, ecc.) ulteriori condizioni devono essere verificate affinché la matrice risulti valida. La difficoltà di un sudoku non è data tanto dalla quantità di numeri iniziali, ma piuttosto dalla loro disposizione.

Le soluzioni di una qualsiasi altra matrice incompleta sono un sottoinsieme delle soluzioni della matrice vuota.

Il numero delle soluzioni del Sudoku classico è , approssimativamente . Il numero delle soluzioni sostanzialmente diverse escludendo le simmetrie dovute a rotazioni, riflessioni, permutazioni e rietichettature è .

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 da Basilea; 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 una volta ed una volta sola, dove n è la dimensione del lato 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 e non 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 Sono di seguito presentate alcune delle varianti più diffuse di sudoku. Si tenga presente che il gioco si presta ad una innumerevole quantità di varianti, e che ad ogni campionato mondiale ne vengono proposte di nuove. Il computo nel 2012 è di oltre 200 varianti originali. 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).

Per la soluzione di un Killer Sudoku può essere utile la tabella riportata alla voce Kakuro.

Sudoku X

La variante detta "xSudoku" o "Sudoku Diagonale" o anche "Sudoku X" si presenta con una matrice lungo la quale 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.

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

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 a incastro

In questa variante la matrice si presenta suddivisa in 9 zone dalla forma irregolare come nel Jigsaw sudoku, ma non contiene la sottovariante del sudoku "toroidale" quindi oltre che in ogni riga e in ogni colonna si deve inserire i numeri da 1 a 9 anche nelle zone bordate di nero.

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

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.

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. In essa si incrociano schemi 9x9, quello centrale ha in comune con gli altri le celle 3x3 poste agli estremi.

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