Il gioco giapponese del sudoku, affonda le sue radici nei quadrati magici studiati da Eulero.
Un quadrato magico è uno schieramento di numeri interi distinti in una tabella quadrata tale che la somma dei numeri presenti in ogni riga, in ogni colonna e in entrambe le diagonali dia sempre lo stesso numero; tale intero è denominato la costante magica del quadrato.
Il Sudoku si e’ subito diffuso in tutto il mondo, come era gia’ successo per il cubo di Rubik, il gioco del 15 e altri puzzles che periodicamente ritornano di moda.
Le regole sono molto semplici e occorre soltanto una matita e un foglio di carta. Si gioca su una tabella di nove per nove caselle in ognuna delle quali si deve inserire una cifra, da uno a nove. Ogni riga e ogni colonna deve contenere tutte le cifre da uno a nove senza ripetizioni. Condizione ulteriore, e questa è la novità, anche ogni blocco di caselle tre per tre, contrassegnato da linee più marcate, deve contenere le nove cifre, senza ripetizioni. Il Sudoku si presenta con una parte delle cifre già inserite nelle caselle (vedi figura 1). Per essere un vero Sudoku, deve inoltre avere un’unica soluzione. Richiede normalmente dai dieci minuti alla mezz’ora per essere risolto. Il nome originale del gioco, lanciato vent’anni fa dalla Nikoli, una casa editrice giapponese specializzata in giochi, era Suji wa dokushin ni kagiru ovvero “Numeri limitati ad una sola persona”, un nome sintetizzato in Sudoku, “Numeri unici”.
Figura 1: Raffigurazione di un sudoku come si presenta al giocatore e la usa soluzione.
Per risolvere un Sudoku, esistono diverse tecniche a seconda della difficolta’ del Sudoku stesso. Una delle tecniche piu’ semplici e’ quella della “Singola posizione”.
Si sceglie una riga, una colonna o un box (il quadrato 3x3) e si analizzano i numeri che ancora non sono stati inseriti. A causa della presenza dei numeri iniziali, le posizioni dove poter inserire un nuovo numero sono limitate. Spesso ci sono 2 o 3 celle dove poter inserire un numero ma se si e’ fortunati ce ne sara’ solo una. Per esempio nel sudoku della figura 2, scegliendo la riga verde si vede subito che il numero 7 puo’ essere inserito solo sull’ultima celle verde verso destra.
Questo perche’ in qualsiasi altra cella verde lo avremmo inserito avrebbe generato delle colonne con due cifre 7.
Figura 2: Tecnica della singola posizione.
Un'altra tecnica semplice e’ quella del “singolo candidato”. In questo caso ce' bisogno di una matita per scrivere in ogni cella i possibili candidati, esaminando le colonne, righe e box circostanti. Nel caso in cui il candidato e’ unico, immediatamente puo’ essere associato alla cella. In figura 3, viene mostrato un esempio di questa tecnica.
Figura 3: Tecnica del singolo candidato (da sinistra verso destra).
Nella cella indicata in verde nel sudoku di centro, l’unico candidato e’ il 2, mentre nella cella sopra quella contenente il numero 8, i possibili candidati sono 1 e 2. A destra viene mostrato il sudoku dopo l’inserimento di tutti i candidati. Si vede immediatamente che, ci sono 3 celle (in verde) dove c’e’ un unico candidato che quindi puo’ essere associato definitivamente alla cella.
Esiste una tecnica che non dice quale numero inserire in una cella, ma aiuta invece a determinare quali sono le celle dove non e’ possibile inserire un numero. Con l’esempio riportato in figura 4, e’ facile capire come funziona questa tecnica chiamata la tecnica delle linee candidate.
Figura 4: Tecnica della singola linea (da sinistra verso destra).
Nel quadrato indicato in verde ci sono due possibili celle (indicate in verde piu’ scuro) dove poter inserire il numero 4. Questo automaticamente fa si che e’ possibile rimuovere qualsiasi altro 4 lungo la colonna individuata dai due 4 del box in basso a sinistra come mostrato in figura 4 nelle ultime due griglie a destra.
Esistono altre tecniche simili che qui non vedremo.
Ma nel caso in cui il Sudoku sia particolarmente complicato quale tecnica usare? Ce ne sono alcune che sono molto semplici da capire ma complicate da applicare. Partiamo con la prima, la cosiddetta tecnica delle “catene forzate”. Per applicarla e’ necessario avere a disposizione piu’ di un foglio per prendere appunti.
Figura 5: Tecnica della catena forzata (da sinistra verso destra).
Osservando la figura 5, si capisce in che modo la scelta del valore 1 nella cella C3R1 (colonna terza e riga 1) forza il valore della cella C1R4 a 5. Infatti nel primo passaggio la scelta iniziale del 1, forza il valore 4 nella cella C3R4, che a sua volta forza il valore 7 nella cella C6R4 e quindi il valore 5 nella cella C1R4.
Si ripete poi la stessa operazione ma anziche’ partire col numero 1, si parte col numero 2 (vedi figura 6).
Figura 6: Tecnica della catena forzata (da sinistra verso destra).
In questo caso la catena che viene fuori e’ molto lunga, ma alla fine forza sempre il numero 5 nella cella C1R4. Poiche’ due diverse scelte portano allo stesso numero nella cella C1R4 questo significa che il 5 e’ il numero da associare a questa cella.
La seconda tecnica normalmente utilizzata per risolvere Sudoku complessi e’ quella che va sotto il nome di X-Wing. Osserviamo la figura 7, partendo dalla riga 4 e 9 dove abbiamo 4 celle con il 6 un possibile candidato.
Figura 7: Tecnica X-Wing
Il trucco per capire la tecnica del X-Wing e’ quello di immaginare cosa succederebbe se uno scegliesse il 6 in una di queste quattro celle. Se scegliamo il 6 in C3R4 questo implica che non e’ possibile avere lo stesso numero in C9R4 e C3R9 come si puo’ vedere dalla griglia centrale in alto della figura 7. Questa scelta forza la cella C9R9 ad avere 6 come candidato. In altre parole un 6 nella cella in alto a sinistra del quadrato iniziale (vedi griglia in basso a sinistra) forza lo stesso valore nella cella in basso a destra. Esattamente con la stessa logica, un 6 nell’angolo in alto a destra del quadrato dovrebbe forzare lo stesso valore nella cella in basso a sinistra (vedi griglia centrale in basso della figura 7). Detto cio’ e’ chiaro che non e’ possibile avere altri 6 nelle due colonne C3 e C9. Questo ci permette di cancellare quasiasi numero 6 che compare come possibile candidato. Nell’esempio di figura 7, e’ possibile rimuovere il 6 da due celle della colonna C9, che lascia la cella C9R1 con un 8.
A causa della grande popolarita’ del Sudoku, diversi matematici e scienziati del computer hanno lavorato su diverse questioni emerse da questo gioco. La prima di queste riguarda il possibile numero di griglie. In altre parole, stabilire qual’e’ il numero di griglie possibili di Sudoku che possono essere create o equivalentemente il numero di modi in cui e’ possibile riempire una griglia 9x9 con i numeri da 1 a 9 soddisfando le regole del Sudoku.
Per rispondere a tale domanda e’ necessario utilizzare tutte le possibili permutazioni e le proprieta’ di simmetria della griglia del Sudoku.
Bertram Felgenhauer del Dipartimento di Scienza dei computer dell’Universita’ di Dresda e Frazer Jarvis del Dipartimento di Matematica dell’Universita’ di Sheffield in Inghilterra, usando la forza-bruta dei computer sono arrivati a calcolare il numero di griglie valide di Sudoku. Un numero veramente grande: 6670903752021072936960 (circa 6.67*1021). Senza considerare le regole del Sudoku elencate all’inizio del capitolo, il numero di possibili griglie sarebbe 981 . Ovviamente per contare le possibili griglie questo numero dovrebbe essere ridotto eliminando tutte quelle configurazioni che non soddisfano le regole.
Se consideriamo un qualsiasi blocco del Sudoku, questo puo’ avere 9! (362880) possibili configurazioni. I possibili modi con cui arrangiare la “banda” in alto (l’insieme dei tre blocchi da 3x3 celle) saranno dati dal prodotto di 9! del primo blocco per il numero di modi in cui e’ possibile arrangiare il blocco 2 della banda superiore e il numero di modi in cui e’ possibile arrangiare il blocco 3 (quello a destra in alto della griglia del Sudoku).
Questo prodotto e’ uguale a 6.67*1021. Comunque se consideriamo la simmetria della griglia del Sudoku questo numero e’ destinato a diminuire. Per simmetrie, intendiamo quelle operazioni che quando applicate alla griglia del Sudoku, esse creano un’altra griglia che e’ essenzialmente equivalente all’originaria. Per prima cosa etichettiamo una griglia del Sudoku come riportato in figura 8.
Figura 8: Griglia del Sudoku etichettata con le lettere.
La colonna ADG e’ chiamata una “pila”, mentre la riga ABC e’ detta una “striscia”.La selezione di specifici valori per uno qualsiasi dei quadrati e’ conosciuta come “Ri-etichettatura”. L’arrangiamento delle cifre da 1 a 9 nel blocco A, e’ un esempio di operazione di ri-etichettatura. Oltre questa operazione, sono possibili anche le:
· Permutazioni delle “strisce”
· Permutazioni delle “pile”
· Permutazioni delle colonne all’interno delle “pile”
· Permutazioni delle righe all’interno delle “strisce”
· Riflessione o rotazione della griglia.
Frazer Jarvis e Ed Russel, in un lavoro intitolato “Mathematics of Sudoku”, hanno individuato 3359323 simmetrie. Una di queste e’ quella rappresentata in figura 9, dove la griglia riportata rimane praticamente la stessa se sottoposta ad una rotazione di 90 gradi e di ri-etichettatura 1—>3—>9—>7—>1 e 2—>6—>8—>4—>2. Il 5 rimane fisso.
Figura 9: Griglia di Sudoku che rimane la stessa in seguito ad operazione di rotazione e ri-etichettatura
Tenendo conto di tutte le simmetrie, gli autori sono arrivati a stabilire che tutte le possibili griglie differenti del Sudoku sono 5472730538.
Normalmente, il Sudoku deve avere una sola soluzione, altrimenti il puzzle non e’ valido. Per essere sicuri di cio’, i puzzles sono presentati con un numero di cifre gia’ presenti nella griglia iniziale, lasciando al giocatore la deduzione delle rimanenti cifre da inserire nelle celle libere. Al momento il migliore risultato ottenuto sul minimo numero richiesto nella griglia iniziale e’ di 17 cifre. Questo e’stato ottenuto dal professore Gordon Royle dell’Universita’ dell’Australia. Attualmente non si sa se con 16 cifre iniziali il Sudoku ammette una singola soluzione. Tutte le griglie con 17 entrate iniziali, vengono chiamate i Sudoku minimi. Al momento si conoscono 47793 diversi Sudoku minimi.
Per analizzare il gioco del Sudoku e’ possibile anche utilizzare la teoria dei grafi. E’ quello che hanno fatto Agnes M. Herzberg e M. Ram Murty in un loro lavoro apparso sul giornale Notices of the AMS di Giugno/Luglio 2007. E’ possibile pensare alla griglia del Sudoku, come agli 81 nodi di un grafo. Ogni cifra da 1 a 9 puo’ essere colorato in modo diverso, e due nodi possono essere connessi se e solo se le due celle che essi rappresentano si trovano nella stessa riga, colonna o quadrato 3x3. Poiche’ nessuna riga, colonna o blocco 3x3 puo’ contenere piu’ di una volta lo stesso numero, questo significa che il grafo non avra’ connessioni tra nodi dello stesso colore. Nel linguaggio della teoria dei grafi, un grafo colorato senza connessioni tra nodi dello stesso colore si chiama un “grafo colorato proprio”.
Quello che i giocatori di Sudoku, quindi, fanno tutti i giorni, e’ cercare di estendere un grafo parzialmente-colorato (la griglia iniziale) ad un grafo colorato proprio.
Grazie a questa analogia tra Sudoku e grafi, Herzberg e Murty hanno utilizzato le tecniche dei grafi per provare alcuni teoremi riguardanti il Sudoku.
Per esempio, hanno provato che il numero di modi per trasformare un grafo parzialmente colorato e’ dato da un polinomio. Se il valore di questo polinomio e’ zero per una certa griglia Sudoku, allora il puzzle non ha soluzione. Se il valore e’ 1, allora il puzzle ha una sola soluzione e cosi via. Essi hanno anche dimostrato che affinche’ un Sudoku abbia un’unica soluzione, ci devono essere almeno 8 delle 9 cifre presenti nella griglia iniziale come entrate. Se vengono dati solo 7 numeri, allora il puzzle ha almeno due soluzioni.
Tenendo presente, quindi, il risultato di G. Royle, per avere un’unica soluzione dobbiamo garantirci che nella griglia iniziale ci siano almeno 17 numeri e che questi siano rappresentati da 8 diverse cifre. Per esempio con una sequenza del tipo:
1, 2, 3, 4, 5, 6, 9, 2, 2, 3, 4, 1, 1, 9, 4, 7, 2
come entrate iniziali il puzzle avra’ sicuramente una soluzione unica.
E’ possibile pensare che nel caso ci sia un numero di entrate superiore a 17, sia abbastanza probabile avere un’unica soluzione del Sudoku. E invece non e’ sempre cosi. L’articolo di Herzberg e Murty, riporta un esempio di una griglia con 29 numeri iniziali che ha due differenti soluzioni. Niente male per un rompicapo come il Sudoku. Un altro ricercatore, David Eppstein dell’Universita’ della California, ha applicato anche lui la teoria dei grafi per costruire nuovi metodi di soluzione.
Supponiamo di avere un Sudoku che e’ stato risolto parzialmente. Assegniamo ad ogni cella vuota un nodo del grafo, e connettiamo i nodi con archi etichettati coi numeri candidati per la cella. Eppstein definisce un ciclo non ripetitivo, un tour chiuso che non ha due archi (edge) consecutivi con la stessa etichetta e ciclo ripetitivo uno in cui e’ possibile trovare due archi consecutivi con la stessa etichetta. I connettori consecutivi sono quelli che condividono uno stesso nodo (per esempio A e B sotto).
Vediamo come funziona il metodo nel caso di cicli non ripetitivi. In questo caso, per qualsiasi cella C del ciclo, con due archi etichettati con A e B che insistono su di essa, il valore di C puo’ essere solo A o B. Nell’esempio della figura 10, la cella C e’ quella sulla sinistra in basso della griglia. Poiche’ i due archi che insistono su questa cella hanno come numeri 2 e 3 significa che la cella C dovra’ avere uno di questi due numeri. La griglia in alto a sinistra e’ il Sudoku parzialmente completato con altri metodi. In basso a destra invece viene mostrato il puzzle risolto.
Figura 10: Metodo del ciclo non ripetitivo di Eppstein.
In caso di ciclo ripetitivo, se ad un nodo confluiscono due archi con la stessa etichetta, la cella associata al nodo del grafo non puo’ che avere come valore l’etichetta delle connessioni. Nell’esempio di figura 11, il nodo indicato in nero non puo’ che avere come valore il numero 4.
Figura 11: Metodo del ciclo ripetitivo di Eppstein.
