Il Sudoku è uno dei giochi più popolari dei giorni nostri. Un'importante domanda che intriga gli scienzati è il numero minimo di indizi, in un puzzle di Sudoku, con soluzione unica. Ad Ottobre 2009, Gordon Royle aveva collezionato 49151 indizi nel puzzle da 17 tra i quali nessuno era isomorfico con un altro (per isomorfismo si intende tradurre l'enigma semplicemente ruotando, specchiando o communtando le cifre). Tuttavia, finora, nessun indizio per un puzzle a 16 caselle è stato trovato con successo o ha dato indizio che ne esista uno.
Gary McGuire, professore dell'Università Nazionale dell'Irlanda, ha presentato un approccio di ricerca per risolvere gli indizi dei puzzle a 16 caselle. Ha inoltre sviluppato un programma, chiamato CHECKER, per provare a risolverli. Secondo la loro analisi sperimentale, il programma richiede circa 300'000 anni su un core di una CPU Intel(R) Xeon(R) Questo indirizzo email è protetto dagli spambots. È necessario abilitare JavaScript per vederlo.. (Nota: utilizzeranno un core per indicare la potenza di elaborazione). Il suo commento finale fu: "Abbiamo bisogno in un notevole passo in avanti nella nostra comprensione per rendere possibile la ricerca di tutti". Hanno bisogno o di ridurre lo spazio di ricerca o di trovare un miglior algortimo di ricerca (vedere Scientific American 2006).
Nelle loro recenti ricerche, hanno proposto alcuni nuovi algoritmi e raffinato il codice aumentando la velocità di 128 volte. Così, in accordo con i loro esperimenti, il loro nuovo programma può risolverlo, su un core, in 2417 anni. Così è diventato fattibile risolvere il problema aperto. Per esempio, se 2417 core sono utilizzati via BOINC, il problema aperto può essere risolto in un anno e, se sono utilizzati 24170 core, può essere risolto in 36 giorni. (Il loro benchmark può essere scaricato qui e ci sono due impostazioni: 100 griglie e 10000 griglie per la verifica).
Ringraziano sinceramente per aver donato le vostre risorse di elaborazione a sudoku@vtaiwan. Il vostro contributo sarà molto di aiuto per risolvere questo problema aperto.
Potreste essere i primi a trovare un puzzle del sudoku a 16 celle.
V-TAIWAN PROJECT
V-Taiwan o Volontari-Taiwan è un progetto di elaborazione volontaria finanziato dal National Science Council (NSC) di Taiwan. Il progetto, annunciato su Internet, è di applicare il calcolo volontario alle applicazioni per giochi dei computer. Attualmente hanno avuto successo utilizzando il calcolo volontario per risolvere diverse aperture Connect6 come riportato nelle pubblicazioni sotto. Tra queste aperture, uno dei più popolari è stato chiamato Mickey Mouse Opening (sin dall'apertura vedrete una faccia di Mickey Mouse).
REFERENZE:
- I-Chen Wu, Chingping Chen, Ping-Hung Lin, Guo-Zhan Huang, Lung-Ping Chen, Der-Johng Sun, Yi-Chih Chan, and Hsin-Yun Tsou, "A Volunteer-Computing-Based Grid Environment for Connect6 Applications", The 12th IEEE International Conference on Computational Science and Engineering (CSE-09), August 29-31, Vancouver, Canada, 2009.
- I-Chen Wu, H.-H. Lin, P.-H. Lin, D.-J. Sun, Y.-C. Chan and B.-T. Chen, "Job-Level Proof-Number Search for Connect6", The International Conference on Computers and Games (CG 2010), Kanazawa, Japan, September 2010.
- I-Chen Wu and Ping-Hung Lin, "Relevance-Zone-Oriented Proof Search for Connect6", the IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2, No. 3, September 2010.
- H.-H. Lin, I-Chen Wu, "Solving the Minimum Sudoku Problem", The International Workshop on Computer Games (IWCG 2010), Hsinchu, Taiwan, November 2010.