Sudoku

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Uno schema di gioco del sudoku...
... e la sua soluzione (evidenziata in rosso)

Il sudoku, in giapponese (数独?, sūdoku), nome completo 字は身に限る 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).[1] 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".[2] In seguito fu diffuso in Giappone dalla casa editrice Nikoli nel 1984,[2] per poi diventare noto a livello internazionale soltanto a partire dal 2005,[3][4] quando fu proposto in molti periodici.

Storia[modifica | modifica wikitesto]

Un quadrato magico diabolico pubblicato su La France il 6 luglio 1895

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.[5] 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.[6]

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.[2]

Il gioco venne introdotto in Giappone dalla casa editrice Nikoli nella rivista Monthly Nikolist nell'aprile del 1984[2] con il titolo Suuji wa dokushin ni kagiru (数字は独身に限る?), successivamente abbreviato da Maki Kaji in Sudoku prelevando soltanto i primi caratteri kanji del nome completo.[2] 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,[3] per poi diffondersi in Europa e nel resto del mondo nel 2005.[4] Sempre nel 2005, "sudoku" venne eletta parola dell'anno dalla Oxford University Press.[7]

Descrizione matematica[modifica | modifica wikitesto]

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, ovvero non devono sussistere due o più soluzioni differenti, nei quali casi il gioco viene considerato non valido. 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 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.

Il numero delle soluzioni del Sudoku classico è 6670903752021072936960,[8] approssimativamente 6,67×1021. Il numero delle soluzioni sostanzialmente diverse escludendo le simmetrie dovute a rotazioni, riflessioni, permutazioni e rietichettature è 5472730538.[9][10]

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.[11]

