![[RSS]](http://tweakimg.net/g/if/v2/icons/rss_small.png){kind=icon}
Sudoku oplosser in Ruby
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:
Deze sudoku wordt binnen de seconde opgelost door mijn Intel SU9400 in mijn laptopje
.
Het gaat hier om ongeveer 500 regels nuttige code:
code:
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!
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!
Zelfbouw-waterkoeling: radiator-behuizing
Hoihoi
Ik ben ook weer eens bezig met een klein projectje.
Mijn NAD716, we kennen hem nog van hier http://boudewijn.tweakblo...716-van-wrak-tot-bak.html ga ik maar eens omvormen in een leuke kast voor mijn radiatoren. Ding krijgt dan toch nog een goed doel...
Ook omdat er destijds best wat respons was op mijn toenmalige gemodder met die versterker een updateje van wat ik ermee aan het doen ben.
Radiatoren? Ja, mijn pc gaat weer eens aan de waterkoeling (na 5 jaar oid er niets aan gedaan te hebben). Omdat ik een dual CPU bak met graka en chipset passief wil koelen ivm het geluid zijn 4 radiatoren geen overbodige luxe.
Dit is een leuk situatieschetsje (op het NB koelblok, 1 CPU en het graka-koelblok na
).
Meediscussieren, afkraken, zeuren etc kan hier:
[CIP] NAD-iator
Ik ben ook weer eens bezig met een klein projectje.
Mijn NAD716, we kennen hem nog van hier http://boudewijn.tweakblo...716-van-wrak-tot-bak.html ga ik maar eens omvormen in een leuke kast voor mijn radiatoren. Ding krijgt dan toch nog een goed doel...
Ook omdat er destijds best wat respons was op mijn toenmalige gemodder met die versterker een updateje van wat ik ermee aan het doen ben.
Radiatoren? Ja, mijn pc gaat weer eens aan de waterkoeling (na 5 jaar oid er niets aan gedaan te hebben). Omdat ik een dual CPU bak met graka en chipset passief wil koelen ivm het geluid zijn 4 radiatoren geen overbodige luxe.
Dit is een leuk situatieschetsje (op het NB koelblok, 1 CPU en het graka-koelblok na
).Meediscussieren, afkraken, zeuren etc kan hier:
[CIP] NAD-iator
Reparatie Iiyama E481S
Zo, een kleine update.
Vorige week begon mijn Iiyama 19" lcd (staat naast mijn main rig) lastig te doen.
Hij wilde eerst even aan gaan, waarna het beeld na 3 seconden weer zwart werd omdat het backlight niet wilde starten.
Aan en uit zetten, aantal malen, hielp.
Telkens meer keren herstarten, tot hij het eergisteren dus compleet niet meer wilde doen.
Ding opengeschroefd (komt zo nog een stukje over) en de print eens bekeken:
Vieze capjes....
Onderzijde print valt me dan weer mee(deze foto is wat eerder genomen):
Overzichtsplaatje:
Natuurlijk vervang ik vervolgens de capjes die zo slecht eraan toe zijn
Okay het open en dicht maken is wat onduidelijk bij dit scherm (weinig instructies te vinden, het is een E481S). Openmaken is gewoon dit verhaaltje de 'verkeerde kant op' uitvoeren
:
EMI schild (?) weer over de SMPS
Plastic kap weer vastschroeven op achterkant monitor (hier moet je bij openmaken even de schroevendraaier tussen zetten).
(plaatje is niet super spannend, dus dit keer geen img-tags
).
http://tweakers.net/ext/f/MgcPYu5cMuEZjP0gSuR6lwxl/full.jpg
Je ziet de 2 halfronde blokjes die je over de schroeven heen moet klikken, als je de zaak openmaakt moet je deze inknijpen en naar je toe trekken.
Dan komen ze los
.
Bevestiging van voet weer vastzetten (daarachter zit het 5e vijsje van de hoofdplaat!).
Daarna de voet weer in elkaar klikken en de 2 schroefjes achterop vastklikken.
Daarna het horizontale deel aan de voet drukken.
Klaar.
Met dank aan naftebakje en de rest van [EL].
Vorige week begon mijn Iiyama 19" lcd (staat naast mijn main rig) lastig te doen.
Hij wilde eerst even aan gaan, waarna het beeld na 3 seconden weer zwart werd omdat het backlight niet wilde starten.
Aan en uit zetten, aantal malen, hielp.
Telkens meer keren herstarten, tot hij het eergisteren dus compleet niet meer wilde doen.
Ding opengeschroefd (komt zo nog een stukje over) en de print eens bekeken:
Vieze capjes....
Onderzijde print valt me dan weer mee(deze foto is wat eerder genomen):
Overzichtsplaatje:
Natuurlijk vervang ik vervolgens de capjes die zo slecht eraan toe zijn
Okay het open en dicht maken is wat onduidelijk bij dit scherm (weinig instructies te vinden, het is een E481S). Openmaken is gewoon dit verhaaltje de 'verkeerde kant op' uitvoeren
:EMI schild (?) weer over de SMPS
Plastic kap weer vastschroeven op achterkant monitor (hier moet je bij openmaken even de schroevendraaier tussen zetten).
(plaatje is niet super spannend, dus dit keer geen img-tags
).http://tweakers.net/ext/f/MgcPYu5cMuEZjP0gSuR6lwxl/full.jpg
Je ziet de 2 halfronde blokjes die je over de schroeven heen moet klikken, als je de zaak openmaakt moet je deze inknijpen en naar je toe trekken.
Dan komen ze los
.Bevestiging van voet weer vastzetten (daarachter zit het 5e vijsje van de hoofdplaat!).
Daarna de voet weer in elkaar klikken en de 2 schroefjes achterop vastklikken.
Daarna het horizontale deel aan de voet drukken.
Klaar
.Met dank aan naftebakje en de rest van [EL].
Nieuwe baan
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.
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
.NAD716: van wrak tot bak
Een paar weken geleden heb ik een NAD716 5.1 versterker (defect) op tweakers opgepikt voor een zacht prijsje.
Dit met het doel om hem weer op te lappen en er dan of een mooie bak aan over te houden, of hem gewoon te verkopen.
Diagnose:
Apparaat wil wel aan, en je hoort wat voedings-relais schakelen.
Vervolgens gaat het powerled aan, maar het display: ho maar.
Ook de knoppen en de versterking lijken niet te reageren.
Eerst even wat fotootjes:
We zien vlnr de voedingsprint en de trafo (buiten de kast de NAD-link-afstands-bedienings-print), daarna een bigass koellichaam voor de eindtorren.
Daarna het mainboard (onderop) met voedings-stabilisatie en display-ICs.
De grote staande print is de print met de volumepot en nog een heel berg losse componenten, met daarop geklikt de FM tuner print (het kleine ding rechts met de RF-behuizing).
Achterkantje (niet zo boeiend):
Voorkant (mag een sopje gebruiken ja):
Service manual gekocht, anders schiet het ook niet op met dit soort projectjes...
Het blijkt dus dat een aantal spannings-regelaars (ik meen 7812's) gewoon een spanning kregen die onder hun drop-out voltage zit; ze moeten minstens 1.5V meer input krijgen dan hun output voor correct functioneren (dat is althans de vuistregel). Hier niet het geval....
Tijd om de multimeter uit de kast te pakken
Vermoedelijk ligt het aan een aantal gelijkrichtingsdiodes op de moederprint, maar dit moet ik nog even goed uitzoeken!
Kapotte print
Echter, na dit alles gedaan te hebben besloot ik (in alle wijsheid) de print met de volumeknop eens goed te laten stuiteren (jaja geen commentaar daarover svp):
Ondertussen is dat na 1 avond hard werken ook allemaal opgelost (en ja dat slechte draadje is ook pleiten).
Met dit als resultaat:
Het losse draadje is al gefixed ja.
En hersolderen.
Ondertussen ook maar even de rest van de printplaat meegepakt, want van dit soort dingen word je niet vrolijk...
Bovenstaande foto is trouwens van de display print, maar er zijn meer van dat soort 'puntjes'. Ook wat halve eilandjes en kuilen in het tin, en van die 'ringen' om pootjes.
Niet goed...
Wordt een dezer dagen vervolgd, we gaan de voeding slopen.
Dit met het doel om hem weer op te lappen en er dan of een mooie bak aan over te houden, of hem gewoon te verkopen.
Diagnose:
Apparaat wil wel aan, en je hoort wat voedings-relais schakelen.
Vervolgens gaat het powerled aan, maar het display: ho maar.
Ook de knoppen en de versterking lijken niet te reageren.
Eerst even wat fotootjes:
We zien vlnr de voedingsprint en de trafo (buiten de kast de NAD-link-afstands-bedienings-print), daarna een bigass koellichaam voor de eindtorren.
Daarna het mainboard (onderop) met voedings-stabilisatie en display-ICs.
De grote staande print is de print met de volumepot en nog een heel berg losse componenten, met daarop geklikt de FM tuner print (het kleine ding rechts met de RF-behuizing).
Achterkantje (niet zo boeiend):
Voorkant (mag een sopje gebruiken ja):
Service manual gekocht, anders schiet het ook niet op met dit soort projectjes...
Het blijkt dus dat een aantal spannings-regelaars (ik meen 7812's) gewoon een spanning kregen die onder hun drop-out voltage zit; ze moeten minstens 1.5V meer input krijgen dan hun output voor correct functioneren (dat is althans de vuistregel). Hier niet het geval....
Tijd om de multimeter uit de kast te pakken
Vermoedelijk ligt het aan een aantal gelijkrichtingsdiodes op de moederprint, maar dit moet ik nog even goed uitzoeken!
Kapotte print
Echter, na dit alles gedaan te hebben besloot ik (in alle wijsheid) de print met de volumeknop eens goed te laten stuiteren (jaja geen commentaar daarover svp
):Ondertussen is dat na 1 avond hard werken ook allemaal opgelost (en ja dat slechte draadje is ook pleiten).
Met dit als resultaat:
Het losse draadje is al gefixed ja
. En hersolderen.
Ondertussen ook maar even de rest van de printplaat meegepakt, want van dit soort dingen word je niet vrolijk...
Bovenstaande foto is trouwens van de display print, maar er zijn meer van dat soort 'puntjes'. Ook wat halve eilandjes en kuilen in het tin, en van die 'ringen' om pootjes.
Niet goed...
Wordt een dezer dagen vervolgd, we gaan de voeding slopen
.