Sudoku : il numero di Dio è il 17

Trovare il numero di Dio del sudoku è la sfida con la quale per anni si sono confrontati matematici e scienziati : quale è il numero più basso di indizi che possono essere dati affinchè la griglia contenga un’unica soluzione ?

I sudoku sui giornali hanno in media una ventina di indizi. Quelli che ne hanno di meno non scendono sotto i 17 indizi. Lo ha confermato il matematico Gordon Royle, dopo aver esaminato circa 50mila griglie sudoku : nessuna ha meno di 17 indizi.
La supposizione di Royle è stata convalidata dagli scienziati Gary McGuire, Bastian Tugemann e Gilles Civario. Hanno messo a punto un algoritmo e un programma capaci di analizzare una griglia contenente 81 numeri per determinare se può o non può essere risolta con soltanto 16 indizi.

Sono molti i numeri nascosti dietro questo gioco apparentemente semplice. Le griglie possibili sono infatti 6 670 903 752 021 072 936 960 (ossia circa 6’671 miliardi di miliardi di griglie).
Fortunatamente per i tre ricercatori non tutte devono essere analizzate perchè molte sono varianti di un’unica configurazione.
Se – ad esempio – in una griglia si sostituiscono tutti gli 1 con un 7, il sudoku che ne risulterà sarà diverso ma la sua struttura geometrica resterà la stessa.
Le trasformazioni possibili sono numerose. Si possono invertire la prima e la seconda linea, oppure le due prime colonne, spostare in basso o in mezzo le tre file in alto, girare la griglia di un quarto di cerchio, vederla riflessa in uno specchio, ecc..
E’ stato così mostrato che tutte le griglie possibili possono essere ridotte 5 472 730 538 (sia oltre una divisione di oltre mille miliardi).

In seguito per ognuno di questi modelli va verificato se una combinazione di 16 indizi è sufficiente per avere un’unica soluzione del sudoku. Ogni volta esistono circa 34 milioni di miliardi di queste combinazioni.
In un articolo pubblicato nel 2006 nella rivista Scientific magazine, Gary McGuire scriveva che se ognuna di queste combinazioni potesse essere analizzata in 1 secondo, ci vorrebbero 173 anni per esaminarle tutte.
I ricercatori hanno cercato di fare un lavoro di semplificazione teorica e nelle griglie hanno individuato giochi di indizi inevitabili (oppure obbligatori) senza i quali il sudoku non potrebbe essere risolto.
Effettuando centinaia di sessioni durante l’intero 2011, hanno lavorato con il super computer Stokes, del Irish Centre for High-End Computing.
In totale hanno accumulato l’equivalente di 7.1 milioni di ore di calcolo e mostrato che con soli 16 indizi, nessuno dei 5 472 730 538 modelli di griglie poteva avere un’unica soluzione.
Il 17 è dunque senza ombra di dubbio il numero di Dio del sudoku.