hakank.blogg

september 28, 2008

Constraint programming: Fler MiniZinc-modeller, t.ex. Martin Gardner och nonogram

Förutom att ha lekt med de Javabaserade villkorsprogrammeringssystemet Choco version 2 har även några MiniZinc-modeller skapats sen sist.

Förra gången räknades till cirka 360 modeller (stora eller små). Nu är det cirka 440 stycken (stora och små), vilket innebär cirka 80 nya modeller. Som vanligt finns de på My MiniZinc page. De läggs upp där så fort som de är klara, så om du är intresserad av nya modeller är det bara att - mer eller mindre - regelbundet kolla den sidan.

Denna gång har det blivit en del problem från husguden Martin Gardner, mest beroende på att jag håller på att beta av samlingen med Martin Gardners pyssel i The Colossal Book of Short Puzzles and Problems, (ISBN: 9780393061147, sammanställd av Dana Richards).

Personliga favoriter
* nonogram.mzn, även känd som "painting by numbers". Utifrån rad- och kolumnsummor ska man skapa bilder. Jämför med "discrete tomography" som nämndes i Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem samt med "Survo puzzle" som nämndes i Nästan 36 modeller med villkorsprogrammering (constraint programming) i MiniZinc.
* two_cube_calendar.mzn: Two cube calendar. Till synes enkelt problem, men det var trixigt att modellera eftersom en siffra kan användas på två olika sätt.
* diffn.mzn. Placering av boxar utan att de överlappar varandra. Stödjer tre olika representationer (vilket tyvärr gör modellen lite svåröverskådlig).
* calculs_d_enfer.mzn: Calculs d'enfer. Yet another alfametiskt problem med några twistar: här används även negativa värden och man ska minimera det största absolutvärdet. En viktig sak är att använda korrekt heuristik annars går det långsamt att lösa problemet: den snabbaste jag hittade var "occurrence" respektive "indomain_max".

Martin Gardner
Detta är några problem från de första kapiteln av (den ovan nämnda) The Colossal Book of Short Puzzles and Problems. En bok att rekommendera. Man noterar redan på de första sidorna (om man inte läst Gardner tidigare för då vet man troligen detta redan) att en del standardexempel - t.ex. SEND + MORE = MONEY, Langfords heltalssekvens - beskrevs eller populariserades av Martin Gardner.

Nedanstående har det gemensamma kännetecknet att de - mig veterligen - inte modellerats i MiniZinc. I vissa fall har jag inte sett någon diskussion alls på nätet (i alla fall inte under dessa namn).

curious_set_of_integers.mzn: Curious set of integers
divisible_by_7.mzn: Divisible by 7
gardner_prime_puzzle.mzn: Prime puzzle
magic_squares_and_cards.mzn: Magic squares and cards
nine_digit_arrangement.mzn: Nine digit arrangements
nine_to_one_equals_100.mzn: Nine to one equals 100
nonogram.mzn
pool_ball_triangles.mzn: Pool ball triangles
two_cube_calendar.mzn: Two cube calendar

Andra pyssel och matematiska gåtor
bank_card
calculs_d_enfer.mzn: Calculs d'enfer puzzle (from the NCL manual), se kommentar ovan
coins_problem.mzn: Minimize the number of coins...
family_riddle.mzn: Family riddle
magic_hexagon.mzn: Magic hexagon
message_sending: Message sending

Operations research, linear programming, integer programming
lectures: ett scheduleringsproblem
scheduling_chip: ännu ett scheduleringsproblem

Non linear problems
spreadsheet.mzn, exempel på problem som ofta löses i spreadsheets

Combinatorics
maximum_subarray.mzn: Maximum subarray
set_packing.mzn, set packing
set_covering_skiena.mzn, set covering (ännu ett exempel)
all_paths_graph.mzn, skapa vägar med utgångspunkt från en grafrepresentation

