Lezer Wouter, een goede vriend van me, stuurt me een gastblog. En ik heb het allemaal goed begrepen, hoor! Echt waar! Hier gaan we:
Recent kreeg ik een vraag naar begeleiding van een middelbaar scholier uit bevriend milieu bij een jaarwerk programmeren. Na een eerste advies richting Java aan de hand van de best seller "Programmeren in Java" van Lieven Smits ( http://hoger.uitgeverijdeboeck.be/livre/?gcoi=90455100405010 ) kwam de vraag naar een praktische toepassing om eea tastbaar te maken. Na beraad werd het oplossen van de Sudoku als case study naar voren geschoven, officieel omdat het een didactisch verantwoord onderwerp is, maar in werkelijkheid evenzeer om papa, verwoed puzzelaar, de loef af te steken. Om het spel eerlijk te spelen, werd afgesproken mijn inbreng te beperken tot het conceptuele, en de eigenlijke programmatie bij de student in kwestie te laten.
We snijden het onderwerp aan door twee alternatieve, en potentieel complementaire technieken voor te stellen. De eerste techniek tracht de menselijke benadering na te bootsen, door het programmeren van een aantal heuristieken. De tweede techniek is deze van de domme kracht, waarbij ongenuanceerd en systematisch alle mogelijkheden worden uitgeprobeerd, om die ene juiste oplossing te weerhouden. De gekende tegenstelling tussen kwantiteit (de snelle aanpak) en kwaliteit (de slimme aanpak), waarbij de laatste vermoedelijk een pak sneller is.
De heuristische methode bestaat erin een aantal vuistregels te bedenken en uit te werken, die toelaten een bijkomend cijfer op het bord te plaatsen. Als bijvoorbeeld het cijfer 1 reeds voorkomt op de eerste en de tweede rij, beperkt dat de mogelijkheden op de derde rij. In geval er slechts één mogelijkheid overblijft voor het cijfer 1 op de derde rij, kunnen we dit toevoegen. Dergelijke vuistregels zullen over het algemeen relatief makkelijk een bijkomend cijfer opleveren, echter zonder garantie dat ze in elke situatie ook succesvol zijn. Voor de hand liggende en generieke heuristieken zijn "slechts één mogelijke cel waar een ontbrekend cijfer geplaatst kan worden", en "slechts één mogelijk cijfer toegelaten in een bepaalde cel", in zekere zin elkaars duale.
Eerdere experimenten van ondergetekende toonden aan dat de twee vermelde heuristieken bijzonder krachtig zijn, maar niet dekkend. Er zijn met andere woorden situaties waarbij geen van beiden ons kan helpen. Vraag is of we deze heuristieken kunnen aanvullen, zodat zij wel dekkend worden, zonder daarbij te vervallen in de techniek van de domme kracht. Een interessante aanvulling op het jaarwerk.
De methode van de domme kracht daarentegen bestaat erin de eerstvolgende vrije cel te nemen, in arbitraire volgorde. Deze cel wordt opgevuld met het eerst mogelijke cijfer, waarbij de overige mogelijkheden bewaard worden als keuzepunten. Wanneer bij herhaling van deze basisoperatie blijkt dat voor een bepaalde cel geen cijfer meer kan gevonden worden, wordt de betreffende oplossingspiste verlaten, en wordt teruggegrepen naar het laatst bijgekomen keuzepunt.
De techniek waarbij op die wijze een zoekruimte systematisch wordt uitgekamd, en bij vastlopen eerder genegeerde alternatieve pistes worden onderzocht, wordt veel gebruikt in regelgebaseerde systemen (expert systems), en wordt ook wel back-tracking genoemd. De keuzepunten kan je vergelijken met de broodkruimels van Klein Duimpje, zij het dat hij enkel terug naar huis wilde, en dat broodkruimels om allerlei redenen vergankelijk zijn.
De kortste oplossing voor het Sudoku probleem tot op heden geformuleerd is ongetwijfeld het Groovy fragmentje te vinden op http://groovy.codehaus.org/Solving+Sudoku , slechts 184 karakters lang. Het betreft, hoe kan het ook anders, de techniek van de domme kracht.
Terug naar de scholier, werd de ambitie geformuleerd beide technieken te combineren. Hierbij worden heuristieken gebruikt zolang zij toelaten voortgang te boeken, en wordt de techniek van de domme kracht gebruikt telkens de heuristieken falen. Een leuk neveneffect is dat dit een metriek kan opleveren voor de effectiviteit van een heuristiek, door te tellen hoe vaak een teruggrijpen naar de techniek van de domme kracht noodzakelijk is.
We beginnen echter bescheiden met het uitwerken van een data type voor de bordrepresentatie, en een eerste poging tot het implementeren van de techniek van de domme kracht. Voldoende materie om de kerstperiode door te komen. We zullen niet nalaten jullie verder te informeren in de loop van het schooljaar, naarmate het jaarwerk vordert.
Enig snel rekenwerk levert een aantal indrukwekkende cijfers op. Een bovengrens voor het aantal mogelijke configuraties waarmee een Sudokubord kan worden opgevuld volgens de regels is 9.278.496.603.801.320.000.000.000.000.000.000.000. We merken hierbij op dat de oplossing maar uniek is op een permutatie van de negen cijfers na. Met 362.880 permutaties levert dit nog steeds 25.569.049.282.962.200.000.000.000.000.000 mogelijke configuraties.
Interessant is ook de symmetrie van het Sudokubord in rekening te brengen. Het verwisselen van rijen of kolommen, zonder daarbij de inhoud van verschillende 3x3 deelvierkanten te vermengen, levert in zekere zin equivalente configuraties op. Het verwisselen van rijen en kolommen in blokken van drie, weerom zonder daarbij de inhoud van verschillende 3x3 deelvierkanten te vermengen, levert nieuwe equivalenties op. Deze zorgen samen voor 1.679.616 permutaties van rijen of kolommen, waardoor 15.223.151.769.786.800.000.000.000 configuraties overblijven.
Daarbij hebben we spiegel- en rotatiesymmetrieen van het bord nog niet vermeld, wat het aantal configuraties mogelijk verder doet verkleinen. Ongetwijfeld bevatten deze transformaties enige redundantie. Een strikte benadering vinden we in de groepentheorie, waarbij de groep van transformaties van het Sudokubord beschouwd wordt, en welke elementen daarin voortbrengend zijn. Dit lijkt een kolfje naar de hand van de zwager van de eigenaar van dit blog; een invitatie !
Bij al dit algoritmisch geweld stelden mijn schoonouders zich de vraag wat er nog leuk was aan Sudoku's als je een computerprogramma hebt dat de oplossing aanreikt in een oogwenk. Welnu, dit is een typische verwarring van de weg en het doel. Het creatieve process van het uitwerken van de oplossing is als de exponent van het oplossen van een individuele Sudoku uit de klasse "very hard", bvb op de Daily Sudoku
( http://www.dailysudoku.co.uk/sudoku ).
Wouter
4 opmerkingen:
Wel, ik ben om mij te amuseren ook aan een sudoku-oplosser bezig. Ik
verkies wel python boven Java maar dat terzijde. Als ik goed op de
hoogte ben is het niet mogelijk om een verzameling van dekkende
heureustieken te hebben omdat het probleem NP-compleet zou zijn. Maar
het is nog steeds leuk om te zoeken naar extra heureustieken die
toelaten meer puzzels op te lossen met minder brute rekenkracht.
Op dit moment heb ik drie heuristieken en twee mogelijkheden die ik nog
nader moet bekijken. Als er belangstelling is, wil ik die wel bespreken
Een terechte opmerking, aangaande het NP-complete karakter van de Sudoku puzzel. Werd de equivalentie met een ander NP-compleet probleem effectief aangetoond, of betreft het een vermoeden ?
Wat onze heuristieken betreft: de eerste, uniek cijfer in een cell, is zeer eenvoudig. Je elimineert voor een lege cel alle waarden die reeds voorkomen in een regio (rij, kolom of 3x3 deelvierkant) waarin de cel zich bevindt. Als slechts één cijfer overblijft, plaats je dat cijfer in de betreffende cel.
De tweede heuristiek is de duale: unieke cel voor een cijfer. Je schrapt voor een bepaald cijfer, op een leeg bord, alle cellen waar reeds een cijfer staat. Vervolgens schrap je alle cellen van elke regio waarin het cijfer reeds voorkomt. Als op die wijze in een regio slechts één vrije cel overblijft, plaats je het betreffende cijfer in deze cel.
Wat het NP-compleet zijn betreft, alle referenties die ik gezien heb, vermelden sudoku als NP-compleet alhoewel ik nog geen bewijs gezien heb.
Wat de heureustieken betreft. Mijn indruk is dat je met cijfers in de cellen werkt. Persoonlijk werk ik met verzamelingen. De heurestieken die ik gebruik elimineren dan mogelijkheden door getallen uit die verzamelingen te verwijderen. Als je dan op de brute-force methode moet overgaan, geven die verzamelingen een idee welke mogelijkheden je nog moet proberen.
Een benadering met verzamelingen was ook al bij me opgekomen. Je werkt dan met facts als "regio bevat of bevat niet cijfers", waarbij "regio" een verzameling cellen is, en "cijfers" een verzameling cijfers. Door het combineren van facts (verzamelingtechnisch) kan je nieuwe facts maken, die dan hopelijk meer specifiek zijn. Wanneer een fact voldoende specifiek is, kan op unieke wijze een cijfer geplaatst worden.
Ik heb dit nog niet uitgewerkt. Omdat dit een breadth-first search is, vraag ik me af hoe omvangrijk de verzameling facts wordt tijdens de search.
Een reactie posten