OBLIG 1 ¨C INF 4820/3820 ¨C 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.