Global constraints
Som vanligt har även några global constraints modellerats. Förutom att många av dem är nyttiga i sig, är modelleringen av dem en nyttig övning. (Nu finns det cirka 100 global constraints modellerade, endast en tredjedel av den fulla listan. I och för sig är cirka 40-50 global constraints redan definierade i MiniZinc, antingen inbyggda eller i global.mzn, men det är i alla fall en massa kvar...)

contains_array
cumulative_test
diffn
discrepancy
disjunctive
domain
domain_constraint
imply
in_interval
in_set
indexed_sum
inverse_within_range
ith_pos_different_from_0
k_same
k_same_modulo
lex2
lex_between
lex_chain_less
lex_different
lex_greater
max_index
min_index
nclass
open_alldifferent
product_test
roots_test
same_interval
same_modulo
shift
sliding_sum
sliding_time_window
sliding_time_window_from_start
smooth
soft_same_var
sort_permutation
weighted_sum (not in the catalogue)

Prolog/constraint logic programming benchmarks
Här är några benchmarks för Prolog eller constraint programming som inte tidigare modellerats i MiniZinc.

crossbar.mzn
crypta.mzn
eq10.mzn
fractions.mzn
grocery2.mzn
magic3.mzn
magic4.mzn
multipl.mzn
olympic.mzn
parallel_resistors.mzn
sudoku_25x25_250.mzn
voltage_divider.mzn

Övrigt
fizz_buzz Liten programmeringsövning
huey_dewey_louie, litet logiskt problem
power, variant av power-funktionen (som ännu inte funkar i MiniZinc)

Posted by hakank at 08:17 EM Posted to Constraint Programming | Matematik | Pyssel | Comments (0)

september 14, 2008

Constraint programming i Java: Choco version 2 släppt - samt jämförelse med JaCoP

I JaCoP - Java Constraint Programming solver gjordes en jämförelse mellan två olika constraint programming system (villkorsprogrammering) i Java:
- JaCoP (se även My JaCoP page)
- Choco (My Choco page)

Då avvaktade jag med framförallt modeller i och mer information om Choco tills det var mer stabilt (beta-versionen har ändrats mycket den senaste tiden) Det är det nu: I onsdags (10 september 2008) släpptes version 2.0 (lagom till internationella constraint programming-kongressen som börjar idag, se nedan under Relaterat). Denna version har en ny hemsida (cf. sidan för Choco version 1).

Choco version 2

The CHOCO development team is eager to announce the release of the new version of its open-source constraint solver: CHOCO.

Choco is Java library that can be used for:
* teaching (a user-oriented constraint solver with open-source code)
* research (state-of-the-art algorithms and techniques, user-defined constraints, domains and variables)
* real-life applications (many application now embed choco)

Choco is final-user oriented. It has been under heavy refactoring from V1 to V2. New constraints, new features have been offered.

Choco is available online with a complete documentation, tutorials, various materials, forums, etc.

Dokumentation

Sajten innehåller följande huvuddelar:

• News
  
• Download
  
• Documentation
  
• Tutorials
  
• FAQ
  
• Constraints. En listning över samtliga constraints; de allra flesta länkarna har en model som exempel.
  
• Forum. Det finns även en mailinglista, och andra forum (som har handlat mest om Choco version 1).
  
• Developers, TODO:s buggfixar.
  
• Sajten för Choco version 1
  

Ett exempel: Minesweeper

Jag har tagit bort en del saker för att göra listningen kortare. Den fullständiga modellen finns i MineSweeper.java.

Den observante kan notera att det är i stort sett samma modell, med endast några få skillnader:
- namn på variablerna: IntegerVariable i Choco, FDV i JaCoP
- metod att skapa variabler: makeIntVar(...) respektive new FDV(store,...). Notera att Choco har en metod för att initiera en array: makeIntVarArray.
- metod för att ange villkoren: model.addConstraint respektive store.impose
- själva villkoren (constraints), i choco behöver man inte new:a dessa villkor. Se mer om villkoren nedan.

