Il robot che risolve Sudoku

Il programmatore svedese Hans Andersson ha utilizzato un kit Mindstorms NXT della Lego per sviluppare un robot per risolvere i puzzle di Sudoku. Andersson aveva comprato il gioco Lego per sua figlia ma non riuscì a resistere a giocare anche lui.

Prima, il robot scannerizza il puzzle ed utilizza un sensore ottico per programmare i numeri e le caselle vuote. Il robot scannerizza una riga alla volta. L'immagine offuscata viene convertita in un'immagine binaria in bianco e nero per migliorare la nitidezza della foto. Viene calcolato un valore secondo il metodo Otsu ed è utilizzato per determinare se ogni pixel dell'immagine è bianco o nero.

L'algoritmo del metodo Otsu classifica i pixel (in primo piano o sullo sfondo) e poi determina la soglia ottimale che minimizza la variazione all'interno della classe. Una volta che il puzzle è pianificato (mapped), il robot lo risolve riempendo le caselle vuote. Il metodo effettua un esame sistematico di tutte le soluzioni possibili e abbandona le soluzioni eliminate. Il processore del Lego Mindstorms è troppo lento per utilizzare un algoritmo di backtracking e non consente le funzioni ricorsive. Ma Andersson è riuscito lo stesso a creare un piccolo robot in grado di risolvere i puzzle di Sudoku in pochi minuti.

Scarica subito una copia gratis

Scrivi un commento

Seguici anche sul tuo Social Network preferito!

Send this to a friend