OBLIG 1 – INF 4820/3820 …
OBLIG 1 – INF 4820/3820 – SUDOKU-L?SEREN
Oppgaven skal leveres pr email til André og meg innen onsdag 17.10 kl 24.00.
Dere kan l?se det i en gruppe p? 1-3 personer. P? besvarelsen skal det klart angis hvem som har v?rt med i gruppen og hvilke deler den enkelte er ansvarlig for.
Oppgaven skal ende opp med kj?rbar kode i Common Lisp.
Programmet skal l?se standard Sudoku oppgaver (p? 9x9 brett). Om Sudoku kan du f eks se
http://www.menneske.no/sudoku/
til slutt skal du b?de angi kode og gi 5 kj?ringseksempler av varierende vanskelighetsgrad og m?le hvor lang tid kj?ringen tar. Noe bakgrunnskode finnes i Norvig kap 17. Du kan ellers bruke kode fra boka
http://norvig.com/paip/
Nedenfor er et forslag til punkter i en besvarelse. Disse kan du f?lge om du vil:
1. Bestem input/output representasjon
2. For algoritmen kan det v?re nyttig ? holde orden p? for hver av de 9 horisontale radene, de 9 vertikale radene og de 9 sm?brettene hvilke tall som er i dem til enhver tid. Det vil ogs? v?re nyttig for hver rute ? holde orden p? hvilke mulige tall som kan settes inn der. Bruk defstruct til ? definere fornuftige datastrukturer for dette.
3. Et f?rste fors?k p? en algoritme kunne v?re ? s?ke gjennom mulige innsettinger for tall i rutene. Du kan f?rst pr?ve dette.
4. Deretter ser du p? ”constraint propagation” slik du har i Norvigs kap 17. Der pr?ver du systematisk ? minske valgmulighetene for hver rute. Du starter et sted og ser om du ved ? ta hensyn til de mulige valg for naborutene kan minske antall valg for ruta. S? g?r du til naboruter og gjentar prosessen. M?let er hele tiden ? gj?re valgmulighetene for hver rute s? liten som mulig.
5. Du kommer fram om det er bare et mulig valg for hver rute.
6. Diskuter mulige forbedringer.