public class MineSweeper {
    int r;        // number of rows
    int c;        // number of cols
    int X = -1;  // represents the unknown value in the problem matrix
    int[][] problem; // The problem matrix
    IntegerVariable[][] game;    // The IntegerVariable version of the problem matrix.
    IntegerVariable[][] mines;   // solution matrix: 0..1 where 1 means mine.
    Model model;
    CPSolver s;
    public void model() {
        model = new CPModel();
        if (problem == null) {
            r = 8;
            c = 8;
            int problemX[][] = {{X,2,X,2,1,1,X,X},
                                {X,X,4,X,2,X,X,2},
                                {2,X,X,2,X,X,3,X},
                                {2,X,2,2,X,3,X,3},
                                {X,X,1,X,X,X,4,X},
                                {1,X,X,X,2,X,X,3},
                                {X,2,X,2,2,X,3,X},
                                {1,X,1,X,X,1,X,1}};
            problem = problemX;
        }
        /*
         * Initialize the constraint variables.
         */
        mines = new IntegerVariable[r][c];
        game  = new IntegerVariable[r][c];
        for(int i = 0; i < r; i++) {
            mines[i] = makeIntVarArray("m_" + i, c, 0,1);
            game[i] = makeIntVarArray("g_" + i, c, -1,8);
        }
        // Add the constraints
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // This is a known value of neighbours
                if (problem[i][j] > X) {
                    // mirroring the problem matrix.
                    model.addConstraint(eq(game[i][j], problem[i][j]));
                    // This could not be a mine.
                    model.addConstraint(eq(mines[i][j], 0));
                    // Sum the number of neighbours: same as game[i][j].
                    ArrayList lst = new ArrayList();
                    for(int a = -1; a <= 1; a++) {
                        for(int b = -1; b <= 1; b++) {
                            if (i+a >= 0 && j+b >=  0 &&
                                i+a < r && j+b < c) {
                                lst.add(mines[i+a][j+b]);
                            }
                        }                        
                    }
                    model.addConstraint(eq(sum(lst.toArray(new IntegerVariable[1])), game[i][j]));
                } // end if problem[i][j] > X
            } // end for j
        } // end for i
    } // end model
   //
   // Search
   //
    public void search() {
        s = new CPSolver();
        s.read(model);
        s.solve();        
        if (s.isFeasible()) {
            int sol = 1;
            do {
                System.out.println("\nSolution # " + sol);
                for(int i = 0; i < r; i++) {
                    for(int j = 0; j < c; j++) {
                        System.out.print(s.getVar(mines[i][j]).getVal() + " ");
                    }
                    System.out.println();
                }
                sol++;
            } while (s.nextSolution() == Boolean.TRUE);
        } else {
            System.out.println("No solutions.");
        } // end if result
    } // end search
   //
   // Main
   //
    public static void main(String args[]) {
        MineSweeper minesweeper = new MineSweeper();
        String file = "";
        if (args.length > 0) {
            file = args[0];
            minesweeper.readFile(file);
        }
        minesweeper.model();
        minesweeper.search();
    } // end main
} // end class

Resultatet:

readFile(minesweeper0.txt)
6
6
..2.3.
2.....
..24.3
1.34..
.....3
.3.3..
22[+0] millis.
16[+0] nodes
20[+0] backtracks
20[+0] fails

Solution # 1
1 0 0 0 0 1
0 1 0 1 1 0
0 0 0 0 1 0
0 0 0 0 1 0
0 1 1 1 0 0
1 0 0 0 1 1


Fördelar/nackdelar

* Exempel. Till skillnad från JaCoP så finns det inte så många fullständiga exempel i distributionen. Några av exemplen är kvar från version 1 och är inte portade till version 2 (koden är helt enkelt bortkommenterad). Det är lite synd. I gengäld finns många test cases för i stort sett samtliga metoder i systemet, vilket är informativt.

* Dokumentation. Som ovan sagt är dokumentationen (på sajten) mycket bra och förklarar i stort sett allting. Man bör dock notera att eftersom den slutliga version 2 är så pass ny finns det några ställen där man inte uppdaterat till denna version. Några constraints är inte heller dokumenterade. Jag antar att allt sådant kommer att fixas till snart.

* Domäner. Choco styrka är finita domäner (heltal eller sådant som kan representeras av heltal), men kan - till skillnad från JaCoP - hantera mängder (sets) samt flyttal. Stödet för de två sistnämda är dock inte lika stort eller stablilt som för finita domäner.

* Global constraints. På sidan Constraints presenteras de (global) constraints som finns i systemet. De flesta förväntade finns med såsom allDifferent, boolChanneling, distance etc. Jag blev dock lite förvånad att count (villkor för att ange att ett visst värde ska ha ett visst antal förekomster) saknades. I YoungTableaux behövdes nämligen ett sådant villkor, men det implementerades i stället genom att trixa med globalCardinality (en generalisering av count).

Speciellt intressant är de relativt nya geost för att hantera geometriska villkor, och tree för "tree partitioning".

Man kan också notera att det finns en viss skillnad i inställning av "convenient constraints" mellan Choco och JaCoP. Efter en fråga till JaCoPs utvecklare om varför villkoret XminusYeqZ saknades kom svaret att man följer en minimalistisk princip att endast implementera de nödvändiga villkoren (man kan använda XplusYeqZ i stället). I Choco verkar man inte ha denna princip: där finns såväl plus som minus; man kan initiera en hel vektor på ett bräde med makeVarIntArray och behöver inte loopa över elementens makeVarInt etc.

* XCSP. XCSP är ett XML-format för constraint satisfaction/programming-problem som används bl.a. i Third International CSP Solver Competition (se även nedan under Relaterat). Choco kan läsa i detta format. Efter de tester jag gjort tycker jag att Chocos stöd är något bättre än JaCoPs. Choco kan dock inte skriva XCSP (det kan JaCoP), men det är på gång.

* Prestanda. Jag har inte gjort några formella tester men min känsla är att Choco nästan alltid är snabbare och kan hantera större problem än JaCoP. Men det är alltså en subjektiv åsikt.

* Open source. Choco är open source till skillnad från JaCoP vilket naturligtvis är en stor fördel. JaCoP kommer enligt uppgift att släppas öppet inom kort, men än så länge finns det inte fritt tillgängligt.

Det finns ett Subversion-repositorium på https://choco.svn.sourceforge.net/svnroot/choco . Jag använder fortfarande version 2.0.0 men kommer väl snart att gå över till 2.0.1 (som skapades i förrgår, dvs strax efter den officiella releasen).

Slutkommentar
I och för sig tycker jag om JaCoP eftersom det har en slim och "naturlig" klassmodell, har många exempel. Trots det kommer jag nog mestadels att använda Choco för villkorsprogrammering i Java eftersom det är (än så länge) ett mer fullständigt system, har bättre dokumentation och drivs av fler utvecklare (vad jag förstår är det åtminstone en heltidstjänst enkom för att utveckla Choco).

Mina Choco-modeller

Modellerna är (direkt från sidan):

• CoinsGrid.java: Coins grid problem from Tony Hürlimann: "A coin puzzle - SVOR-contest 2007".
  
• DeBruijn.java: de Bruijn sequences, both "normal" and "arbitrary".
  Usage: java DeBruijn base n (m)
  where base is the base to work with, n is the "bit length" and m the optional length of the sequence (default length is base^n).
• Diet.java: Simple diet problem.
• FurnitureMoving.java: Simple task optimization using cumulative.
• LeastDiff2.java: Least diff problem, an alphametic puzzle, minimize the difference ABCDE-FGHIJ where A..J is integers 0..9 (all different)
• MineSweeper.java: Minesweeper problem.
  Problem files for the Minesweeper program.
  Usage: java Minesweeper problem file
  
  • Problem 0 from Gecode minesweeper.cc
  • Problem 1 from Gecode minesweeper.cc
  • Problem 2 from Gecode minesweeper.cc
  • Problem 3 from Gecode minesweeper.cc
  • Problem 4 from Gecode minesweeper.cc
  • Problem 5 from Gecode minesweeper.cc
  • Problem 6 from Gecode minesweeper.cc
  • Problem 7 from Gecode minesweeper.cc
  • Problem 8 from Gecode minesweeper.cc
  • Problem 9 from Gecode minesweeper.cc
  • From "Some Minesweeper Configurations", page 2
  • From "Some Minesweeper Configurations", page 3
  • From Richard Kaye: "How Complicated is Minesweeper?", splitter (131072 solutions)
  • From Richard Kaye: "How Complicated is Minesweeper?", wire
• QuasigroupCompletion.java: Quasigroup completion problem.
  Problem files:
  
  • quasigroup1.txt
  • quasigroup2.txt
  • quasigroup3.txt
  • quasigroup4.txt
  • quasigroup5.txt
  • quasigroup6.txt
  • quasigroup7.txt
  • quasigroup8.txt
  • quasigroup9.txt
• Seseman.java: Seseman convent problem, a simple recreational mathematics puzzle.
• SurvoPuzzle.java: Survo puzzle.
  Problem files:
  
  • survo_puzzle_126_2008.txt
  • survo_puzzle_127_2008.txt
  • survo_puzzle_128_2008.txt
• YoungTableuax.java: Young tableaux and partitions

Relaterat

Intressant nog börjar stora villkorsprogrammeringskonferensen International Conference on Principles and Practice of Constraint Programming idag och håller på till 18 september. Jag väntar speciellt med spänning på resultatet av två olika tävlingar:
- Third International CSP Solver Competition
- MiniZinc Challenge 2008 (Rules). En av utvecklarna av MiniZinc har antytt att några av mina MiniZinc-modeller med på ett hörn i denna tävling.

Posted by hakank at 10:56 FM Posted to Constraint Programming | Pyssel | Comments (0)

augusti 30, 2008

Ubiquity 0.1 - kommandoradsfunktionalitet i Firefox

Den senaste veckan har det pratats en del om version 0.1 av Firefox-tillägget Ubiquity från Mozilla Labs. Här är några kommentarer efter en första sittning.

Och det är helläckert!

Med en enkel tangentbordskombination (Alt-mellanslag i min Firefox 3.0 + Mandriva Linux) får man upp en "kommandorad" där man kan skriva in kommandon. Detta kallas för "Ubiq", vilket på svenska torde bli "att ubiqa" (eller möjligen "att ubika").

En mycket trevlig introduktion av funktionaliteten, inklusive en kort video, görs i Introducing Ubiquity.

Exempel

google

google Ubiquity


gör en googlesökning på sökfrasen "Ubiquity".

this
Stöter man på en fras (t.ex. "constraint programming") kan man markera den och sedan ubiqa med


wiki this


varpå en Wiki-sökning görs. this avser det markerade området:. Man skriver alltså this.

translate
Markera en engelsk fras och ubiqa


translate this from english to swedish


Översättningen visas redan i previewfältet så man behöver inte ens exekvera kommandot. Riktigt trevligt.

Den finns stöd för en massa andra sökmotorer etc. såsom Yahoo, IMDB etc.

Andra kommandon som är bra att känna till:

* command-list: Visar vilka kommandon som finns tillgängliga för tillfället i browsern, inklusive egentillverkade (se nästa avsnitt).

Skriva egna Ubiquity-kommandon

