Sudoku

Som et lille barselsprojekt ville jeg gerne prøve at lære lidt af Googles kodesprog, Golang.

Som så mange gange før, var det dog svært at finde på et egentlig projekt, man kunne bruge det til. Så jeg tog nogle kurser og lavede nogle øvelser — men selvom sproget er min nye favorit, manglede der et projekt. Så fik jeg idéen om man mon ikke kunne løse sudokuer ved at kode et ret simpelt program …

Reglerne i sudoku er jo nemme: en tabel med 9×9 felter; hver række og kolonne skal indeholde tallene 1-9, og de ni mindre kasser af 3×3 felter skal også indeholde tallene 1-9.

Jeg gik derfor i kast med det og det lykkedes da også ret hurtigt ved hjælp af en algoritme, der kaldes for backtracking:

1. Start i et hjørne
2. Bevæg dig hen ad brættet til første tomme felt
3. Sæt et 1-tal: Var det ikke tilladt? Prøv med 2, 3, 4, 5, 6, 7, 8, 9. Hvis ingen af dem går, er brættet ugyldigt.
4. Gå endnu et felt frem.
5. Sæt et 1-tal: Var det ikke tilladt? Prøv med 2, 3, … Hvis ingen er gyldige, går du bagud, indtil der er et tal, du har sat, der er mindre end 9 og øger det med 1.
6. Gentag punkt 4-5 indtil brættet er løst.

Da jeg kunne løse en sudoku, tænkte jeg, at det kunne være sjovt at se processen. Så jeg ændrede programmet, så det kunne animere sine løsninger.

Resultatet af det ses nedenfor. Selve løsningen tager under 1 sekund (også for almindelige “sværere” sudokuer), men at vise animationen tager tid.

Links

• Kildekoden på Github - på ingen måde optimeret eller pæn (endnu?).