Il Sudoku
La parola “Sudoku” deriva dal giapponese 「数字は独身に限る]
(Sūji wa dokushin ni kagiru), che si traduce letteralmente come:
“I numeri devono essere solitari”
È uno dei puzzle logici più popolari al mondo, ma dietro la sua apparente semplicità si nasconde una profonda complessità matematica.
Infatti troppe volte ho risolto sudoku ma poi mi sono chiesto, come si creano i sudoku? Quali posizioni e qual è il numero minimo di numeri affinché sia risolvibile?
Come si genera un Sudoku?
Un Sudoku completo è una griglia 9×9 divisa in nove blocchi 3×3, dove ogni riga, colonna e blocco contiene tutti i numeri da 1 a 9 esattamente una volta.
La generazione di un Sudoku avviene tipicamente in due fasi: prima si crea una griglia completa valida partendo da una griglia vuota e riempendola ricorsivamente con numeri casuali, verificando ad ogni passo che le regole del Sudoku siano rispettate.
Poi si rimuovono alcuni numeri dalla griglia completa per creare il puzzle. La sfida è rimuovere abbastanza numeri da rendere il puzzle interessante, ma non così tanti da renderlo impossibile o con soluzioni multiple.
Qual è il minimo di celle di un Sudoku risolubile?
“If you can figure it out, you will be a rock star in the universe of people who care about such things. Granted, that is a far smaller universe than the one full of people who care about actual rock stars, but still, it would be great.”
–dal libro: “Taking Sudoku Seriously: The Math Behind the World’s Most Popular Pencil Puzzle” di Jason Rosenhouse
Una delle domande più affascinanti sulla matematica del Sudoku è: qual è il numero minimo di celle che devono essere riempite per avere un puzzle con soluzione unica? La risposta, dimostrata nel 2012 da McGuire, Tugemann e Civario nella pubblicazione There is no 16-clue sudoku, è 17 celle.
Gli autori hanno dimostrato questo risultato attraverso un’esaustiva ricerca computazionale, generando e testando miliardi di configurazioni di Sudoku. Hanno dimostrato che nessun Sudoku con 16 o meno celle può avere una soluzione unica, mentre hanno trovato 49.151 Sudoku essenzialmente diversi con esattamente 17 celle (tutti scaricabili qui).
Il motivo profondo per cui 17 è il minimo non è completamente compreso da un punto di vista teorico puro, ma si può intuire che con meno di 17 celle, i vincoli forniti non sono sufficienti a determinare univocamente gli altri 64 numeri.
La struttura combinatoria del Sudoku richiede una certa “densità” di informazione per eliminare tutte le ambiguità.
Ecco un esempio di sudoku con soli 17 elementi, buona fortuna se proverete a risolverlo ahahha
Quanti possibili Sudoku esistono?
Il numero totale di griglie Sudoku 9×9 valide e completamente riempite è:
$$N \approx 6,7 \times 10^{21}$$
Questo numero enorme - più di 6 miliardi di trilioni - supera di gran lunga il numero di secondi trascorsi dalla nascita dell’universo (circa $10^{17}$ secondi).
Due griglie Sudoku sono considerate essenzialmente equivalenti se una può essere trasformata nell’altra attraverso operazioni che preservano la validità del Sudoku. Queste operazioni, chiamate trasformazioni invarianti, includono:
- Permutazione dei numeri: sostituire tutti gli 1 con 5, tutti i 5 con 3, ecc., usando una qualsiasi permutazione dei numeri da 1 a 9
- Scambio di righe all’interno di un blocco: scambiare due righe che appartengono allo stesso gruppo di tre righe
- Scambio di colonne all’interno di un blocco: scambiare due colonne che appartengono allo stesso gruppo di tre colonne
- Scambio di blocchi di righe: scambiare interi gruppi di tre righe
- Scambio di blocchi di colonne: scambiare interi gruppi di tre colonne
- Trasposizione: scambiare righe con colonne (ruotare la griglia)
Queste trasformazioni formano un gruppo matematico chiamato gruppo del Sudoku, di ordine:
$$|G| = 9! \times 6^8 \times 2 = 3.359.232$$
Questo numero rappresenta quante trasformazioni diverse possiamo applicare a un Sudoku. In teoria, se applicassimo tutte queste trasformazioni a una griglia, dovremmo ottenere esattamente 3.359.232 griglie diverse (che sono tutte equivalenti tra loro).
Considerando queste trasformazioni, il numero di griglie essenzialmente diverse si riduce drasticamente a:
$$N_{essenziali} = 5.472.730.538 \approx 5,5 \times 10^9$$
Questo significa che possiamo raggruppare i $6,7 \times 10^{21}$ Sudoku in circa 5,5 miliardi di classi di equivalenza. Se dividiamo il numero totale di griglie per il numero di griglie essenzialmente diverse, otteniamo la dimensione media di una classe di equivalenza:
$$\frac{N}{N_{essenziali}} = \frac{6,7 \times 10^{21}}{5,5 \times 10^9} \approx $$ $$ \approx 9! \times 3.359.058,6$$
Questo numero ci dice che, in media, ogni griglia “essenzialmente diversa” può essere trasformata in circa 1.219.680.506 griglie equivalenti attraverso le trasformazioni invarianti.
Qui emerge un fatto curioso: questo numero ($3.359.058,6$) è leggermente inferiore all’ordine del gruppo del Sudoku ($3.359.232$). Se fosse esattamente uguale, significherebbe che ogni griglia può essere trasformata in esattamente $|G|$ griglie diverse.
Ma dato che è leggermente più piccolo, significa che alcune griglie hanno delle simmetrie speciali: se applichiamo certe trasformazioni a queste griglie, otteniamo la stessa griglia di partenza invece di una nuova griglia.
Per esempio, immagina una griglia Sudoku che rimane identica se la trasponi (scambi righe con colonne). Per questa griglia, applicare la trasposizione non produce una griglia “nuova”, ma la stessa griglia. Quindi queste griglie speciali producono meno di 3.359.232 griglie diverse quando applichiamo tutte le trasformazioni.
In realtà, ci sono solo 560.151 griglie che hanno questo tipo di simmetrie speciali, circa lo 0,01% del totale.
La stragrande maggioranza delle griglie Sudoku (il 99,99%) non ha alcuna simmetria: ogni trasformazione che applichiamo produce effettivamente una griglia diversa.
Il Sudoku è NP-completo
Un problema è NP-completo se appartiene alla classe NP (Nondeterministic Polynomial time), cioè data una soluzione proposta possiamo verificare rapidamente (in tempo polinomiale) se è corretta, ed è NP-hard, ovvero ogni altro problema in NP può essere ridotto ad esso in tempo polinomiale. La classe NP-completo rappresenta i problemi più difficili nella classe NP. Se si trovasse un algoritmo efficiente (tempo polinomiale) per risolvere un qualsiasi problema NP-completo, si risolverebbero automaticamente tutti i problemi NP, e questo è il famoso problema P vs NP, uno dei sette Problemi del Millennio.
Il problema di decisione associato al Sudoku (“Esiste un modo di completare questa griglia parzialmente riempita rispettando le regole?”) è stato dimostrato essere NP-completo da Takayuki Yato e Takahiro Seta nel 2003.
Dato un Sudoku completo, possiamo verificare in tempo $O(n^2)$ (dove $n=9$) se è valido: basta controllare che ogni riga contenga i numeri 1-9 senza ripetizioni (operazione che richiede $O(n)$ per riga, quindi $O(n^2)$ totale), controllare ogni colonna con la stessa complessità, e controllare ogni blocco 3×3. Inoltre, si può dimostrare che problemi NP-completi noti (come il problema della colorazione di grafi o il Latin Square Completion) possono essere ridotti al Sudoku.
Di seguito trovate un sudoku generato casualmente che potete risolvere a mano, vedere le soluzioni ed eventualmente provare le varie operazioni di equivalenza: scambio righe e colonne dello stesso blocco e permutazione: