Inleiding

Onlangs heb ik J-Fall 2008 bezocht. De eerste keer dat ik dit Java congres bezoek. In alles wat kleiner dan JavaPolis maar over het algemeen erg interessant en goed georganiseerd. Naast het gebruikelijke t-shirt werpen en een mooie JavaFX demo met een Wii afstandsbediening en een projector die enthousiast werd onthaald, wil ik een onderwerp extra belichten naar aanleiding van een lezing die ik daar bezocht heb: het oplossen van Constraint Satisfaction Problems met Java [1]. In dit artikel neem ik de proef op de som door met een CSP framework te proberen een Sudoku puzzel op te lossen.

Constraint Satisfaction Problems

Constraint Satisfaction Problems (CSP’s) zijn problemen waarvoor in het algemeen enige vorm van menselijke intelligentie nodig is om ze op te lossen, zoals het oplossen van puzzels en het inroosteren van resources. (Een goede beschijving is te vinden in [2].) Deze problemen kenmerken zich ook door het grote aantal mogelijkheden (de zoekruimte) dat moet worden doorzocht waardoor brute-force algoritmen geen oplossingen kunnen geven binnen een aanvaardbare tijd.

Ook neemt door een beperkte toename van het aantal variabelen deze zoekruimte explosief toe. Een voorbeeld dat gegeven werd was een haven waar 10 schepen ontladen moeten worden maar waar maar 5 dokken beschikbaar zijn. De rekentijd van een brute force algoritme zou al snel enorm toenemen indien hetzelfde bepaald zou moeten worden voor 20 schepen voor 10 dokken (van 5^10 naar 10^20 mogelijkheden).

Een mogelijke oplossing moet voldoen aan een aantal eisen (constraints). In dit voorbeeld bijvoorbeeld dat de lengte van een schip niet groter mag zijn dan de lengte van het dok. Of dat schepen met een bederfelijke of gevaarlijke lading eerder gelost moeten worden dan anderen. Hoe meer constraints des te ingewikkelder het bepalen van een oplossing (satisfaction) voor een brute force algoritme of voor een mens. CSP algoritmen worden juist efficiënter indien er meer constraints zijn. Ze zijn erg goed in het beperken van de zoekruimte aan de hand van deze constraints waardoor het aantal mogelijke oplossingen drastisch afneemt. Als een schip niet langer mag zijn dan een dok vallen bijvoorbeeld al een aantal mogelijkheden af.

In een CSP framework zijn deze algoritmen ingebouwd en hoeven we alleen de constraints op te geven waaraan de oplossing moet voldoen. We kunnen wel verschillende algoritmen gebruiken voor verschillende soorten problemen. Dit is een onderwerp op zich en valt buiten dit artikel. Een voorbeeld van een commercieel product is ILog JSolver [3], dat bijvoorbeeld gebruikt wordt bij planning van vluchtschema’s op vliegvelden. Een wat beperkter product is Cream [4], dit is een open source CSP framework met een Java API. Met dit laatste product probeer ik een “Sudoku oplosser” te maken.

Sudoku

De regels voor een Sudoku mogen bekend worden verondersteld maar ik herhaal ze hier voor de goede orde:

• Een Sudoku speelveld bestaat uit 9 rijen en 9 kolommen.
• Het speelveld is onderverdeeld in 3×3 subvelden van 3 rijen en 3 kolommen
• Elk veld moet een waarde tussen 1 en 9 hebben.
• Elke waarde in een rij moet uniek zijn
• Elke waarde in een kolom moet uniek zijn
• Elke waarde in een subveld moet uniek zijn.
• Elke Sudoku begint met een aantal gegeven startwaarden.

Cream CSP Framework

Cream bestaat uit een Netwerk object waarin je de variabelen (het Sudoku speelveld), het domein (de mogelijke waarden) en de constraints vastlegt. Cream gebruikt een wrapper voor integer variabelen (IntVariable) zodat het gemakkelijker is om deze constraints te bepalen. Indien x bijvoorbeeld van het type IntVariable is dan kunnen we zeggen: x.ge(1), wat betekent dat variabele x groter of gelijk aan 1 moet zijn. De constraints kunnen bijna letterlijk uit de Sudoku regels worden overgenomen. In het onderstaande code fragment wordt aangegeven dat alle waarden in een rij uniek moeten zijn. In het bijgevoegde complete voorbeeld zijn de andere constraints opgenomen [5]. Daarna worden een aantal startwaarden gegeven waarna een Solver het probleem probeert op te lossen.

        Network net = new Network();
        // Een Sudoku speelveld bestaat uit 9 rijen en 9 kolommen.
        IntVariable[][] s = new IntVariable[9][9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                s[r][c] = new IntVariable(net);
            }
        }
        // Elk veld moet een waarde tussen 1 en 9 hebben
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                s[r][c].ge(1);
                s[r][c].le(9);
            }
        }
        // Elke waarde in een rij moet uniek zijn
        for (int r = 0; r < 9; r++) {
            new NotEquals(net, s[r]);
        }
        // Elke waarde in een kolom moet uniek zijn
        // ...
 
        // Het speelveld is onderverdeeld in 3x3 subvelden
        // van 3 rijen en 3 kolommen
        // Elke waarde in een subveld moet uniek zijn
        // ...
 
        // Elke Sudoku begint met een aantal gegeven startwaarden
        // 0,0 is linksboven
        s[0][0].equals(2);
        s[0][1].equals(9);
        // ... etc.
 
        // initialiseer de solver en print oplossing(en)
        Solver solver = new DefaultSolver(net);
        for (solver.start(); solver.waitNext(); solver.resume()) {
            Solution solution = solver.getSolution();
            for (int r = 0; r < 9; r++) {
                for (int c = 0; c < 9; c++) {
                    int v = solution.getIntValue(s[r][c]);
                    System.out.print(v + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
        solver.stop();

Bij een willekeurige Sudoku uit de krant was dat op mijn computer binnen 100 ms! Als je deze startwaarden niet geeft (of minder) dan zal de Solver gewoon alle mogelijke oplossingen geven, waarvan de eerste wel even op zich kan laten wachten.

Conclusie

Het blijkt erg makkelijk om met een CSP framework een Sudoku op te lossen met zeer weinig regels code. Het meeste werk zit er in om de regels te vertalen in voor het CSP framework begrijpelijke constraints.

Resources
[1] Solving Constraint Satisfaction Problems in JavaJ-Fall 2008
[2] Aircraft Scheduling, DNA Sequencing & Sudoku – Solving Constraint Satisfaction Problems with Java
[3] ILog JSolver
[4] Cream CSP Framework
[5] sudoku.java