Che fosse un numero magico, come molti dei numeri primi, non era in discussione neanche prima. Ma ora il 17 assume un’aura ancora più potente grazie a uno studio irlandese che spiega come questo sia il numero minimo di indizi necessari per risolvere un Sudoku. Gli indizi sono, in questo caso, alcuni numeri da cui partire, già posizionati in alcune caselle. Per dimostrare che con 16 o meno indizi non si arriva a una soluzione univoca, Gary McGuire e il suo team dello University College di Dublino hanno impiegato 7,1 milioni di ore di calcolo all’Irish Centre for High-End Computing.
Infatti, i ricercatori hanno dovuto controllare tutte le possibili griglie con 16 indizi, all’incirca 6.670.903.752.021.072.936.960 schemi (circa 6.671 miliardi di miliardi). Fortunatamente, come spiegano su Arxiv, gli studiosi irlandesi hanno potuto fin da subito ridurre il numero alla minore – seppure sempre considerevole – cifra di 5.472.730.538. Questa riduzione è stata possibile grazie a un algoritmo, detto di forza bruta, in grado di identificare tutti quegli schemi a geometria uguale (quelli in cui numeri diversi, per esempio 6 e 9, occupano le stesse posizioni: la soluzione finale sarà diversa, ma la geometria è identica). Questi ultimi schemi portano quindi a soluzioni multiple.
Successivamente i ricercatori hanno controllato, grazie a un programma chiamato Checker, i 5,5 miliardi di schemi restanti, impiegando praticamente tutto il 2011. Il 1 gennaio di quest’anno hanno finalmente pubblicato online i risultati di tutti questi milioni di ore di calcolo: non esistono schemi a sedici indizi che abbiano una soluzione univoca. Il minimo sono diciassette.
La tesi di McGuire ha ottenuto un discreto consenso a una recente conferenza di matematici appena conclusasi a Boston, dove è stata presentata pubblicamente per la prima volta dai ricercatori irlandesi. Tuttavia, a chi non ama la matematica pura, e cerca un’applicazione pratica di studi e teorie, potrebbe sembrare uno studio che lascia il tempo che trova. Per questo motivo gli scienziati sottolineano il fatto che il loro metodo di ricerca e il loro algoritmo potrebbero trovare facile applicazione in tutti quei campi in cui è necessario esaminare enormi quantità di dati, come il sequenziamento dei genomi o l’analisi dell’espressione genica, ma anche per testare nuovi software.
Riferimenti: Nature doi:10.1038/nature.2012.9751
Arxiv
Credits immagine a Olivander via Flickr
7.1 milioni di ore di calcolo = 810.5 anni
Mi sfugge qualcosa?