Risoluzione del Sudoku mediante backtracking
- Studente: Andrea De Fanti
- Matricola: VR089606
- Insegnamento: Ragionamento automatico
- Anno Accademico: 2010/11
- Docente: Alessandro Farinelli
Specifiche
- Formalizzazione Sudoku come rete di vincoli
- Implementazione di due o più tecniche solutive (principalmente backtracking)
- Il programma deve essere in grado di leggere file formato standard (machine readable)
- Comparazione empirica dei risolutori su varie istanze, utilizzando come misure elementi quali numero di constraint check, numero di variabili istanziate, etc..
- Il programma sarà dotato di interfaccia grafica per l'utente.
Algoritmo ed euristiche
Sono stati implementati quattro algoritmi di backtracking:
- Risoluzione per riga (BackTrack1.java): utilizza un ordinamento delle varibili per riga
- Risoluzione per colonna (BackTrack2.java) utilizza un ordinamento delle varibili per colonna
- Risoluzione in modalità random (BackTrack3.java) utilizza un ordinamento random delle varibili
- Risoluzione con l'euristica considera il blocco più vincolato (BackTrack4.java). L'ordinamento delle variabili è dinamico in base al blocco con il maggior numero di vincoli
Ogni algoritmo implementa un'interfaccia comune (Solver.java).
Il codice
- Linguaggio utilizzato: JAVA
- Compilazione javac *.java
- Esecuzione: java Gui
Relazione
- Le regole del gioco
- La formalizzazione
- Lo scopo del progetto
- La generazione della griglia
- L'interfaccia e gli algoritmi
- Compilazione e esecuzione
- Risultati
Link
|