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!

Zo, tijd voor een update.


Ik heb weer een leuk baantje voor 1-2 dagen in de week (leuk, als afgestudeerd HBOer om toch in de IT te blijven werken.... ik ben niet zo goed in bordenwassen ).
Te weten bij Surfnet

Erg gave tent die ik al vanuit mijn stage kende.


Ik ga hier een geografisch informatie-systeem, waarin data van verschillende glasvezelkabels ligt, uitbreiden. Eerst echter moet er een enorme waslijst aan, al dan niet undesired, features worden afgewerkt.

Het doel van de database is inschatten, nav de geografische coordinaten van die fibers (die van verschillende aanbieders komen), wat het risico is dat meerdere kabels van 1 verbinding bij een ongeluk beschadigd raken. Redundantie en risico-analyse dus.

Hierna wordt met flex (webapplicatie, client-side) de route van de kabel zichtbaar gemaakt, waarna ook nieuwe kabels ingetekend kunnen worden. Bovenstaande gaat dus met SOAP naar de business logic toe.

Ik heb totaal geen ervaring met GIS'es, maar wel met postgresql, waar deze dus op draait.

De business logic maakt gebruik van Python, op een SOAP framework.... dus dat is best een interessant speeltje.
Webinterface is gemaakt in flex (open source flash achtige).
Verder was UNIX kennis een dikke pre, dus dat gaat ook helemaal goedkomen met mij .


Leuke van het project is dat het hele project zoals het er nu bijligt (en straks dus ook) opensource is. Dit draaide tot voorkort op een andere plaats, maar nu is er gelukkig een sourceforge projectje.
De gegevens van de glasvezelaanbieders zijn uiteraard niet opensource.... jammer maar helaas.


Tips, tricks, commentaar en succeswensen zijn uiteraard altijd welkom.

Screenshots etc komen maandag weer .