Ultimo aggiornamento: 15-05-2014
Durante l’ultima sessione di corsi, ho seguito Agoritmi 2, in cui il prof per spiegarci il BackTrack c’ha fatto implementare in python un sudoku solver, basandosi sugli appunti di Norving, che usa backtrack con constraint propagation.
Base
Io ho scritto il programma con una euristica diversa dalla sua: non uso la propagazione dei vincoli (e che lo facevo uguale :P) e non risolvo solo per sottogriglie, ma vado a vedere la colonna o la riga o la sottogriglia che ha il maggior numero di numeri già inseriti e lì vado a tentare l’inserimento di un nuovo numero, ovviamente il tutto ottimizzato usando le hash table (usando la funzione set in python) in modo da non contare ogni volta il numero di elementi presenti.
Con questi meccanismi rapportato all’algoritmo di Norving “mi difendo”, non ho performance così elevate, però riesco a risolvere i suoi hardest sudoku anche in 0.03 secondi, ma a volte anche di più (parlo di secondi e molti a volte):
Solution computed . . . 9 2 . . . . 3 8 7 9 2 6 4 1 5 . . 6 8 . 3 . . . 5 4 6 8 1 3 9 7 2 1 9 . . 7 . . . 6 1 9 2 4 7 5 8 3 6 2 3 . . 4 . 1 . . 2 3 5 7 4 9 1 6 8 . . 1 . . . 7 . . 9 6 1 2 5 8 7 4 3 . . 8 . 3 . . 2 9 4 7 8 6 3 1 5 2 9 7 . . . 8 . . 9 1 7 5 4 3 8 2 6 9 1 . . . 5 . 7 2 . . 6 1 3 5 9 7 2 8 4 . . . . 6 4 . . . 8 2 9 1 6 4 3 5 7 Number of recursive calls: 735 In 0.0366179943085 seconds .. Solution computed 7 . . . . . 4 . . 7 9 8 6 3 5 4 2 1 . 2 . . 7 . . 8 . 1 2 6 9 7 4 5 8 3 . . 3 . . 8 . 7 9 4 5 3 2 1 8 6 7 9 9 . . 5 . . 3 . . 9 7 2 5 8 6 3 1 4 . 6 . . 2 . . 9 . 5 6 4 1 2 3 8 9 7 . . 1 . 9 7 . . 6 3 8 1 4 9 7 2 5 6 . . . 3 . . 9 . . 6 1 7 3 5 2 9 4 8 . 3 . . 4 . . 6 . 8 3 5 7 4 9 1 6 2 . . 9 . . 1 . 3 5 2 4 9 8 6 1 7 3 5 Number of recursive calls: 3595 In 0.172569036484 seconds
Continue reading Algoritmi Randomizzati e Paralleli per risolvere il Sudoku