Instruktioner hur man skapar egna kommandon finns i Author Tutorial, där det finns mycket mer avancerade saker än nedanstående.

För att testa kommandona använder man en webbaserad kommandoeditor via kommandot command-editor, där man skriver in kommandona. Man behöver inte göra något speciellt mer än skriva (eller klistra in) koden, saker sker automatiskt i bakgrunden.

Det första exemplet är en sökning på Bokus och den andra en sökning på knuff.se. Det är inte rocket science, men funkar. (Jag har inte laborerat med mer de avancerade preview-funktionerna speciellt mycket.)


makeSearchCommand({
name: "bokus",
url: "http://www.bokus.com/cgi-bin/book_search.cgi?FAST={QUERY}",
icon: "http://www.bokus.com/favicon.ico",
description: "Searches Bokus for your books, movies, and games.",
preview: function(pBlock, directObj) {
if (directObj.text)
pBlock.innerHtml = "Searches Bokus for " + directObj.text;
else
pBlock.innerHTML = "Searches Bokus for the given words.";
}
});

Det enda man egentligen behöver veta för att göra liknande kommandon är sökurlen och sedan byta ut sökfrasen med {QUERY}.

Man kan nu testa detta med


bokus constraint programming


eller för att söka på ett ISBN som man ser hos sin favoritblogg: 9780140286809 . Märk detta och skriv


bokus this


(Boken har inget med Ubiquity att göra - mer än möjligen indirekt genom associationer.)


knuff Ubiquity


som ger följande resultat.

För mer persistent användning av kommandona, för att ge sina medmänniskor tillgång till dem - och eventuellt "prenumerera" för att få automatiska uppdateringar - bör man publicera koden någonstans på webben. Läs i Author Tutorial hur man gör detta.

Jag har dock inte publicerat någon sådan sida. Eventuellt kommer det senare.

Säkerhet

Detta sagt, testa gärna funktionaliteten, men prenumerera inte på något som du inte känner till/litar på.

Några andra kommentarer

* De speciella internationella tecknen (framförallt "å", "ä" och "ö") stökade i kommandot translate, möjligen är det något konstigt i min miljö...

* Vissa kommandon, t.ex. translate skriver in texten där (mus)markören befinner sig. Vad jag vet finns det inget sätt att ångra detta utan man måste ladda om sidan igen för att ta bort texten. Jag trodde att undo skulle göra det, men icke.

* Detta är version 0.1 och mycket kommer säkerligen att ändras...

* För övrigt påminner detta en del om programmeringsspråket/-miljön Rebol.

Länkar

* Wiki: Ubiquity
Introducing Ubiquity
* Google-gruppen ubiquity-firefox
* User Tutorial
* Author Tutorial
* Forum

Posted by hakank at 10:18 EM Posted to Program | Sökmotorer | Comments (4)

augusti 23, 2008

Nästan 36 modeller med villkorsprogrammering (constraint programming) i MiniZinc

(Språklig not: Av någon anledning tycker jag inte riktigt om namnet "villkorsprogrammering" utan använder hellre det engelska "constraint programming", men det svenska namnet är vedertaget framförallt i vissa utbildningscentra så det måste nämnas emellanåt.)

Sedan sist har fler MiniZinc-modeller skapats. Det finns nu över 360 .mzn-filer - modeller och datafiler - på My MiniZinc page och det känns därför som rätt tillfälle att rensa lite från inkorgen, närmare bestämt nedanstående nästan 36 modeller. Grupperingen här nedan är inte riktigt samma som på MiniZinc-sidan.

Referenser till problemformulering/originalmodell/inspiration finns som vanligt i respektive modell.

Personliga favoriter

Modeller

Kombinatorik/global constraints
* Dominating Set
* Graph Degree Sequence
* Stretch circuit
* Subsequence sum

