Algoritmi genetici e sudoku

Algoritmi genetici e sudoku

Introduzione: Un curioso modo di risolvere un sudoku utilizzando un computer.

Cose da fare:  Si tratta di un’applicazione Java che vi permette di far risolvere un sudoku a un computer. Cliccate sulla figura sopra per attivarla. Ci sono 3 sudoku gia’ pronti oppure potete inserirne uno nuovo selezionando “Custom” e cliccando col mouse le caselle da impostare. Dopodiche’ un click su “Solve” e vedrete il computer cercare di risolvere il sudoku.

Cosa succede: Se volete far risolvere un qualsiasi sudoku a un computer potete adottare varie strategie. La piu’ semplice sarebbe quello della “forza bruta” in cui il computer tenta sistematicamente tutte le combinazioni possibili fino a trovare quella giusta. Il computer e’ velocissimo e potrebbe anche funzionare : ma talvolta il numero delle prove da fare e’ cosi’ alto da rendere impraticabile la cosa.

Oppure potete cercare di copiare il modo come lo risolve una persona esperta  magari sfruttando la possibilita’ dei computer di accedere in maniera velocissima ad archivi   di dati sconfinati : e’ praticamente cosi’ che il computer e’ riuscito a superare i campioni di questo gioco.

Infine c’e’ la possibilita’ di usare un algoritmo genetico. Questo assomiglia al primo metodo, solo che si procede per “generazioni” successive cercando, come fa la natura con l’evoluzione, di far sopravvivere solo le combinazioni “piu’ forti” (cioe’ che piu’ si avvicinano alla soluzione). Si cerca inoltre di migliorare di generazione in generazione facendo incrociare le combinazioni scelte. Non e’ detto che il programma arrivi alla soluzione : talvolta puo’ bloccarsi su una combinazione e non riuscire piu’ a convergere. In questo caso conviene riprovare cliccando daccapo su “Solve”. Oppure aumentare il numero di tentativi a ogni generazione (“Population size”).

Il sudoku della figura sopra era di livello avanzato ed e’ stato risolto aumentando la “Population size” a 1000 dopo sole 40 generazioni in tempo brevissimo. Invece con la “Population size” predefinita di 500 dopo un minuto e oltre mille generazioni era ormai bloccato.

Commenti: Dalla stessa pagina iniziale in basso a destra potete far partire 3 altre applicazioni degli algoritmi genetici. Infine cliccando su “User Manual” sopra potete leggere un breve tutorial introduttivo a come programmare algoritmi genetici in Java usando la libreria fornita dall’autore (Watchmaker Framework).

Altri applet di informatica .

Il materiale ha come indirizzo: http://watchmaker.uncommons.org/examples/sudoku.php .
Titolo in inglese: An Evolutionary Sudoku Solver .
Autore : Daniel W. Dyer
© Daniel W. Dyer

Ricerca di pagine che hanno link a questo materiale .

Tweet

Leave a Reply

Your email address will not be published. Required fields are marked *