Galileo Giornale di scienza e problemi globali

23 Febbraio 2012 | ultimo aggiornamento circa 14 ore fa
Temi fisica e matematica

17 indizi per risolvere il Sudoku

1
di Caterina Visco | Pubblicato il 10 Gennaio 2012 10:56
Detail-sudoku

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

tags: matematica, giochi, computer

Leggi anche

Commenti lascia un commento

  • di Emanuele , il 12 Gennaio 2012 14:29
    7.1 milioni di ore di calcolo = 810.5 anni Mi sfugge qualcosa?

Lascia un commento

Autore

Caterina Visco

Little-n657142005_1016243_7576

Laureata in Scienze Biologiche, ha lavorato come web content editor per il portale medico Yahoo!Salute. Nel 2009, dopo uno stage a Internazionale, approda a Galileo, dove, oltre contribuire alla produzione dei contenuti, è community manager e coordinatrice della redazione. Scrive per diverse testate giornalistiche tra cui L'espresso, Wired, Le Scienze, Mente e Cervello, Nova - Sole 24 ore, Il Venerdì di Repubblica.


Vai alla pagina dell'autore

Oggi su Galileo

Sondaggio

Nature ha stilato una lunga lista di fattori che possono determinare il successo di una carriera nell’ambito della ricerca scientifica. Tra questi, la capacità di produrre pubblicazioni, di sviluppare metodi originali, ma anche la qualità delle infrastrutture. Secondo voi, oltre alla disponibilità adeguata di finanziamenti e retribuzioni, qual è l'ingrediente fondamentale che consente di fare ricerca nel modo migliore?

risultati

Segui Galileo su

Galileo Servizi Editoriali

Parole per la scienza

Galileo servizi editoriali è un service giornalistico che realizza inchieste per le principali testate italiane, sviluppa progetti di comunicazione per le aziende e gli enti di ricerca, produce formazione universitaria, organizza mostre, eventi, conferenze, realizza pubblicazioni su carta e siti web. vai al sito di Galileo Servizi Editoriali
  • Madri dopo la chemio L'ESPRESSO
  • Training d'oro VELVET DI MARZO
  • Le vie della chimica SAPERE DI FEBBRAIO
  • Epatite C sei in trappola L'ESPRESSO
  • Il cuore al centro LE SCIENZE
  • Giochi da primate NATIONAL GEOGRAPHIC KIDS

Partners