Operations research
* Data Envelopment Analysis (DEA) model. (För tillfället är det endast ECLiPSe's eplex-solver som klarar detta.)

Enigma-pyssel
* Enigma eighteen
* Five fives
* Eight times
* Eight times 2, alternativ modell
* Planets

Dell Logic Puzzles
Logiska problem från brownbuffalo.sourceforge.net.
* Tunapalooza
* A round of golf
* Arch friends
* Four islands
* Breaking news
* Baby sitting
* Lecture series

100 dörrars-problemet
Problemformulering t.ex. hos Rosetta code.
* 100 doors problem, unoptimized (version 1)
* 100 doors problem, unoptimized (version 2)
* 100 doors problem, optimized, using set representation
* 100 doors problem, optimized, using array representation

Andra pyssel
* Clock triplets
* Franklin's 8x8 magic square
* Magic sequence, version 3 (en av flera varianter)
* Murder: Ett mord har begåtts ..(logiskt pysse)
* Number Generation, generalisering av Devil's Word (devils_word.mzn respektive Devil's word CGI-program).
* Self Referential Quiz
* Survo puzzle

Två exempel från Constraint Processing skriven av Rina Dechter
* Nadel's construction problem, sidan 5
* Scheduling speakers, sidan 72

Två exempel från theorem proving (automated reasoning)
* Jobs puzzle
* Who killed Agatha?

Övriga modeller
* Family, familjeträd, ett standard Prologprogram formulerat i MiniZinc
* ISBN: en etyd i konstruktion av ISBN-13 (med kontrollsiffra)

Posted by hakank at 08:35 FM Posted to | Comments (0)

augusti 19, 2008

Digital grusväg 1/2008 ute!

Via ett personligt epost-meddelande erhölls den glädjande nyheten att Digital Grusväg (Aperiodisk tidskrift) numro 1 anno 2008 är officiell. För att citera (delar av relevanta) delar av mailet:

I detta nummer...Vad är det i mjölken? Har sista bussen gått?

Samtidigt kan passas på att tipsas om Nerdlunchers (kreativitetens högborg på nätet, som lyckats lokalisera tillståndet av total förvirring, vilket dock måste sägas inte råder å nämnda nätplats), speciellt Wikin där Hr. Grusväg emellanåt och från tid till annan smular sitt oefterlikneliga grus.

Tidigare här på bloggen diskussioner diskuterar sådant som namnets ("Digital Grusväg"s) tillkommande (ehuru länkar är - som vanligt i denna av regn småningom fyllda spindelvävsvärld - inaktuella) .

Posted by hakank at 07:32 EM Posted to Diverse | Comments (0)

augusti 17, 2008

JaCoP - Java Constraint Programming solver

Fast det jag egentligen hållit på med den senaste veckan är att kolla in JaCoP, ett (annat) constraint programming-system i Java.

Det som beskrivs här nedan är JaCoP version 2. Information om version 1.3 finns på ett annat ställe (LTH, Lunds Universitet), men det är alltså 2:an som gäller.

JaCoP

Java Constraint Programming solver, JaCoP in short, is a Java library, which provides Java user with Constraint Programming technology. JaCoP is actively developed since year 2001. Krzysztof Kuchcinski and Radoslaw Szymanek are the authors of this Java library. They are working in their free time to improve this library. They both have worked countless hours to create software which is frequently used not only in their research work.

...

JaCoP is available for free as Java library for research and educational purposes. JaCoP is not free for commercial applications. However, our intention is to charge minimum fees in order to have some additional help in creating better documentation and better product.

I JaCoP google group berättas att man har planer att skapa en "dual license" (dvs både en fri och en komersiell licens).

För att få tillgång till JaCoP-distributionen måste man - än så länge - maila Radoslaw Szymanek (radoslaw.szymanek@gmail.com ) med en förfrågan, helst på engelska. Berätta gärna att du läste om JaCoP här.

Dokumentation

