[Home]HomePage

HomePage | RecentChanges | Preferences

Labbook ZSB 2005

Dit Labbook behoort bij het project [Zoeken, Sturen en Bewegen]

0435899		nout		Niels Out   
0440949		acranenb	Andreas van Cranenburgh

Inleiding

Ons project gaat over [Sudoku]. We zullen deze puzzel algoritmisch proberen op te lossen. Als dit lukt, willen we het uitbreiden met vergelijkingen tussen verschillende puzzels.

Wat is Sudoku

Dit is een puzzel, meestal bestaande uit een veld van 9 x 9. In ieder vakje dient een getal van 1 tot 9 ingevuld te worden. In iedere regel en kolom mag elk cijfer maar een keer voorkomen. Ook is het veld opgedeeld in 9 vakjes van 3 x 3, regio's genaamd. Elk cijfer mag ook maar een keer voorkomen in elke regio.

Een puzzel bevat een aantal gegeven waarden, het doel is dan om de rest in te vullen. Doorgaans zijn de gegeven waarden zo gekozen dat er maar een oplossing is voor een puzzel.

Sudoku is in Nederland bekend geworden doordat deze puzzels dagelijks in de Sp!ts te vinden zijn.

Voorbeeld:

Plan

We gaan een programma schrijven om Sudoku puzzels op te lossen. Dit doen we in C en Prolog. Hierna vergelijken we de twee programma's op bijvoorbeeld snelheid en leesbaarheid.

We gaan uit van de brute force methode, domweg alle mogelijke waarden invullen. Met alle mogelijke waarden wordt bedoeld waarden die nog niet eerder in dezelfde regel, kolom of regio zijn gebruikt.

We verwachten dat C sneller zal zijn dan onze Prolog versie, omdat Prolog langzaam is.

Hierna gaan we een puzzel die relatief lang duurt om op te lossen, simpeler maken door meer/minder vakjes open te laten in het begin. We verwachten dat een versie met minder vakjes open sneller op te lossen is. Bovendien vermoeden we dat als we meer vakjes openlaten, dat er ook meerdere mogelijke oplossingen zijn.

