Cerca nel blog

2006/03/10

Fisico risolve per caso Sudoku. Tutti.

Leggo sul Chronicle Online, pubblicazione della Cornell University, una storia molto curiosa che è emblematica di come a volte procede la scienza. Il fisico Veit Elser, che lavora alla Cornell, era alle prese con un problema di elaborazione delle immagini usate in biologia. La sua soluzione è un algoritmo che promette grandi progressi nella microscopia per diffrazione a raggi X, preziosissima nell'analisi delle strutture infinitesimali degli organismi.

Lo stesso algoritmo, tuttavia, ha una conseguenza imprevista: è applicabile al Sudoku, il popolarissimo gioco enigmistico, e in una maniera molto particolare. L'algoritmo risolve qualsiasi Sudoku.

Trovate maggiori dettagli, e un Sudoku da risolvere generato dall'algoritmo, nell'articolo originale (in inglese).

9 commenti:

Anonimo ha detto...

Non so se viene applicato lo stesso algoritmo, ma di risolutori per sudoku ne esistono già da tempo, come riporta questo sito

http://www.terzaghi.it/excel/sudoku.htm

ciao
giovanni

Anonimo ha detto...

si l'arloritmi di risoluzione sono anche banali da scrivere...

Daniele ha detto...

Anche mio fratello ne ha fatto uno quest'estate nel tempo libero. Gira su mac e in genere impiega pochi secondi.

Andrea ha detto...

Ecco come ha fatto a vincere, ha usato l'algoritmo di Elser!

http://www.ansa.it/main/notizie/fdg/200603111754234275/200603111754234275.html

Valse ha detto...

Non voglio fare l'antipatico, ma basta provare tutte le combinazioni, quindi l'esistenza di un algoritmo risolvente è scontata. Più interessante sarebbe capire qual'è la classe di complessità dell'algoritmo, per capire se è sostanzialmente migliore di quelli esistenti.

mother ha detto...

Il problema non è la risoluzione che in genere si trova con un semplice algoritmo che definisce tutte le possibili soluzioni del campo del sudoku e una Subroutine di verifica che accerta quella che è l'unica soluzione del gioco.
Il problema è mettere sotto forma di algoritmo una metodologia intelligiente che permetta di ridurre il campo delle possibili soluzioni da verificare a un numero minore tale che si possa finire entro la giornata.

Vi faccio notare che il sudoku del gioco proposto è a + blocchi della settimana enigmistica ed è a lettere (24 possibili casi) il che aumenta esponenzialmente le possibili soluzioni.
Avere un algoritmo semplice che risolve in 1 anno il sudoku a x blocchi (1..100 blocchi)perchè passa tutte le possibili soluzioni, non è come averne uno che lo risolve in un giorno.

Bye bye

Anonimo ha detto...

Posso chiedervi se qualcuno ha capito come funziona in dettaglio l'algoritmo (ho letto la pagina in inglese, ma non mi pare ci sia scritto niente di specifico) ? Mi piacerebbe capire meglio qual e' l'algoritmo proposto.
Per quel che riguarda la grandezza della tabella non mi sembra niente di eccezionale: pure io sono riuscito a scrivere un programma che risolve i 25x25 del Secolo XIX (giornale di Genova).
Ciao,
DR

Rijk Willemse ha detto...

I am addicted to Sudoku! I made an inventory of methods for solving even the most difficult Sudoku. Start with looking for duo's, it's an eye opener!
Check http://www.sudokuhints.nl/en/ for details.

Good luck!

Madhu ha detto...

Algoritmi simili si usano per risolvere il problema della fase, evidentemente simile al sudoku ma con un miliardo di elementi.
L'articolo originale e'
http://it.arxiv.org/abs/math/0111080
apparentemente pero' questo algoritmo non e' il piu' efficiente nella sua classe:
http://it.arxiv.org/abs/physics/0603201