På SudukoACSP förklaras detaljerat och pedagogiskt om de viktigaste JaCoP-metoderna via lösning av Sudoku-spelet. Rekommenderad läsning.

Man kan ställda frågor på JaCoPFAQ (kräver registrering).

En PDF-presentation Introduction to JaCoP för version 1 finns på kurssidan EDA340: Constraint Programming (LTH, Lunds Universitet).

Ett exempel: Minesweeper

En stor skillnad mellan MiniZinc-modellen och JaCoP-modellen är - förutom att JaCop-modellen är mer pratig - att det finns stöd för att läsa in externa problem-filer (MiniZinc har ett annat sätt att lösa detta).

Input till programmet är en problemfil, t.ex. minesweeper0.txt:

# Minesweeper problem.
# This problem file is used by
# http://www.hakank.org/JaCoP/MineSweeper.java
#
# Problem from Gecode/examples/minesweeper.cc problem 0
6
6
..2.3.
2.....
..24.3
1.34..
.....3
.3.3..


Här nedan visas de mest relevanta delarna av programmet. Det är alltså inte ett komplett program.

import JaCoP.constraints.*;
import JaCoP.core.*;
import JaCoP.search.*;
public class MineSweeper {
    // declare the variables
    int r;        // number of rows
    int c;        // number of cols
    int X = -1;  // represents the unknown value in the problem matrix
    int[][] problem; // The problem matrix
    FDV[][] game;    // The FDV version of the problem matrix.
    FDV[][] mines;   // solution matrix: 0..1 where 1 means mine.
    Store store;
    public void model() {
        store = new FDstore();
        // Initialize the constraint variables.
        mines = new FDV[r][c];
        game  = new FDV[r][c];
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // 0: no mine, 1: mine
                mines[i][j] = new FDV(store, "m_" + i + "_" + j, 0, 1);
                // mirrors the problem matrix
                game[i][j] = new FDV(store, "g_" + i + "_" + j, -1, 8);
            }
        }
        // Add the constraints
        for(int i = 0; i < r; i++) {
            for(int j = 0; j < c; j++) {
                // This is a known value of neighbours
                if (problem[i][j] > X) {
                    // mirroring the problem matrix.
                    store.impose(new XeqC(game[i][j], problem[i][j]));
                    // This could not be a mine.
                    store.impose(new XeqC(mines[i][j], 0));
                    // Sum the number of neighbours: same as game[i][j].
                    ArrayList lst = new ArrayList();
                    for(int a = -1; a <= 1; a++) {
                        for(int b = -1; b <= 1; b++) {
                            if (i+a >= 0 && j+b >=  0 &&
                                i+a < r && j+b < c) {
                                lst.add(mines[i+a][j+b]);
                            }
                        }                        
                    }
                    store.impose(new Sum(lst, game[i][j]));
                } // end if problem[i][j] > X
            } // end for j
        } // end for i
    } // end model

Till skillnad från MiniZinc (men i likhet med Choco, Gecode etc) måste man uttryckligen ange vilken sökmetod som ska användas. Här används metoden SimpleMatrixSelect över variabelmatrisen mines. Här skrivs endast den sista lösningen ut.

    public void search() {
        SelectChoicePoint select = 
            new SimpleMatrixSelect (mines,
                              new SmallestDomain(),
                              new IndomainMin ()
                              );
        Search label = new DepthFirstSearch ();
        label.getSolutionListener().searchAll(true);
        label.getSolutionListener().recordSolutions(true);
        boolean result = label.labeling(store, select);
        int numSolutions = label.getSolutionListener().solutionsNo();
        if (result) {
            System.out.println("\nThe last solution:");
            for(int i = 0; i < r; i++) {
                for(int j = 0; j < c; j++) {
                    System.out.print(mines[i][j].value() + " ");
                }
                System.out.println();
            }
            System.out.println("numSolutions: " + numSolutions);
        } else {
            System.out.println("No solutions.");
        } // end if result
    } // end search