De Code

 o C: https://unstable.nl/andreas/c/sudoku.c
         gebruik: ./sudoku <file.txt
 o SWI-Prolog: http://student.science.uva.nl/~nout/sud.pl
         gebruik: start('file.txt').
 o GNU prolog versie: https://unstable.nl/andreas/prolog/sud.pl [binary]
         gebruik: ./sud file.txt

 o Prolog code met constraints (niet door ons gemaakt, vergelijkingsmateriaal: https://unstable.nl/andreas/prolog/sudoku.notours.pl

Zondag 26 Juni

Begonnen met opzet van het C programma. Bestandsformaat voor puzzels bedacht: negen karakters per regel, negen regels. Lege vakjes zijn spaties of nullen. Voor prolog wordt hetzelfde formaat gebruikt, zodat dezelfde puzzles makkelijk te vergelijken zijn met beide talen.

Het programma lost puzzels op met maximaal 41 ontbrekende waarden. Bij meer ontbrekende waarden geeft het programma het om onduidelijke redenen op.

Maandag 27 Juni

Het C programma verder bewerkt. Na een paar kleine verandering lost het programma alle sudoku's op. Wel is het algoritme nog zeer inefficient, soms is de maximale recursie wel 70.000. Desalniettemin worden alle puzzels in minder dan een seconde opgelost!

Prolog code kan simpele sudoku's oplossen, moeilijkere duren erg lang (te lang).

Dinsdag 28 Juni

Ge-experimenteerd met het vinden van meerdere oplossingen (bijvoorbeeld bij een leeg veld). Een eenvoudige aanpassing maakt dit mogelijk: in plaatst van "return true" wordt de oplossing nu geprint. Algoritme om nieuwe puzzels te generen bedacht.

Prolog code kan meeste sudoku's snel oplossen, sommige duren echter nog vrij lang.

Samen naar robotvoetbal-wedstrijd gekeken ter ontspanning.

Woensdag 29 Juni

Het C en prolog programma werkt respectievelijk goed en redelijk. Het prolog programma kan nog verder geoptimaliseerd worden.

Een idee om nu uit te voeren is een groostchalige meting. We nemen een collectie van Sudoku puzzels met oplopend aantal ontbrekende vakjes. Dan kijken we hoe snel de programma's deze puzzels kunnen oplossen. Om de meetresultaten betekenis te geven moet elke puzzel bijv. 100 keer worden opgelost, anders zijn de resultaten niet significant. De resultaten zetten we dan uit in een grafiek.

Command line opties toegevoegd aan het C programma:

 o -g genereer een puzzel.
 o -s x  geef oplossing nummer x.
 o -n x  los puzzel x maal op.

Prolog code aangepast om ook met GNU prolog te werken. De reden hiervoor is dat GNU prolog programma's kan compileren naar native executables. Hierdoor zal de vergelijking met C veel eerlijker worden.

's Avonds VIA-BBQ met waarschijnlijk veel bier.

Donderdag 30 Juni

Gisteravond was erg gezellig, maar we zijn wel net als voorgaande dagen voor 11 uur al weer aan het werk op de universiteit. Het blijkt dat de gecompileerde versie van het Prolog programma inderdaad veel sneller werkt. We hebben op internet ook een erg snelle prolog code gevonden die met constraints werkt, waarmee we ook gaan vergelijken.

De puzzelgenerator van de C code kan nu een opgegeven aantal waarden wegstrepen, zodat de moeilijkheidsgraad is te bepalen. Met het volgende commando hebben we nu 40 puzzels gemaakt om de meting mee te gaan doen:

COUNTER=50; until [ $COUNTER -lt 10 ]; do; ./sudoku -g $COUNTER >puzzle$COUNTER.txt; let COUNTER-=1; done

Het resultaat is een 40-tal bestanden, puzzle50.txt tot en met puzzel10.txt, met allemaal verschillende puzzels in oplopende moeilijkheidsgraad.

Vrijdag morgen 1 Juli

Na metingen bekeken te hebben, vallen wat dingen op, zie discussie hierover.

2:13 --> We hadden dus de user time ipv de total moeten gebruiken om te checken welke sneller is, maar we hadden ook naar bed moeten gaan.

Dit doen we nu dus ook, welterusten!

Software en Apparatuur

We gebruik van de volgende software voor ons project:

- Linux

- GNU C compiler

- GNU Prolog

- SWI prolog

- Kwrite to edit the code :P

Apparatuur die we gebruikt hebben:

- Personal Computer van Dell, zoals aanwezig op universiteit

Meetresultaten

Zie MeetResultaten voor de ruwe data. Zie https://unstable.nl/andreas/c/meetgegevens.xls voor de spreadsheet.

De grafieken

Toelichting: op de Y-as staat de tijd in seconden. Op de X-as staat het number van de puzzel.

Opvragen van de eerste 10 oplossingen:

100 maal oplossen:

Discussie

Er zijn wat meetwaarden die duidelijk niet kloppen in de grafieken. Onder andere de hoge piek bij 34 is vreemd. We vermoeden dat dit komt door onze manier van de tijd meten, we hebben niet veel tijd hierin gestoken om te kijken of dit wel altijd klopt. Volgens de meting 2% cpu 0.214 total die bij 34 hoort, was de cpu voor slechts 2% in gebruik, gedurende 0.214 seconde, wij gingen er echter vanuit dat deze 0.214 het aantal seconden was dat de cpu geheel gebruikt werd.

Conclusie

Onze verwachting dat C sneller is dan Prolog lijkt te kloppen. Wel zit de Constraints versie van prolog er zeer dichtbij. Het is goed mogelijk dat het verschil in tijden tussen deze twee komt door de tijd die het inlezen van de files inneemt. Bij de 100 maal oplossen vertonen zowel de C versie als de constrains Prolog code kleine piekjes, die redelijk regelmatig lijken, dit komt misschien ook wel door de manier van meten. Onze eigen prolog code is duidelijk langzamer, alhoewel we er al veel aan geoptimaliseerd hebben.

Het klopt bovendien dat een puzzel met weinig open vakjes sneller is op te lossen, wat echter alleen bij onze prolog versie te zien is. Bij de C en de andere prolog code gaat er waarschijnlijk te veel tijd verloren met bijzaken als de puzzel inlezen.


HomePage | RecentChanges | Preferences
Edit text of this page | View other revisions
Last edited July 1, 2005 7:50 by Andreas (diff)
Search: