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
Si tratta di una patologia rara e difficile da trattare. Colpisce prevalentemente gli uomini e…
Secondo gli autori di un recente studio potrebbe contenere informazioni sul sesso e sul concepimento,…
Dopo il segnale incomprensibile, gli scienziati hanno riparato il danno a uno dei computer di…
L’Aifa ha approvato l’estensione della rimborsabilità del trattamento, che era già stato approvato per l'atrofia…
Resistono alle radiazioni potenziando la loro capacità di riparare i danni al dna. Piccolo aggiornamento…
Mai così tanti casi di leptospirosi in un anno dal 2001: a contribuire all’aumento delle…
Questo sito o gli strumenti di terze parti in esso integrati trattano dati personali (es. dati di navigazione o indirizzi IP) e fanno uso di cookie o altri identificatori necessari per il funzionamento e per il raggiungimento delle finalità descritte nella cookie policy.
Leggi di più
Visualizza i commenti
7.1 milioni di ore di calcolo = 810.5 anni
Mi sfugge qualcosa?