Lees een eenvoudige representatie van een Sudoku in,
bijvoorbeeld zoiets als:
4
1 0 3 0
3 0 0 1
0 1 4 0
4 0 0 0
De eerste regel bevat het aantal rijen/kolommen van de Sudoku (in het voorbeeld
4, meestal 9). Daarna staat de rijen van de Sudoku: in ons voorbeeld 4 rijen met 4 getallen,
waarbij de nullen staan voor onbekende getallen.
De oplossingen zijn individuen, met 16 (4 bij 4) of 81 (9 bij 9)
getallen uit {1,2,3,4} respectievelijk {1,2,3,4,5,6,7,8,9}.
Bedenk eenvoudige genetische operatoren. Verwissel bijvoorbeeld
rijen of kolommen tussen individuen. En moeten de rijen en/of
kolommen altijd permutaties zijn en blijven van {1,2,3,4} respectievelijk {1,2,3,4,5,6,7,8,9}?
Probeer niet het ultieme programma te schrijven!
Voor liefhebbers een artikel over dit probleem:
Timo Mantere and Janne Koljonen,
Solving and Rating Sudoku Puzzles with
Genetic Algorithms,
2007 IEEE Congress on Evolutionary computation, CEC2007, pages 1382-1389
(niet plagiëren svp; dank aan Pieter Bas).
Beschrijf in het verslag (niet te lang, niet te kort!)
duidelijk representatie, fitness-functie, genetische operatoren, experimenten.
De uitvoer van het programma geeft de
"beste oplossing" die gevonden is voor een enkele voorbeeldgraaf.
Zie hier voor meer
informatie over gnuplot.
In te leveren: geprint verslag (in LaTeX gemaakt; de C++-code als Appendix, zie verder hier voor opmerkingen over het verslag), en per email: de C++-code. Stuur svp geen emails met LaTeX/PS/PDF/executables.
Deadline: maandag 4 mei 2009.
Vragen en/of opmerkingen kunnen worden gestuurd naar: kosters@liacs.nl.
3 april 2009 — http://www.liacs.nl/home/kosters/AI/ga09.html