Boudewijns blogje

Hoihoi


Voor het eerst sinds een redelijke tijd weer eens een blogpost van me.
Dit keer over een sudoku oplosser die ik in het kader van een universiteitsopdracht (uva, MSc. software engineering) moest schrijven (don't ask....). Dit moest (helaas) in Ruby, en mocht dus niet in Haskell, wat ik een stuk handiger vind.


Solvertje is geschreven, en ik wilde zo min mogelijk brute-forcen. Uiteraard kon ik jullie mijn oplossing niet onthouden.

Het idee is dat er een schaduwmatrix wordt gemaakt (pfields) van de gewone sudoku matrix (fields) met daarin per veld alle nog mogelijke waarden.
Zolang het mogelijk is om een getal in de gewone matrix in te vullen ) is er dus een pfields met als lengte 1 (en als inhoud het getal dat in fields moet).

Telkens als ik een waarde toevoeg aan fields wordt die pfields matrix geupgrade.
Als er geen waardes meer zijn die ik kan invullen gaat het algoritme kijken welk pfields veld de kortste lengte heeft (en dus de minste invulmogelijkheden) en dan worden verschillende instances van de sudoku gespawned (zie de fork methode) om zo verder te gaan met solven. Hier gebruik ik dus backtracking; termineert een van de sudoku-forks echter positief, dan is de sudoku sowieso opgelost.

Ik heb even een en ander van blackboard gecopieerd als voorbeeld code:



code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

De volgende testcase kun je gebruiken om je Sudoku sovler uit te proberen. --- | --- | -1- 4-- | --- | --- -2- | --- | --- ----+-----+---- --- | -5- | 4-7 --8 | --- | 3-- --1 | -9- | --- ----+-----+---- 3-- | 4-- | 2-- -5- | 1-- | --- --- | 8-6 | --- Deze Sudoku is notoir lastig. Dit houdt in dat deze bewijsbaar tot minimaal 17 levels backtracking zal leiden bij een triviale brute-force approach. Om de performance van je solver in orde te krijgen moet je dus nog iets slims doen, bijvoorbeeld een goede heuristiek gebruiken voor de volgorde waarin je door de Sudoku werkt. Tip: vermijdt voortijdige optimalisatie en maak aanvankelijk een cleane versie waarvan je daarna de ordegroottes van je algorithme goed kunt krijgen.

Deze sudoku wordt binnen de seconde opgelost door mijn Intel SU9400 in mijn laptopje .


Het gaat hier om ongeveer 500 regels nuttige code:

code:

1 2 3 4 5 6 7

www-productie:/var/www/boudewijnector.nl/devcorner# wc -l * 29 runner.rb 93 stdoutPrinter.rb 155 sudokuLogger.rb 481 sudoku.rb 141 voorbeeldsudoku.rb 899 total

En ik ben me ervan bewust dat sommige dingen best makkelijker kunnen (zie ook het commentaar in sudoku.rb).
runner.rb is het bestand waarmee je de rest runt, en die gebruikt voorbeeldsudoku om de voorbeelden uit te halen. Momenteel is daar bovenstaande sudoku voor ingesteld.

de logger en de printer zijn handig voor debuggen, en sudoku.rb is de logica zelf.


Files zijn hier te vinden:
http://devcorner.boudewijnector.nl/runner.rb
http://devcorner.boudewijnector.nl/stdoutPrinter.rb
http://devcorner.boudewijnector.nl/sudokuLogger.rb
http://devcorner.boudewijnector.nl/sudoku.rb
http://devcorner.boudewijnector.nl/voorbeeldsudoku.rb

Heb je feedback of kritiek, dan hoor ik het graag!