Varianti[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Esempio di 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[modifica | modifica wikitesto]

Esempio di 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[modifica | modifica wikitesto]

È 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[modifica | modifica wikitesto]

Esempio di 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Esempio di Multi Sudoku a 9 griglie intrecciate

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[modifica | modifica wikitesto]

Esempio di Sudoku Samurai
Soluzione

È 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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. Gabriele Simionato, sebbene non inventore di tale variante, è stato uno dei primi a proporlo nel contesto di una competizione, e detta variante è stata proposta al campionato mondiale tenutosi a Philadelphia.

Sudoku Spread[modifica | modifica wikitesto]

Questa variante, presentata per la prima volta al campionato italiano di sudoku del 2017, è stata ideata dal matematico italiano Giorgio Dendi. Si tratta di una variante cosiddetta "esterna", in cui cioè sono poste all'esterno dello schema delle informazioni necessarie per la sua risoluzione.

Esempio di Sudoku Spread.

In alto a sinistra dello schema è indicata una coppia di numeri: a sinistra di ogni riga e sopra ogni colonna è indicata la somma di tutti i numeri che dovranno essere collocati in tale riga o colonna nelle caselle comprese tra quelle contenenti i numeri della suddetta coppia. Allo stesso modo, in basso a destra dello schema è indicata una differente coppia di numeri: a destra di ogni riga e sotto ogni colonna è indicata la somma di tutti i numeri che dovranno essere collocati in tale riga o colonna nelle caselle comprese tra quelle contenenti i numeri di questa seconda coppia.

Soluzione del Sudoku Spread.

Sudoku Esterno[modifica | modifica wikitesto]

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.

4D Sudoku[modifica | modifica wikitesto]

Versione twisty puzzle del Sudoku. La prima versione di questo rompicapo manipolativo è stata presentata a Žilina durante il 4th World Sudoku Championship nel 2009, a titolo di pura curiosità. Il rompicapo è costituito da 27 cubi colorati alternativamente di bianco ed arancione, calamitati in modo che la polarità consenta di accostare solo i cubi dell'altro colore. Le facce di ogni cubo presentano un numero da 1 a 9 (il 6 ed il 9 non sono distinguibili tra loro); fanno eccezione 9 facce su altrettanti cubi, lasciate intenzionalmente spoglie, le quali rappresentano la base inferiore del cubo. La soluzione del gioco consiste nel disporre i cubi in modo che ogni faccia del cubo finito presenti i numeri dall'1 al 9, ed i numeri di una stessa faccia siano orientati nella medesima direzione. Nel fare ciò bisogna anche tenere conto delle facce interne, quelle cioè che scompaiono all'interno del cubo, le quali sono soggette al medesimo vincolo.

Nonostante il tipo di rompicapo, e il metodo risolutivo, che il più volte campione mondiale Thomas Snyder ha definito "molto lontano dal ragionamento necessario a risolvere un sudoku", il gioco è stato sottoposto ai concorrenti del già citato campionato, come prova a sorpresa. Le indicazioni fornite dalla giuria proponevano ai solutori di costruire più facce possibili coi numeri dall'1 al 9, purché il 4 fosse al centro. Ciò rendeva di fatto impossibile arrivare ad una soluzione completa del rompicapo, mancando un cubo che contenesse solo numeri 4 su tutte le sei facce, da posizionarsi al centro.

Dopo la finale del medesimo campionato aspramente contestata da vari partecipanti a causa di un regolamento poco chiaro, il gioco è stato nuovamente sottoposto ai finalisti come una sorta di "spareggio". Ai finalisti è stato chiesto di risolvere il 4D Sudoku in un tempo massimo di 15 minuti, nonostante gli autori del gioco avessero dichiarato, durante la presentazione, che a loro sono serviti quattro giorni per trovare una soluzione valida. Nessuno dei giocatori è stato ovviamente in grado di concludere il 4D Sudoku in un tempo così breve, e vincitore del campionato è stato nominato Ian Mrozowski in virtù della posizione in classifica.

L'unico tra i partecipanti al campionato ad essere riuscito a risolvere il cosiddetto "sudokubo", sebbene non durante una prova, è stato l'americano Wei-Hwa Huang, in un tempo di circa due ore.

Sudokube[modifica | modifica wikitesto]

È la versione manipolativa del sudoku, realizzato con il meccanismo del cubo di rubik.

Metodi risolutivi[modifica | modifica wikitesto]

Esistono diversi metodi risolutivi per questo gioco, tutti poco legati alla matematica e strettamente connessi 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 sono i numeri da 1 a 9 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.

Per eliminazioni successive (Naked Single)[modifica | modifica wikitesto]

Uno schema con le annotazioni dei possibili numeri in ogni casella

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

Per "zone proibite" (Hidden Single)[modifica | modifica wikitesto]

Uno schema in cui si sta cercando il numero 6

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 che compare già due volte in tre regioni di fila per controllare se, nella terza regione dove non è presente, nella linea dove non è presente, sono impedite 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 6: esso è presente già in due delle prime tre regioni in colonna quindi deve essere presente nella terza regione (quella centrale) nella rimanente delle tre colonne (la prima); qui una casella è già occupata (dal numero 3) quindi controllando le linee ortogonali delle ultime due caselle rimaste si individua una linea già occupata. I tre "6" considerati (in giallo) impediscono quindi la presenza di altri 6 nelle caselle vuote evidenziate in violetto. Nella regione centrale sinistra rimane una sola casella "permessa" per il 6 (evidenziata in verde): e poiché deve esistere un 6 per ogni regione, si deduce che il 6 di quella regione è proprio lì.

Block and Column/Row Interactions/Tertium non datur[modifica | modifica wikitesto]

Esempio di interazione tra blocchi e colonne

Per applicare questa tecnica è sufficiente verificare solo i numeri candidati all'inserimento nelle sottogriglie (o blocchi): se, entro una data sottogriglia, un candidato è presente solo ed esclusivamente in una certa riga o in una certa colonna, allora esso può essere eliminato in quella riga o colonna dalle celle che non appartengono alla sottogriglia di partenza.

Nell'immagine a destra viene riportato un esempio pratico della tecnica; i numeri nelle celle evidenziate in verde sono i numeri già inseriti all'inizio nello schema, mentre quelli piccoli sono i candidati possibili della cella.

Se andiamo ad osservare la prima sottogriglia notiamo che il candidato 7 è presente solo nelle caselle evidenziate in rosso, che si trovano entrambe sulla seconda colonna. In quella sottogriglia il 7 è obbligato a stare nella seconda colonna. Questa informazione è sufficiente per procedere all'eliminazione del candidato 7 nella seconda colonna dalle celle che non appartengono alla prima sottogriglia (le celle evidenziate in giallo).

Block Interactions/Tertium non datur[modifica | modifica wikitesto]

Esempio di interazione tra blocchi

Questa tecnica analizza i candidati delle celle a gruppi di due sottogriglie orizzontali o verticali tra di loro. Nell'esempio viene analizzata la sottogriglia centrale con quella centrale in alto.

Nell'immagine notiamo che il candidato 3 è presente in due sole colonne tra le due sottogriglie prese in analisi. Se nella sottogriglia più in alto il candidato 3 è nella quarta colonna, nella sottogriglia più in basso il candidato 3 dovrà risiedere obbligatoriamente nella quinta colonna. Nel secondo caso il candidato 3 sta nella sottogriglia più in alto, nella quinta colonna, obbligando nella sottogriglia centrale l'inserimento del 3 nella quarta colonna. In tutti i casi possibili il 3 viene escluso dalla possibilità di essere inserito nelle celle evidenziate in giallo.

Per questo motivo, l'informazione che un candidato sia presente in due sole colonne in due sottogriglie, ci consente di eliminare il candidato dalle celle in quelle colonne che non appartengono alle sottogriglie che abbiamo appena analizzato.

Se le due sottogriglie che andiamo ad analizzare sono allineate orizzontalmente dobbiamo verificare che i candidati siano presenti in due sole righe. Se le sottogriglie sono allineate verticalmente, come nell'esempio, dobbiamo verificare che siano su due sole colonne.

Tertium non datur[modifica | modifica wikitesto]

A differenza delle precedenti, questa tecnica è applicabile a qualsiasi gruppo (colonna, riga o sottogriglia). Si basa sul postulato che all'interno di un gruppo in n celle devono esistere esattamente n numeri, da cui per il corollario pragmatico della scelta è possibile ridurre il numero di candidati nelle celle del gruppo.

Sia ogni casella libera rappresentata dalla sequenza dei suoi n candidati, così riportati {x1 ...,xn}

1. se in un gruppo la stessa sequenza di n candidati è presente n volte, allora i candidati di questa possono essere esclusi dalle altre caselle

Si prende il seguente schema di candidati per cella:

{4,5} {4,7,9} {4,5} {7,9} {4,5,9,1}

nell'esempio, solo due caselle hanno la stessa sequenza di due candidati {4,5}, possiamo quindi escludere tali candidati dalle altre caselle, semplificando così le possibili soluzioni:

{4, 5} {7, 9} {4, 5} {7, 9} {9, 1}

poiché il 4 e il 5 sono obbligati ad essere nelle due caselle individuate; se, infatti, uno di essi fosse in una casella differente, si arriverebbe ad una situazione con una caselle rimarrebbe vuota. Abbiamo ora con altre due caselle che possono ospitare la sequenza {7,9}, quindi:

{4, 5} {7, 9} {4, 5} {7, 9} {1}

trovando così una soluzione.

La risoluzione vale anche per compresenze triple, quadruple e così via:

{4, 5, 7} {4, 5, 7} {4, 5, 7} {1, 4, 5, 7, 9} {1, 4, 5, 7, 9}

è evidente che le prime tre caselle presentano tutti i medesimi candidati (4, 5 e 7) e dunque questi possono essere solo in queste tre caselle. Di conseguenza, semplificando, avremo: {4, 5, 7} {4, 5, 7} {4, 5, 7} {1, 9} {1, 9}.

La regola vale anche se i gruppi non sono completi: se n numeri e non altri appaiono almeno una volta in uno di n gruppi allora questi numeri non possono apparire in altri gruppi. Per esempio nei 5 gruppi seguenti

{4, 5} {4, 7} {5, 7} {1, 4, 5, 7, 9} {1, 4, 5, 7, 9}

4, 5 e 7 appaiono pur non completamente nei primi tre gruppi e in assenza di altri numeri, quindi essi non possono apparire nei due gruppi rimanenti:

{4, 5} {4, 7} {5, 7} {1, 9} {1, 9}.

Al limite questa regola funziona anche a schemi completi. Consideriamo i gruppi seguenti:

{4} {7} {5} {1} {9}

Applichiamo la regola p.es. ai primi 3 gruppi: 4, 7 e 5 appaiono da soli almeno una volta nei primi tre gruppi e quindi non appaiono nei due seguenti.

2. Se in un gruppo gli stessi n candidati sono presenti esattamente nelle stesse n sequenze, allora è possibile escludere gli altri candidati da tali caselle

Nell'esempio che segue il 5 ed il 9 compaiono solo nella prima e quarta cella, quindi

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

Tornei[modifica | modifica wikitesto]

Il primo campionato mondiale di Sudoku si è tenuto a Lucca dal 10 all'11 marzo 2006,[12] ed è stato vinto dalla concorrente ceca Jana Tylova.[13][14]

La selezione italiana per il campionato mondiale, valido anche come primo campionato italiano, è avvenuta sempre a Lucca, il 4 marzo 2006, ed è stata vinta da Giulia Franceschini, di Venezia. Al secondo posto si è classificato Gabriele Quaresima, di Cori, mentre al terzo si è piazzato Gabriele Simionato, di Torviscosa.[15] Ad organizzare il primo campionato italiano e il primo campionato del mondo è stata la Nonzero s.r.l.[16] ed in entrambi i casi a dirigere il torneo è stato Paolo Fasce,[17] chiamato da Riccardo Albini in quanto autore di A scuola di Sudoku per Edizioni Sonda. La prima nazionale italiana di sudoku contava sei membri: oltre ai tre già citati ne facevano parte Francesco Aricò, di Firenze, Anna Magagni, di Modena, e Martino Nacca, di Atripalda.[18]

Vincitori del campionato italiano[modifica | modifica wikitesto]

  • 2006: (Lucca) Giulia Franceschini[19]
  • 2007: (Lucca) Elena Mazzini[19]
  • 2008: (Lucca) Gabriele Simionato[19]
  • 2009: (Lucca) Gabriele Simionato[19]
  • 2010: (Lucca) Elena Mazzini[19]
  • 2011: non disputato[19]
  • 2012: (Modena) Giovanni Frugoli[19]
  • 2013: non disputato[19]
  • 2014: (online) Giovanni Frugoli[19]
  • 2015: (Marina di Carrara) Gianluca Mancuso[19]
  • 2016: (Modena) Gianluca Mancuso
  • 2017: (Modena) Gianluca Mancuso
  • 2018: (Sesto San Giovanni) Gianluca Mancuso
  • 2019: (Sesto San Giovanni) Valerio Stancanelli
  • 2020: (online) Valerio Stancanelli
  • 2021: (Vicenza, liceo scientifico Lioy) Giulia Cossutti
  • 2022: (Verona) Laura Tarchetti
  • 2023: (Verona) Laura Tarchetti

Vincitori del campionato del mondo (World Sudoku Championship)[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  1. ^ Florian Stark, Leonhard Euler: Wahrer Erfinder des Sudoku war ein Schweizer, in DIE WELT, 14 aprile 2013. URL consultato il 27 agosto 2021.
  2. ^ a b c d e (EN) Ed, Jr. Pegg, Ed Pegg Jr.'s Math Games: Sudoku Variations, su MAA Online, The Mathematical Association of America, 15 settembre 2005. URL consultato il 25 luglio 2009 (archiviato dall'url originale il 23 luglio 2009).
  3. ^ a b (EN) So you thought Sudoku came from the Land of the Rising Sun ..., su the Guardian, 15 maggio 2005. URL consultato il 27 agosto 2021.
  4. ^ a b Corriere della Sera - Sudoku, nuovo gioco-mania d'Europa, su corriere.it. URL consultato il 27 agosto 2021.
  5. ^ (FR) Les ancêtres français du sudoku
  6. ^ (EN) Jack Malvern, Les fiendish French beat us to Su Doku, in Times Online, 3 giugno 2006. URL consultato il 16 settembre 2006.
  7. ^ (EN) Word of the Year, su languages.oup.com. URL consultato il 10 febbraio 2023.
  8. ^ A107739 - OEIS, su oeis.org. URL consultato il 27 agosto 2021.
  9. ^ Frazer Jarvis, Ed Russell, There are 5472730538 essentially different Sudoku grids ... and the Sudoku symmetry group, su Frazer Jarvis's home page, 7 settembre 2005. URL consultato il 16 settembre 2006 (archiviato dall'url originale il 4 ottobre 2006).
  10. ^ A109741 - OEIS, su oeis.org. URL consultato il 27 agosto 2021.
  11. ^ (EN) Sudokus and bimagic squares Archiviato il 3 dicembre 2006 in Internet Archive.
  12. ^ Agenda 1º Campionato Mondiale Sudoku 2006, su wsc2006.com. URL consultato il 25 luglio 2009 (archiviato dall'url originale il 19 luglio 2008).
  13. ^ (EN) Home page ufficiale 1º Campionato Mondiale Sudoku 2006 Archiviato il 21 marzo 2006 in Internet Archive.
  14. ^ (EN) Sudoku title for Czech accountant, 11 marzo 2006. URL consultato il 27 agosto 2021.
  15. ^ Classifica selezione italiana 1º Campionato Mondiale Sudoku 2006, su wsc2006.com. URL consultato il 25 luglio 2009 (archiviato dall'url originale il 19 luglio 2008).
  16. ^ nonzero, su nonzero.it. URL consultato il 27 agosto 2021.
  17. ^ Il diagramma della finale del Campionato del Mondo 2006 risolto passo passo: Corso a Matefitness, su fasce.it. URL consultato il 26 gennaio 2013 (archiviato dall'url originale il 1º maggio 2013).
  18. ^ Risultati 1º Campionato Mondiale Sudoku 2006, su wsc2006.com. URL consultato il 25 luglio 2009 (archiviato dall'url originale il 7 settembre 2009).
  19. ^ a b c d e f g h i j Campionato Italiano Sudoku Archiviato il 13 ottobre 2008 in Internet Archive.
  20. ^ (EN) 1st World Sudoku Championship Archiviato il 17 febbraio 2009 in Internet Archive.
  21. ^ (EN) 2nd World Sudoku Championship Archiviato il 17 febbraio 2009 in Internet Archive.
  22. ^ (EN) 3rd World Sudoku Championship Archiviato il 30 gennaio 2009 in Internet Archive.
  23. ^ (EN) 4th World Sudoku Championship Archiviato il 17 febbraio 2009 in Internet Archive.
  24. ^ (EN) 5th World Sudoku Championship
  25. ^ a b (EN) http://www.wscwpc.ini.hu/
  26. ^ (EN) http://wscwpc2013.sudoku.org.cn/ Archiviato il 25 maggio 2014 in Internet Archive.
  27. ^ (EN) http://www.uk2014.org
  28. ^ (EN) http://www.wscwpc2015.org/
  29. ^ (EN) http://www.slovakia2016.org Archiviato il 26 novembre 2018 in Internet Archive.

Bibliografia[modifica | modifica wikitesto]

  • Jean-Paul Delahaye, "La scienza del Sudoku", Le Scienze, agosto 2006
  • Kim, Scott, "The Science of Sudoku", 2006
  • Andrea Cattania Il mio Sudoku ISBN 978-88-6393-177-8

Voci correlate[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]


Controllo di autoritàLCCN (ENsh2005003630 · J9U (ENHE987007549557905171
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica