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

Choco presenteras så här:
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


Till skillnad från JaCoP finns det mycket dokumentation om Choco, t.ex. en bra och inträngande genomgång hur man skapar modeller, tweakar lösningar och mer avancerade användningar.

Sajten innehåller följande huvuddelar:


Ett exempel: Minesweeper


I JaCoP - Java Constraint Programming solver presenterades JaCoP-modellen för Minesweeper. Här är motsvarande modell i Choco. Input till programmet är en problemfil, t.ex. minesweeper0.txt.

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

På My Choco page finns ett antal Choco-modeller. Det är (i skrivande stund) en portning av de modeller som finns (i skrivande stund) på My JaCoP page (förutom DeBruijnIterate som var en specialmodell för att generera lösningar batch-vis).

Modellerna är (direkt från sidan):


Relaterat


Choco: Constraint Programming i Java om Choco version 1, som skrev i april 2006.


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 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


JaCoP presenteras på följande sätt:

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


JaCoP Web är stället där man hittar information om systemet. Tyvärr finns ännu inte så mycket dokumenterat för version 2, vilket är en stor nackdel. I distributionen finns ett stort (>= 57) antal exempel som gör att man får bra tips hur JaCoP används (eventuellt finns någon av nedanstående modeller med). Man lär sig även mycket genom att studera den övriga källkoden.

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


Här nedan visas ett exempel av ett JaCoP-program. Jag har valt Minesweeper ("MS Röj") för enkel jämförelse med MiniZinc modellen på Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life.

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.

(Jag har önskat en möjlighet att skriva ut samtliga lösningar via en iterator istället för att alla lösningar räknas ut innan presentationen, och det kanske kommer.)

    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


Fördelar/nackdelar


Här är några kommentarer om JaCoP.

Intrycket efter en vecka är att det är ett trevligt system, och för det mesta är det naturligt hur man programmerar modellerna. De lite mer avancerade modellerna nedan, Minesweeper och de Bruijn sekvenser, portades från MiniZinc-modellerna ganska rakt av och utan några större problem. Det är naturligtvis en fördel att ha modellerat en hel del constraint programming-problem innan.

* Bra exempel. Det finns många exempel som visar hur man använder JaCoP. Många är standardexempelmen det finns några nya saker.

* Dokumentation. En av de stora nackdelarna är avsaknaden av dokumentation, men eftersom det är en enkel klassstruktur är det rätt enkelt att hitta constraints (de finns i katalogen JaCoP/constraints och sökmetoderna (JaCoP/search.

* Finita domäner. JaCoP hanterar endast finita domäner, dvs stöd för mängder (sets) saknas, liksom flyttal. Det senare gör inte så mycket för min egen del, däremot saknar jag sets för modellering av en del problem. En kommentar om detta från utvecklaren av JaCoP finns här.

* Global constraints. JaCoP har ett antal global constraints, vilket förenklar både syntaktiskt och prestandamässigt.

* XCSP. XCSP är ett XML-format för constraint satisfaction/programming problem som används bl.a. i Third International CSP Solver Competition. JaCoP kan både läsa och skriva i detta format. Trevligt! (Tänk på att skapa XML-filen innan sökningen börjar, annars hårdkodas lösningen.)

* Prestanda. Jag har inte gjort några formella tester av hastighet eller minnesanvändning, men de flesta av mina modeller (se nedan) har lösts snabbt, åtminstone lika snabbt som den snabbaste av de solvers som finns för MiniZinc (vilket oftast är Gecode/fz).

* Java. Naturligtvis är det mestadels en fördel att använda ett "riktigt" programspråk och baka in stöd för constraint programming där. Ett exempel på detta är Minesweeper (och Quasigroup completion problem) där man kan läsa in problemfiler av godtyckligt format. Problemet är att det blir emellanåt väldigt pratigt, t.ex. just vid filinläsning, och det är något som jag inte tycker om (och är en stor orsak till min förtjusning över agila programspråk). Ett framtida projekt är att skriva om några modeller till Groovy.

* Jämförelse med Choco 2.0. När jag började med JaCoP så var ett av målen att jämföra med Choco version 2, ett annat constraint programming system i Java. Choco 2.0 är dock för närvarande i beta-status så jag avvaktar med detta till det blivit lite mer stabilt. (Det har tidigare skrivits om Choco version 1 här.)

Choco är mer kompetent än (existerande distribution av) JaCoP: mer dokumentation (både pedagogiska texter och JavaDoc), stöd för mängder och flyttal, och det finns mängder av test-program. Dock finns det betydligt färre "riktiga" exempel än för JaCoP.

Som sagt. Det är ett framtida projekt att jämföra JaCoP och Choco.

Mina JaCoP-modeller

På My JaCoP page har jag lagt ett antal modeller för version 2. Några av dem kräver utilitetsklassen HakankUtil.java. Samtliga program (i alla fall i nedanstående lista) finns även som MiniZinc-modell (MiniZinc är ett alldeles utmärkt verktyg för att prototypa constraint programming-problem).


Se även

* Sidan för JaCoP version 1. Där finns referenser som fortfarande är relevanta.

* Choco: Constraint Programming i Java där JaCoP nämns en passant som ett system att kolla in.

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

juli 20, 2008

Fler constraint programming-modeller i MiniZinc, t.ex. Minesweeper och Game of Life

Här är några fler MiniZinc modeller som skapats sedan sist. För en fullständig lista över samtliga publicerade modeller, se My MiniZinc page.

I samtliga modeller anges referenser, inspiration etc.

Personligen tycker jag följande modeller är lite kul:
* Minesweeper (som presenteras speciellt nedan)
* Game of Life
* Quasigroup completion problem (se nedan för ett antal testproblem)
* Födelsedagsproblemet


Minesweeper


Tänkte nämna något mer om Minesweeper.

Modellen till Minesweeper är - möjligen förvånansvärt - enkel. Notera att man s.a.s. "räknar baklänges": genom att summera minorna (mines) för att få de värden som ges i problemet (game). Sådant är typiskt i constraint programming.


% MiniZinc model for Minesweeper.
int: r; % rows
int: c; % column
int: X = -1; % the unknowns

% encoding: -1 for unknown, >= 0 for number of mines in the neighbourhood
array[1..r, 1..c] of -1..8: game;
array[1..r, 1..c] of var 0..1: mines;

constraint
forall(i in 1..r, j in 1..c) (
(
(game[i,j] >= 0 )
->
game[i,j] = sum(a,b in {-1,0,1} where
i+a > 0 /\ j+b > 0 /\
i+a <= r /\ j+b <= c
)
(mines[i+a,j+b])
)
/\
(game[i,j] > X -> mines[i,j] = 0)
/\
(game[i,j] = X <- mines[i,j] = 1)
)
;

Ett exempelproblem, där ett tal anger hur många bomber det finns som grannar och X att vi inte vet något om rutan (det kan vara en bomb men behöver inte vara det).

% Minesweeper example
r = 6;
c = 6;
game = array2d(1..r, 1..c, [
X,X,2,X,3,X,
2,X,X,X,X,X,
X,X,2,4,X,3,
1,X,3,4,X,X,
X,X,X,X,X,3,
X,3,X,3,X,X,
]);

Lösningen - som kommer blixsnabbt - är följande. Positionerna av bomberna markeras med 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

Minesweeper har visats vara ett s.k. NP-komplett problem, dvs ohyggligt svårt att lösa generellt för godtyckligt stora problem. De exempel som används i modellen är dock så (förhållandevis) små att lösningen kommer direkt.

Se vidare
Richard Kaye's Minesweeper Pages
Minesweeper (Wikipedia)
Ian Stewart on Minesweeper
The Authoritative Minesweeper: Articles and Announcements

Automatisk "lösning" av Minesweeper i Mozart/Oz där fler referenser ges.

Övriga modeller

Här är de övriga modellerna, grupperade enligt samma princip som på My MiniZinc page.

Puzzles, small and large

Global constraints

Operations research, linear programming, integer programming

  • Markov chains (fertlizer example from Taha "Operations Research")
  • Talent, exempel från ILOG OPL

Combinatorial problems

Other models


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

juli 07, 2008

Fler MiniZinc modeller kring recreational mathematics

I Martin Chlond's Integer Programming Puzzles i MiniZinc förevisades MiniZinc-modeller för Martin Chlonds Integer Programming Puzzles.

Här är några fler i samma stil (recreational mathematics) som jag just har lagt upp på min Minizinc-sida . Det är MiniZinc-modeller baserade på Chlonds Puzzle artiklar (och de där ingående integer programming-modellerna) i INFORMS Transactions on Education (en öppen tidskrift om operational research).


Och så några andra recreational mathematics modeller som publicerades samtidigt:

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

juli 04, 2008

Martin Chlond's Integer Programming Puzzles i MiniZinc

Som tidigare nämnts är Puzzles - Integer Programming in Recreational Mathematics en mycket trevlig samling pyssel skapad av Martin Chlond. De flesta problemen är klassiker inom området (recreational mathematics) och flera används som paradigmproblem i constraint programming eller integer programming.

I april skrevs MiniZinc-modeller för samtliga problem men jag har inte kommit loss att hyfsa till dem. Förrän nu. Samliga 48 problem har nu gåtts igenom så att de har en enhetlig struktur, kommentarer är på engelska etc.

Förutom MiniZinc-modellen nedan finns även en länk till Martin Chlonds lösning av problemet (oftast skrivet som en XPress Model, men de allra sista är i AMPL). MiniZinc-modellerna är i stort sett en konvertering av Chlonds modell. I några fall har flyttalsrepresentationer omvandlats till heltalsrepresentationer.

Nedanstående listning finns även på min MiniZinc-sida, men det blir en bättre bäring om de även listas här.

Martin Chlond's Integer Programming Puzzles

The collection is separated in four sections where the problems is presented:
* Integer Programming Puzzles section 1
* Integer Programming Puzzles section 2
* Integer Programming Puzzles section 3
* Integer Programming Puzzles section 4


Problems: Integer Programming Puzzles section 1
Solutions:
Twelve draughts puzzle (Chlond's solution)
Description : Twelve draughts puzzle Source : Boris Kordemsky - The Moscow Puzzles (P36)

Coin puzzle
(Chlond's solution)
Description : Coin puzzle
Source : Mathematical Puzzles of Sam Loyd (P111)

Egg basket puzzle
(Chlond's solution)
Description : Egg basket puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

Evens puzzle
(Chlond's solution)
Description : Evens puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P8)

Fifty puzzle
(Chlond's solution)
Description : Fifty puzzle
Source : The Puzzles of Sam Loyd (P 54)

Honey division puzzle
(Chlond's solution)
Description : Honey division puzzle
Source : H E Dudeney - Amusements in Mathematics

Wine cask puzzle
(Chlond's solution)
Description : Wine cask puzzle
Source : M Kraitchik - Mathematical Recreations (p 31)

Knight domination puzzle - all squares threatened
(Chlond's solution)
Description : Knight domination puzzle - all squares threatened
Source : M Kraitchik - Mathematical Recreations (P256)

Mango puzzle
(Chlond's solution)
Description : Mango puzzle
Source : M Kraitchik - Mathematical Recreations (P32)

Remainder puzzle
(Chlond's solution)
Description : Remainder puzzle
Source : Boris Kordemsky - The Moscow Puzzles (P136)

5 X 5 puzzle
(Chlond's solution)
Description : 5 X 5 puzzle
Source : Unknown

Lights on puzzle
(Chlond's solution)
Description : Lights on puzzle
Source : Unknown


Problems: Integer Programming Puzzles section 2

Solutions:
Clarke's tobacconist
(Chlond's solution)
Description : Clarke's tobacconist
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Tommy's Birthday Coins
(Chlond's solution)
Description : Tommy's Birthday Coins
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Lewis Carroll coin puzzle
(Chlond's solution)
Description : Lewis Carroll coin puzzle
Source : Wakeling, E., (1995), Rediscovered Lewis Carroll Puzzles, Dover.

Dudeney's tea mixing problem
(Chlond's solution)
Description : Dudeney's tea mixing problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Jive turkeys
(Chlond's solution)
Description : Jive turkeys
Source : rec.puzzles

Public School Problem
(Chlond's solution)
Description : Public School Problem
Source : Clarke, L.H., (1954), Fun with Figures, William Heinemann Ltd.

Dudeney's bishop placement problem I
(Chlond's solution)
Description : Dudeney's bishop placement problem I
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Dudeney's bishop placement problem II
(Chlond's solution)
Description : Dudeney's bishop placement problem II
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Kraitchik's queen placement problem
(Chlond's solution)
Description : Kraitchik's queen placement problem
Source : Kraitchik, M., (1942), Mathematical Recreations, W.W. Norton and Company, Inc.

Schuh's queen placement problem
(Chlond's solution)
Description : Schuh's queen placement problem
Source : Schuh, F., (1943), Wonderlijke Problemen;
Leerzam Tijdverdrijf Door Puzzle en Speel, W.J. Thieme & Cie, Zutphen.

Dudeney's queen placement problem
(Chlond's solution)
Description : Dudeney's queen placement problem
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Joshua and his rats
(Chlond's solution)
Description : Joshua and his rats
Source : Sole, T., (1988), The Ticket to Heaven, Penguin Books


Problems: Integer Programming Puzzles section 3

Solutions:
The Abbott's Puzzle
(Chlond's solution)
Description : The Abbott's Puzzle
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The Abbott's Window
(Chlond's solution)
Description : The Abbott's Window
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The First Trial
(Chlond's solution)
Description : The First Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Second Trial
(Chlond's solution)
Description : The Second Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Third Trial
(Chlond's solution)
Description : The Third Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fourth Trial
(Chlond's solution)
Description : The Fourth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Fifth Trial
(Chlond's solution)
Description : The Fifth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The Sixth Trial
(Chlond's solution)
Description : The Sixth Trial
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

Werewolves II
(Chlond's solution)
Description : Werewolves II
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Werewolves IV
(Chlond's solution)
Description : Werewolves IV
Source : Smullyan, R., (1978), What is the Name of this Book?, Prentice-Hall

Earthlings
(Chlond's solution)
Description : Earthlings
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling

Equal Vision
(Chlond's solution)
Description : Equal Vision
Source : Poniachik, J. & L., (1998), Hard-to-solve Brainteasers, Sterling


Problems: Integer Programming Puzzles section 4

Solutions:
On the road
(Chlond's solution)
Description : On the road
Source : Poniachik, J. & L, (1998), Hard-to-solve Brainteasers, Sterling

The Riddle of the Pilgrims
(Chlond's solution)
Description : The Riddle of the Pilgrims
Source : Dudeney, H.E., (1949), The Canterbury Puzzles, 7th ed., Thomas Nelson and Sons.

The Logical Labyrinth
(Chlond's solution)
Description : The Logical Labyrinth
Source : Smullyan, R., (1991), The Lady or The Tiger, Oxford University Press

The gentle art of stamp-licking
(Chlond's solution)
Description : The gentle art of stamp-licking
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

The crowded board
(Chlond's solution)
Description : The crowded board
Source : Dudeney, H.E., (1917), Amusements in Mathematics, Thomas Nelson and Sons.

Non-dominating queens problem
(Chlond's solution)
Description : Non-dominating queens problem
Source : http://www.cli.di.unipi.it/~velucchi/queens.txt

Enigma
(Chlond's solution)
Description : Enigma
Source : Herald Tribune circa November 1979 - courtesy of Dr Tito A. Ciriani

Price change puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations (p 33-35), Dover

Book buy puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Shopping puzzle
(Chlond's solution)
Source: M Kraitchik, Mathematical Recreations(p37), Dover

Book discount problem
(Chlond's solution)
Source: J. & L. Poniachik, Hard-to-Solve Brainteasers (p16), Sterling

Seven 11 (Chlond's solution)
Source: alt.math.recreational

Posted by hakank at 07:09 FM Posted to Constraint Programming | Pyssel | Comments (0)

juni 29, 2008

Gruppteoretisk lösning av M12 puzzle i GAP

I Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc) presenterades det gruppteoretiska pysslet M12, då med en lösning i MiniZinc (modellen M12.mzn).

När jag läste om M12 tänkte jag att det skulle vara skoj med även en gruppteoretisk lösning eftersom det är ett gruppteoretiskt problem. En sådan lösning har nu gjorts med hjälp av det abstrakta algebraiska systemet GAP. Numera finns GAP även med i distributionen av det öppna matematiska (och mycket trevliga) systemet Sage.

Uppdatering
Efter lite funderande kom jag på en bättre lösning. I stället för att ändra en massa i denna text skrev jag en ny: Gruppteoretisk lösning av M12 puzzle i GAP - take 2, vilken se.


Kort beskrivning av M12
Som tidigare beskrivits går M12-pysslet ut på att man har en sekvens av 12 siffror i en härlig oordning och man ska med hjälp av två operationer återställa sekvensen till 1,2,3,4,5,6,7,8,9,10,11,12. Operationerna är:
Merge: [1, 12, 2, 11,3, 10, 4, 9, 5, 8, 6, 7] blir [1,2,3,4,5,6,7,8,9,10,11,12].
Inverse: Vänder listan om, [1,2,3,4,5,6,7,8,9,10,11,12] blir [12,11,10,9,8,7,6,5,4,3,2,1]. Not, jag kallar operationen (av historiska skäl) för Reverse här nedan.


GAP-program
Här är GAP-programmet (M12_gap.txt). Resultat från ett kommando eller kommentar skrivs efter "#".


Först definierar vi operatorerna, dvs generatorerna i gruppen. Här används PermList som tar en lista och skapar en permutationscykel.

#
# Solving the M12 for a specific sequence
#

#
# Define the operators
#

# Reverse (Inverse)
reverse := PermList([12,11,10,9,8,7,6,5,4,3,2,1]);
# (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)

# Merge
merge := PermList([1,12,2,11,3,10,4,9,5,8,6,7]);
# (2,12,7,4,11,6,10,8,9,5,3)

Skapa gruppen g och gör några tester.


# Create the group
g:=Group([reverse, merge]);
# Group([ (1,12)(2,11)(3,10)(4,9)(5,8)(6,7), (2,3,5,9,8,10,6,11,4,7,12) ])

# Which group is it?
StructureDescription(g);
# "M12"

Size(g);
# 95040

Bra, det är alltså gruppen M12, dvs Mathieu-grupp av ordningen 12. Notera att det finns ett inbyggt kommando för att skapa en Mathieugrupp (MathieuGroup), men den har inte de generatorer som vil ska använda, alltså rullar vi vår egen.


Nu börjar det roliga. Låt oss som exempel ta följande sekvens som nyss skapats av M12-programmet.


#
# Create the puzzle to solve
#
puzzle:=[4, 5, 11, 1, 9, 6, 3, 10, 2, 7, 12, 8];;


För att få reda på lösningen görs en "faktorisering", med hjälp av funktionen Factorization.


Factorization(g, PermList(puzzle)^-1);
# x1*x2^2*x1*x2^-5*x1*x2^-5

Här har vi en lösning som ska tolkas som operationer i pysslet:

x1*x2^2*x1*x2^-5*x1*x2^-5

x1 betyder den första generatorn (dvs Reverse/Inverse) och x2 är Merge.

Det finns två saker att tänka på här:
- man ska läsa sekvensen baklänges
- alla operationer med negativ exponent måste konverteras till en positiv exponent. Det görs med en enkel subtraktion: x2^-5 innebär samma sak som x2^(11-5) = x2^6

Om vi översätter enligt ovanstående två regler blir det:

x2^6 x1 x2^6 x1 x2^2 x1

Så, uttolkat i samma form som M12-applikationen blir lösningen följande. Tänk på att vi arbetar med lösningen bakifrån och att x1 är I och x2 är M:

M6 I M6 I M2 I

Detta är en lösning med 6+1+6+1+2+1 = 17 steg.


En variant

Förutom Factorization finns det en annan metod, och det är den som generellt rekommenderas för att göra denna typ av "faktoriseringar". Tyvärr tenderar den att generera längre lösningar än med Factorization.


#
# This is the recommended function for factorizations, but it gives longer
# solutions (strings) than Factorization.
#

#
# Create names to identify the operations
#
M:=g.2; R:=g.1;
hom:=EpimorphismFromFreeGroup(g:names:=["R","M"]);

#
# Now, solve the puzzle
#
PreImagesRepresentative(hom,PermList(puzzle)^-1);
# M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Lösningen är alltså:

M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2

Notera att R^-1 ska tolkas som en Inverse-operation.

Ovanstående motsvarar följande M12-operationer:

M2 I M10 I M8 I M3 I M I M4 I M8

Detta är en lösning på 2 + 1 + 10 + 1 + 8 + 1 + 3 + 1 + 1 + 1 + 4 + 1 + 8 = 42 steg, vilket är mycket längre än Factorization-approachen.


Man bör notera att dessa faktoriseringar är optimerade att få så små exponenter som möjligt oavsett om det är positiva eller negativa exponenter. Vi är dock endast intresserade av positiva exponenter och lider därför av denna optimering.

Om man adderar exponenterna utan tecken, ger Factorization i alla fall en enklare lösning.

Factorization: x1*x2^2*x1*x2^-5*x1*x2^-5 = 1 + 2 + 1+ 5 +1+ 5 = 15 steg.

PreImagesRepresentative: M^-3*R^-1*M^4*R^-1*M*R*M^3*R*M^-3*R*M^-1*R*M^2 = 3 + 1 + 4 + 1 + 1+ 3+ 1 + 3+ 1+ 1 + 1 + 2 = 22 steg.


Båda dessa faktoriseringar går mycket snabbt, typ någon sekund eller så.


Jämförelse med MiniZinc-lösningen
Jag testade att köra pysslet med MiniZinc-modellen M12.mzn. Den tar väldigt lång tid (typ 10-tals minuter) och ger följande lösning på 18 steg, dvs något sämre än Factorization-varianten. Operatorn 1 motsvarar Merge och operatorn 2 motsvarar Inverse.


2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 2

dvs operationerna: R M6 R M2 R M R M3 R M

Så här ser sekvensen ut för respektive operation. Siffran till vänster är operationen. Första raden är ursprungssekvensen och är endast med för presentationens skull.


0: 4 5 11 1 9 6 3 10 2 7 12 8
2: 8 12 7 2 10 3 6 9 1 11 5 4
1: 8 7 10 6 1 5 4 11 9 3 2 12
1: 8 10 1 4 9 2 12 3 11 5 6 7
1: 8 1 9 12 11 6 7 5 3 2 4 10
1: 8 9 11 7 3 4 10 2 5 6 12 1
1: 8 11 3 10 5 12 1 6 2 4 7 9
1: 8 3 5 1 2 7 9 4 6 12 10 11
2: 11 10 12 6 4 9 7 2 1 5 3 8
1: 11 12 4 7 1 3 8 5 2 9 6 10
1: 11 4 1 8 2 6 10 9 5 3 7 12
2: 12 7 3 5 9 10 6 2 8 1 4 11
1: 12 3 9 6 8 4 11 1 2 10 5 7
2: 7 5 10 2 1 11 4 8 6 9 3 12
1: 7 10 1 4 6 3 12 9 8 11 2 5
1: 7 1 6 12 8 2 5 11 9 3 4 10
1: 7 6 8 5 9 4 10 3 11 2 12 1
2: 1 12 2 11 3 10 4 9 5 8 6 7
1: 1 2 3 4 5 6 7 8 9 10 11 12 % Solution!

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

juni 24, 2008

MiniZinc-nyheter

Här är några nyheter om constraint programming-systemet MiniZinc.

* Det har kommit en ny version av MiniZinc: version 0.8.1, som i princip endast är buggfix jämfört med version 0.8.

* ECLiPSe stödjer nu version 0.8-formatet. Ladda ner den senaste utvecklingsversionen här. I skrivande stund är det version 5.10_135 som gäller.

* Eftersom ECLiPSe ny stödjer version 0.8-formatet, har jag som utlovats ändrat alla mina modeller till detta format. Se My MiniZinc Page. Ett fåtal modeller krånglade och finns därför kvar i gamla formatet.

* Skaparna av MiniZinc har startat en tävling MiniZinc Challenge 2008. Fördelen med detta är att det kan generera lite buzz, samt göra så att fler solvers utvecklas.

* En ny solver har tillkommit:: fzntini som bygger på SAT solvern Tinisat. För närvarande finns det endast en Linux-exekutabel av solvern, dvs ingen källkod.

Posted by hakank at 09:23 FM Posted to Constraint Programming | Comments (0)

Tre matematiska / logiska pyssel med constraint programming-lösningar: n-puzzle, SETS, M12 (i MiniZinc)

Här är några matematiska / logiska pyssel med lösningar i MiniZinc.

n-puzzle (8-puzzle, 15-puzzle)

n-puzzle (8-puzzle, 15-puzzle) är ett synnerligen standardpyssel som ofta används för att testa algoritmer och liknande inom AI eller för att träna hjärnan. Det går ut på att flytta en blank bricka runt i en matris så att siffrorna återställs till en given ordning (oftast 1..15 eller 1..8) och den blanka ska vara i den nedersta högra rutan .

Min lösning på detta problem finns i n_puzzle.mzn och får väl anses vara ett pseudo-härke eftersom det använder en del trixerier såsom dummy-drag (kring rad 111).

Här är exempel på 8-puzzle, dvs en matris med 3x3. Talet 9 representerar den blanka rutan som flyttas runt.

Definiera först utgångspositionen:

puzzle =
[|2,3,6,
|1,4,9,
|7,5,8|];

Resultatet är (med num_sols = 8, dvs antal olika drag):


puzzle:
2 3 6
1 4 9
7 5 8
...
0: 2 3 6 1 4 9 7 5 8
0: 2 3 9 1 4 6 7 5 8
0: 2 9 3 1 4 6 7 5 8
0: 9 2 3 1 4 6 7 5 8
0: 1 2 3 9 4 6 7 5 8
0: 1 2 3 4 9 6 7 5 8
0: 1 2 3 4 5 6 7 9 8
1: 1 2 3 4 5 6 7 8 9
moves:
0 6
6 3
3 2
2 1
1 4
4 5
5 8
8 9

Lösningen finns i andra kolumnen i moves, dvs

6 3 2 1 4 5 8 9

Där 6 betyder att blank (9) och brickan som finns i position 6 ska byta plats, 3 att 9 och brickan i position 3 ska byta plats etc.

Raderna med matrisen visar hur draget påverkar matrisen (som en vektor). Talet framför raden (0 eller 1) visar om lösningen är gjort (1) eller inte (0).


M12


M12 är ett pyssel inspirerat av spel såsom ovanstående 15-pyssel och Rubiks kub (och dess släktingar). Skaparna av M12, gor Kriz and Paul Siegel, beskrev det Scientific American-artikeln Rubik's Cube Inspired Puzzles Demonstrate Math's "Simple Groups" för någon vecka sedan:

What we wanted for educational purposes was an entertaining way to develop people’s intuitions for groups entirely unlike the ones represented by the cube. And what we wanted as puzzle fans was a new set of puzzles whose solutions require a substantially different strategy from that of Rubik’s Cube and its relatives. So we made the natural connection: we were able to develop three new puzzles based on groups known as sporadic simple groups, whose properties are both remarkable and not well known except to specialists. Happily, the experiences of our colleagues show that anyone who can learn to solve Rubik’s Cube can gain an equally substantial understanding of these sporadic simple groups by doing our puzzles. But more, these puzzles are challenging in the sense that they do not yield to the methods that work with Rubik’s Cube—and we think they are a lot of fun. Readers who want to get their hands on them right away can download them.

Kortfattad beskrivning av M12
Talen 1 till och med 12 används, och de blandas slumpmässigt (fast inte hur som helst). Själva pysslet går ut på att man ska få tillbaka ursprungspositionen 1..12 med hjälp av endast två operationer:
- invert: placera talen i omvänd ordning, dvs 1..12 blir 12..1.
- merge: detta är en variant av "perfekt blandning". Den beskrivs som is a "card shuffle" best understood by trying it out, och kan väl enklast förklaras med följande: Om konfigurationen är

a) 1 12 2 11 3 10 4 9 5 8 6 7

och man gör en merge blir resultatet


b) 1 2 3 4 5 6 7 8 9 10 11 12

dvs man får då lösningspositionen.

Lösning i MiniZinc
I M12.mzn finns en modell för att lösa M12, dvs det enklaste av de tre problemen. För mer avancerade problemkonfigurationer, säg antal operationer > 24, tar det rätt lång tid.

Exempel:
Här är ett enkelt problem:

init = [7,1,8,9,12,5,3,10,4,11,6,2]

Lösning:

init: [7, 1, 8, 9, 12, 5, 3, 10, 4, 11, 6, 2]
check: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
check_ix: 10
operations: [0, 1, 1, 1, 2, 1, 1, 1, 1, 2, 0, 0]
0: 7 1 8 9 12 5 3 10 4 11 6 2
1: 7 8 12 3 4 6 2 11 10 5 9 1
1: 7 12 4 2 10 9 1 5 11 6 3 8
1: 7 4 10 1 11 3 8 6 5 9 2 12
2: 12 2 9 5 6 8 3 11 1 10 4 7
1: 12 9 6 3 1 4 7 10 11 8 5 2
1: 12 6 1 7 11 5 2 8 10 4 3 9
1: 12 1 11 2 10 3 9 4 8 5 7 6
1: 12 11 10 9 8 7 6 5 4 3 2 1
2: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12
0: 1 2 3 4 5 6 7 8 9 10 11 12

Operationerna som används är kodade enligt:
0: gör inget (samma som föregående rad) . Not: Första raden är en dummy operation.
1: merge (M)
2: inverse (I)

Lösningen här är alltså: MMMIMMMMI .
Tyvärr klarar MiniZinc inte av att presentera strängar därav de numeriska värdena.

Tips: Antalet rader i lösningen (rows) påverkar väldigt mycket hur lång tid det tar. Börja därför med ett lägre värde (t.ex. 12) och öka detta försiktigt.

Not: Modellen är till strukturen rätt lik modellen för n-pysslet (se ovan) och det är ingen slump. (Jag skrev dock M12.mzn före n_puzzle.mzn)


Mer info om M12
* För att spela M12 (och dess storebröder) online kan man gå hit.
* Spelen finns även att tillgå som Windows-program från en av författarnas hemsida Igor Kriz. Se README för mer info.
* God Plays Dice skrev lite om detta i Rubik's deck of cards?.
* Wikipedia om den gruppteoretiska bakgrunden: Sporadic group.


SET puzzle


Tommy på Användbart skrev om dessa problem för några dagar sedan. Problemet påminner om vissa typer av IQ-test där man ska lista ut vilka saker som hör ihop med andra, och tycker man sådana problem är intressanta är SET värt att bita i.

När Tommy berättade om detta på senaste bloggträffen var en av mina första reaktioner att börja med att skapa en modell för problemet. Vilket sålunda har gjorts.

Läs mer om SET, med regler, tips etc:
* Wikipedia Set_(game), som väldigt korfattat beskriver problemet så här


Different "categories":
* They all have the same number , or they have three different numbers.
* They all have the same symbol , or they have three different symbols.
* They all have the same shading, or they have three different shadings.
* They all have the same color , or they have three different colors.

* New York Times har ett pyssel varje dag, och här förklaras lite mer.
* Ett lärt paper om SET: Benjamin Lent Davis and Diane Maclagan, The Card Game Set (PDF).


Huvuddelen av MiniZinc-modellen visas här med kommentarer. Den fullständiga modellen finns i set_puzzle.mzn.

include "globals.mzn";

int: n = 9; % number of items
% int: n = 12; % number of items
int: num_sets = 4; % number of Sets to find
% int: num_sets = 5; % number of Sets to find
int: m = 3; % number of items in a Set
int: num_flavours = 3; % number of flavours of the attributes
int: num_attributes = 4; % number of different attributes in each item
array[1..n, 1..num_attributes] of var 1..num_flavours: puzzle;

% decision variable: the sets to find
array[1..num_sets] of var set of 1..n: x;

% solve satisfy;
solve :: set_search(x, "input_order", "indomain_min", "complete") satisfy;

constraint

% exact three items in each set
forall(i in 1..num_sets) (
card(x[i]) = m
)
/\ % must be different sets
all_different(x)
/\
forall(i in 1..num_sets) (

% identify the items in this set
forall(a in 1..num_attributes) (
let {
array[1..m] of var 1..n: arr
}
in
% assign the set
forall(j in 1..m) (
arr[j] in x[i]
)
/\ % symmetry breaking: all different and sorted
forall(j in 1..m-1) (
arr[j] < arr[j+1]
)
/\
(
% EITHER all are same with regard to this attribute
forall(j in 1..m-1) (
puzzle[arr[j],a] = puzzle[arr[j+1],a]
)
\/
% OR all are different with regard to this attribute
forall(i, j in 1..m where i != j) (
puzzle[arr[i],a] != puzzle[arr[j],a]
)
)
) % end forall 1..num_attributes

) % end forall 1..num_sets

% /\ % Symmetry breaking: order the sets
% % Only works for flatzinc version >= 0.8
% increasing(x)
;

output [
show(x)
]

Idealet vore naturligtvis att man kunde förevisa bilden för programmet och sedan löstes problemet, men så långt har jag inte kommit. Istället används en enkel kodning från bilden med de ingående rutornas attribut till en matris av tal. Den kodning som används är följande, dvs det tal som visas inom parentes.


Symbols: Each card has ovals (1), squiggles (2), or diamonds (3) on it;
Color : The symbols are red (1), green (2), or purple (3);
Number : Each card has one (1), two (2), or three (3) symbols on it;
Shading: The symbols are solid (1), striped (2), or open (3).

Det problem som Tommy visar hos sig kodas så här:


puzzle =
array2d(1..n, 1..num_attributes,
[2,1,2,1,
3,3,2,1,
1,2,2,2,
1,2,2,1,
3,2,2,1,
3,1,2,1,
3,2,2,2,
2,3,2,2,
1,2,2,3,
]);

Det finns en unik lösning till detta problem (modulo symmetrier), nämligen dessa fyra mängder

{1, 2, 4}
{2, 5 6}
{3, 4, 9}
{6, 8, 9}

Posted by hakank at 09:07 FM Posted to Constraint Programming | Pyssel | Comments (0)

juni 05, 2008

Mats Anderssons tävling kring fotbolls-EM 2008 - ett MiniZinc-genererat tips

Mats Andersson har tidigare haft flera roliga tävlingar. Inför fotbolls-VM 2006 var det en tävling där man skulle gissa resultat i matcherna.

Eftersom mitt kunnande om fotboll var synnerligen begränsat valde jag en enkel metod genom att skapa ett beslutsträd för hur resultaten skulle bli. Och kom naturligtvis sist.

Inför fotbolls-EM (som alltså startar på lördag) har Mats en ny tävling, och den vill man ju inte missa.

Constraint programming-modell i MiniZinc

Eftersom kunnandet kring fotboll fortfarande är (ännu mer synnerligen) begränsat kan det inte vara frågan om att göra några bedömningar kring hur matchresultaten kommer att bli.

Denna gång tänkte jag istället parasitera på Mats fantastiska fotbollskunnande och utnyttja det tips han själv gjort. För detta har skapats en modell i constraint programming-systemet MiniZinc. Modellen finns här och visas även nedan.

Modellen bygger på Mats tips med följande villkor.

Möjligen är några av villkoren lite väl begränsande men har fördelen att det inte blir så många lösningar (om man t.ex. skulle göra någon form av okulärbedömning av dem, vilket inte gjorts här, så det spelar egentligen inte någon roll hur många lösningar som genereras)

1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips.
Kommentar: Om Mats anser att ett lag vinner så gör jag det också. Mats borde veta sådant.

2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
som för Mats tips.
Kommentar: Detta är för att få ner antalet möjliga lösningar.

3) Inga resultat får vara exakt samma som Mats.
Kommentar: Egentligen borde man tillåta att några resultat är samma som Mats, men det blir roligare så här.

4) Det får vara maximalt 5 mål per match.
Kommentar: Kanske det skulle vara maximalt 6 mål, eller 7?


Det finns 29 olika lösningar till detta problem. Redan innan jag tittade på resultaten beslöt jag mig för att ta den sista lösningen som solvern Gecode fz (version 1.2.1) genererade.

Mitt tips

Här är alltså mitt tips till fotbolls-EM 2008.

1. Schweiz - Tjeckien 2-2
2. Portugal - Turkiet 1-0
3. Österrike - Kroatien 0-1
4. Tyskland - Polen 1-2
5. Rumänien - Frankrike 1-3
6. Holland - Italien 1-2
7. Spanien - Ryssland 1-0
8. Grekland - Sverige 1-1
9. Tjeckien - Portugal 1-3
10. Schweiz - Turkiet 1-1
11. Kroatien - Tyskland 0-0
12. Österrike - Polen 1-3
13. Italien - Rumänien 2-0
14. Holland - Frankrike 0-1
15. Schweiz - Portugal 0-1
16. Turkiet - Tjeckien 1-1
17. Sverige - Spanien 1-3
18. Grekland - Ryssland 1-3
19. Österrike - Tyskland 0-3
20. Polen - Kroatien 0-1
21. Holland - Rumänien 1-0
22. Frankrike - Italien 1-3
23. Grekland - Spanien 1-4
24. Ryssland - Sverige 0-1


MiniZinc-modellen


Här nedan visas MiniZinc-modellen för problemet. (webb-versionen kan ha några små skillnader.)


%
% MiniZinc-modell för Mats Anderssons tävling om resultatet i fotbolls-EM 2008.
%
% För beskrivning av tävlingen se:
% http://www.mats-andersson.se/blogg/show.asp?svarsID=1956
%
%
% Min variant bygger på Mats tips med följande villkor:
%
% 1) Skillnaden i mål mellan lag 1 och lag 2 ska vara samma som Mats tips
% (om Mats anser att ett lag vinner så gör jag det också. Mats borde veta
% sådant).
% 2) Totalt antal mål gjorda i alla matcher i mitt tips ska vara samma antal
% som för Mats tips
% 3) Inga resultat får vara exakt samma som Mats.
% 4) Det får vara maximalt 5 mål per match.
%
% Med dessa begränsningar finns det 29 olika lösningar.
% Det beslöts innan lösningarna studerats att ta den sista lösningen
% som solvern Gecode fz (version 1.2.1) genererade.
%

%
% Model created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc
%

int: n = 24; % antal fotbollsmatcher
array[1..n, 1..2] of 0..4: m; % Mats tips
array[1..n, 1..2] of var 0..4: h; % mitt tips

int: m_sum = sum(i in 1..n) (m[i,1] + m[i,2]); % totalt antal mål i Mats tips
var int: h_sum; % total antalet mål i mitt tips

solve satisfy;

constraint
forall(i in 1..n) (
% förhållandet i mål mellan lagen ska vara samma som Mats tips
m[i,1] - m[i,2] = h[i,1] - h[i,2]

/\ % max 5 mål per match
h[i,1] + h[i,2] <= 5
)
/\ % inga matcher får ha exakt samma resultat som Mats
sum(i in 1..n) (
bool2int(
m[i,1] = h[i,1] /\ m[i,2] = h[i,2]
)
) = 0

/\ % totalt antal mål i mitt tips
h_sum = sum(i in 1..n) (
h[i,1] + h[i,2]
)
/\ % totalt antal mål ska vara samma i Mats och mitt tips
h_sum = m_sum
;

output
[
if j = 1 then "\n" ++ show(i) ++ ": " else " " endif ++
show(h[i,j])
| i in 1..n, j in 1..2
];


%
% Mats tips
%
m = [
1,1, % 1. Schweiz - Tjeckien 1-1
2,1, % 2. Portugal - Turkiet 2-1
1,2, % 3. Österrike - Kroatien 1-2
0,1, % 4. Tyskland - Polen 0-1
0,2, % 5. Rumänien - Frankrike 0-2
0,1, % 6. Holland - Italien 0-1
2,1, % 7. Spanien - Ryssland 2-1
0,0, % 8. Grekland - Sverige 0-0
0,2, % 9. Tjeckien - Portugal 0-2
0,0, % 10. Schweiz - Turkiet 0-0
2,2, % 11. Kroatien - Tyskland 2-2
0,2, % 12. Österrike - Polen 0-2
3,1, % 13. Italien - Rumänien 3-1
1,2, % 14. Holland - Frankrike 1-2
1,2, % 15. Schweiz - Portugal 1-2
0,0, % 16. Turkiet - Tjeckien 0-0
0,2, % 17. Sverige - Spanien 0-2
0,2, % 18. Grekland - Ryssland 0-2
1,4, % 19. Österrike - Tyskland 1-4
2,3, % 20. Polen - Kroatien 2-3
2,1, % 21. Holland - Rumänien 2-1
0,2, % 22. Frankrike - Italien 0-2
0,3, % 23. Grekland - Spanien 0-3
1,2 % 24. Ryssland - Sverige 1-2
];

%
% End of MiniZinc model.
%


Notera att MiniZinc inte hanterar strängar speciellt bra så resultatet presenteras endast så här:


1: 2 2
2: 1 0
3: 0 1
4: 1 2
5: 1 3
6: 1 2
7: 1 0
8: 1 1
9: 1 3
10: 1 1
11: 0 0
12: 1 3
13: 2 0
14: 0 1
15: 0 1
16: 1 1
17: 1 3
18: 1 3
19: 0 3
20: 0 1
21: 1 0
22: 1 3
23: 1 4
24: 0 1


Slutord


Från början tänkte jag använda någon form av statistisk metod som analyserade Mats tips för att skapa mitt eget tips. Ovanstående angreppssätt ligger definitivt mer i linje med det jag håller på med nu.

Naturligtvis ska man se allt detta som en liten etyd i constraint programming.

Posted by hakank at 09:18 EM Posted to Constraint Programming | Pyssel | Comments (0)

juni 02, 2008

Nya MiniZinc-modeller, flera global constraints, däribland clique

Sedan anteckningen Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem i förra veckan har några fler modeller skapats. Samtliga modeller finns att ladda ner från My MiniZinc page.

Denna gång är det förvisso några pyssel men fokus har varit att implementera global constraints från den fantastiska samligen Global Constraints Catalogue.

Pyssel

Samtliga desa pyssel är från de kommenterade exemplen i det första kapitlet från boken Problem Solving Through Recreational Mathematics av Bonnie Averbach och Orin Chein (ISBN: 9780486409177).

Av enkelhet är filerna döpta efter exemplets namngivning. Den specifika problemformuleringen finns i mzn-filen.
- Exempel 1.2. Enkelt problem om tre damer som sitter vid ett bridgebord och byter kort. Det gäller att avgöra hur de sitter.
- Exempel 1.3. Här ska man avgöra namnet på hustrur och hästar till 5 olika män.
- Exempel 1.4. Svårare variant av 1.2. Fem män med olika yrken spelar poker. Här gäller det att avgöra yrke och position vid bordet.
- Exempel 1.5. Nim, ganska generell. Problemet är att avgöra vilken strategi som garanterar vinst, men här visas endast alla giltiga drag (man får alltså dra egna slutsatser om strategier).

Global constraints etc

Så har det skapats några global constraint som finns i Global Constraints Catalogue eller sådana som är lite mer generella. Samtliga modeller innehåller ett enkelt exempel, för det mesta är det exemplet som finns i katalogen.


clique
Jag börjar med clique eftersom det är en av mina favorit-constraints, och att det tog en stund att får det rätt.

Modell och exempel finns i clique.mzn. Se även Global constraint-entry.

clique är ett begrepp från grafteorin som innebär att samtliga noder inom denna klick är kopplade till varandra. (Det är ungefär det vi menar med det vardagliga "klick" för att beskriva en social struktur, ett gäng, ett kotteri, etc.)

Ibland är problemet att hitta den största klicken i en graf, men ibland räcker det bara med en klick, vilken som helst av en viss storlek.

Exempel på clique
Låt oss leka lite med exemplet från GC-katalogen. Det är 5 noder som har följande kopplingar:

1 är kopplad till 2,4
2 är kopplad till 1,3,5
3 är kopplad till 2,5
4 är kopplad till 1,5
5 är kopplad till 2,3,4

Modellen arbetar med en matrisrepresentation av grafen, och visas i koden nedan.

Här är hela modellen.


include "globals.mzn"
int: num_nodes;
array[1..num_nodes, 1..num_nodes] of 0..1: g; % the graph (as a matrix)

var set of 1..num_nodes: s; % the clique
var int: c = card(s); % size of the clique

%
% clique(clique size, the clique, the graph)
%
% Note: I have added the clique in the parameters list.
%
predicate clique(var int: c, var set of int: s, array[int, int] of int: g) =
let {
int: n = card(index_set_1of2(g)),
array[1..n] of var bool: s_bool
}
in
link_set_to_booleans(s, s_bool)
/\
forall(i,j in 1..n where i != j) (
(s_bool[i] /\ s_bool[j]) -> ( g[i,j] > 0)
)
/\
c = card(s)
;

solve maximize c;

constraint
% s = {1,2,3} /\ % Exempel 1
clique(c, s, g)

% /\ % Example 2
% c >= 2
;

%
% data
%
num_nodes = 5;
g = [
% 1 2 3 4 5
1,1,0,1,0, % 1
1,1,1,0,1, % 2
0,1,1,0,1, % 3
1,0,0,1,1, % 4
0,1,1,1,1, % 5
];

Exempel på några problem med clique

Med constrainten clique kan man nu lösa bl.a. följande problem:

1. Är {1,2,3} en klick i denna graf?

solve satisfy;

constraint
s = {1,2,3}
/\
clique(c, s, g)
;

Svaret är: "No solution". Det är alltså ingen clique.


2. Visa samtliga klickar som är större än 2.
Det görs med denna constraint-sektion:


clique(c, s, g)
/\
c >= 2

dvs här har vi inte fixerat s (själva klicken). En massa lösningar skrivs nu ut.


3. Vilken är den största klicken och hur stor är den?
Här används solve maximize eftersom vi är ute efter den största av något (nämligen klickens storlek, c). För att effektivisera sökningen kan man begränsa till att undersöka klickar av storlek 2 eller större.


solve maximize c;
% ...
constraint
clique(c, s, g)
/\
c >= 2
;

Svar: Den största klicken är {2,3,5} och den är över 3 noder.
Not: Med solve maximize får man endast en lösning. Det är möjligt att det finns andra cliques som är lika stora. Då måste man ändra modellen till:

solve satisfy;
% ...
constraint
clique(c, s, g)
/\
c >= 3
;

I denna graf finns dock ingen annan clique med tre eller flera noder än {2,3,5}.


Noteras kan att det i modellen även finns en slumpgenererad graf på 100 noder. I den grafen finns 3515 olika klickar >= 3 (dock inklusive "subklickar"). Det finns fyra klickar av storlek 6. Det sistnämnda problemet tar cirka 5 sekunder att lista ut.

Övriga global constraints

Här är listingen av några andra global constraints. Beskrivning och länk till global constraints-katalogen finns i modellen.

* all_differ_from_at_least_k_pos

* all_min_dist

* alldifferent_cst

* alldifferent_except_0

* alldifferent_modulo

* alldifferent_on_intersection

* alldifferent_partition

* alldifferent_same_value

* alldifferent_soft
Modellen implementerar två varianter:
- soft_all_different_ctr
- soft_alldifferent_var

* change

* circular_change

* common
Modellen implementerar:
- common
- used_by

* count_ctr
Notera att MiniZinc har en count constraint i globals.mzn, men den är inte så generell som katalogens. Min modell är mer generell.

* distance_between

* inflexions

* k_alldifferent

* longest_change

* nchange

* period

* sum_ctr

Och så några generella constraints som inte finns i GC-katalogen:

* runs: Antalet runs i en vektor. En run är ett segment av en vektor som består av samma värde.

* fix_points: Antalet fixpoints i en vektor, dvs antalet positioner där värdet är samma som dess position.

Matris-operationer

Modellen transpose innehåller några matrisoperationer: - transpose - scalar_add - scalar_mult

Det var dessa matrisoperationer som jag behövde för tillfället.

En trevlig sak med constraint-programming är - som vi sett ovan och som jag skrivit om tidigare - att man "vända på" ett problem. I transpose-modellen finns en 4x4-matris (x) som man gör en transpose på (roterar 90 grader), varpå man gör en skalär addition på dessa två matriser (originalmatrisen + den transponerade).

Låt x vara originalmatrisen, t vara den transposerade matrisen och slutligen p vara resultatet av p = x + t (skalär addition av x och p).

Då kan vi lösa några olika problem.

1. Givet x, räkna ut p
Detta är det normala problemet: Räkna ut p om vi har x (och därmed t).


int: n;
array[1..n, 1..n] of var 1..10: x;
array[1..n, 1..n] of var 1..10: t;
array[1..n, 1..n] of var int: p;

solve satisfy;

%
% definition av transpose och scalar_add
% ....

constraint
x = [1,1,1,1,
2,2,2,2,
3,3,3,3,
4,4,4,4]
/\
transpose(x,t)
/\
scalar_add(x,t,p)
;

Här räknas både t och p ut med ledning av de värden som vi givit x.


2. Givet p, räkna ut x och t
Det är nu det börjar bli skoj!

Vi låter nu x och t vara variabler (dvs deklarerar dem inte) och fixerar endast p (resultatet av x + t). Hur många olika lösningar x + t = p med en fix matrix p finns det?


% ....

constraint
transpose(x,t)
/\
scalar_add(x,t,p)
/\
p =
[2, 3, 4, 5,
3, 4, 5, 6,
4, 5, 6, 7,
5, 6, 7, 8]

Svar: Det finns 2880 lösningar.


Slutord (för dagens skörd)


Global Constraint Catalogue innehåller för närvarande över 300 global constraints och jag har bara implementerat en bråkdel av dem. Flera kommer med stor sannolikhet att modelleras, i alla fall sådana som verkar nyttiga/skoj och går att göra i MiniZinc. Det finns några mer avancerade grafteoretiska constraints som är svåra att implementera i MiniZinc, som saknar rekursioner och dynamiskt växande listor.


Posted by hakank at 08:02 EM Posted to Constraint Programming | Comments (0)

MiniZinc/FlatZinc version 0.8 släppt

Häromdagen släpptes en ny version av MiniZinc (se även My MiniZinc page), det constraint programming-system som jag håller på med just nu.

Den nya versionen finns här.

Förändringar
I NEWS beskrivs alla de förändringar som gjorts sedan version 0.71.

Notera att detta endast gäller MiniZinc/FlatZinc. Ändringarna är ännu (2008-06-02) inte införda för de andra solvers, dvs Gecode fz respektive ECLiPSe's ic, fd eller eplex. Jag väntar med spänning på detta.


De praktiskt viktigaste ändringarna är:

* ny deklaration av vektorer
vektorer (arrays) i högre dimensioner konverteras inte längre automatiskt till en "multi-array". Man måste deklarera dimensionen explicit.

Exempel: För att deklarera en 2-dimensionell vektor (dvs en matris) gjorde man tidigare så här:

int: n;
array[1..n, 1..n] of int: x;
% en massa andra saker
% ...
n = 3;
% deklarationen (gamla sättet)
x =
[1,2,3,
4,5,6,
7,8,9];
% ....

Nu måste man istället skriva deklarationen så här:

% ...
x =
[|1,2,3,
|4,5,6,
|7,8,9|]

Dvs man måste omsluta varje rad med ett "|"-tecken. Notera att "parenteserna" inte får delas upp utan man måste skriva "[|" respektive "|]". Gör man inte så blir det ett kryptiskt fel.


* FlatZinc har flera solvers
För FlatZinc (den solver som kommer med MiniZinc-distributionen) är default solver fd, en finite domain-solver och det var den endast som fanns tillgänglig i version 0.7.1.

Följande solvers finns nu att tillgå i FlatZinc. Från kommandot flatzinc --help:

Solver Selection Options:
-s , --solver , --solver-backend
Select the solver(s) and evaluation algorithm that should be used.
Valid solver backends are: `fd', `sat', `mip', `fdmip', `colgen',
`skp' and `ttt'. (The default is `fd'.)

--mip-solver
Use the specified solver as the default MIP solver.
Supported MIP solvers are: osi-cbc.

--sat-solver
Use the specified solver as the default SAT solver.
Supported SAT solvers are: minisat.

--colgen-mip-solver
Use the specified solver as the default MIP solver for the column
generation backend. (Note that this choice will be overridden by
a `colgen_master_solver' annotation in the model.)
Supported column generation MIP solvers are: osi-cbc.

--colgen-approx-solver
Use the specified approximate linear solver with the column
generation backend. (Note that this choice will be overridden by
a different choice inside a `colgen_master_solver' annotation in
the model.)
Supported approximate linear solvers are: osi-volume.

Speciellt intressanta är fd, mip (mixed integer programming, använder Coin:s osi-cbc) och fdmip (en hybrid mellan dessa).

Det antyds att allt utom fd och möjligen mip/fdmip bör anses som odokumenterade features.

Tyvärr generar flatzinc-programmet endast en lösning. Hoppas att man ändrar detta i en senare version så att alla lösningar visas (som Gecode fz och ECLiPSe's ic/fd gör).


* show_cond
När man skriver ut resultaten, med show(variabel) inom output, har man endast kunnat för if-satser på fixa variabler (dvs par-deklarerade variabler), vilket har begränsat uttryckfullheten ordentligt.

I version 0.8 finns det möjlighet att med show_cond göra en dynamisk kontroll av icke-fixa variabler. Exempel: Här skriver vi endast ut de värden som tillsammans blir 14, dvs de som har värdet 1 i x-vektorn. MiniZinc/FlatZinc skriver ut 2 3 4 5.

int: n = 10;
array[1..n] of var 0..1: x;

solve satisfy;
constraint sum(i in 1..n) (x[i]*i) = 14;

output [
show_cond(x[i] > 0, i, "") ++ " "
| i in 1..n
];


* vektorer är 1-baserade
I äldre versionen var alla vektorer 0-baserade (dvs första element räknades från 0). Nu börjar man på 1 istället. Normalt behöver man inte bry sig om, detta förutom då man arbetar med "slices" som skickas till ett predikat.


Mina exempel
Mina MiniZinc-modeller på My MiniZinc page är fortfarande i gamla 0.7.1-formatet, och jag kommer att vänta med att konvertera dem till version 0.8 tills åtminstone en av de två andra solvers (Gecode fz respektive ECLiPSe's varianter) stöder denna version. Då är det förmodligen endast vektor-deklarationerna som kommer att ändras (men kanske en och annan show_cond läggs till).


Wrapper
För övrigt har jag skapat en flexibel Perl-wrapper kring de olika solvers. Det har stöd för både 0.7.1 och den nya 0.8. Och man kan från kommandoraden t.ex. ändra parametrar, lägga till constraints, ändra antal lösningar som ska visas etc.

Jag har ännu inte några planer att lägga upp detta program publikt, men maila mig gärna om du är intresserad av det. Som en teaser visas två exempel som faktiskt inte är helt ovanliga:

mzx.pl model.mzn --solver minizinc --new --option "--solver fdmip" --param "n=10;k=3"

mzx.pl model.mzn --solver ic --param "n=100;k=12" --num_solutions 10

Det första exemplet kör den nya versionen av MiniZinc (oftast SVN-versionen) med solvern fdmip, och ändrar parametern n till 10 samt parametern k till 3. Det andra exemplet kör ECLiPSe's ic-solver med andra parametrar samt visar endast de 10 första lösningarna.


Posted by hakank at 06:10 EM Posted to Constraint Programming | Comments (0)

maj 26, 2008

Några fler MiniZinc-modeller, t.ex. Smullyans Knights and Knaves-problem

Här är några MiniZinc-modeller som skapats sedan förra anteckningen om sådana modeller.

Samtliga modeller att tilnå finns via My MiniZinc page.

Digital Tomography samt några varianter
Det problem som skrevs om i Ett litet april-pyssel löste jag själv med en digital tomografi-teknik. Se modellen tomography.mzn.

En viss förklaring av digital tomografi finns på sidan Open problems in discrete tomography. Sidan innehåller några Java-applets som man själv kan leka med.

I ovanstående modell var det bara en färg ("svart") man arbetade med, men problem kan generaliseras till flera färger. En sådan generalisering görs i tomography_n_colors.mzn, och som exempel modelleras bl.a. "The two atom problem".

Solitaire Battleship (wikipedia) är en variant av "Sänka skepp" som har liknande förutsättningar som digital tomografi. MiniZinmodell: solitaire_battleships.mzn.


SONET problem
SONET-problemet är ett standardproblem inom constraint programming som jag inte hittat någon MiniZinc-modell av så därför rullade jag en egen: sonet_problem.mzn.

För mer om problemet se t.ex. Simplified SONET Problem (Postscript-fil).


A Coin Puzzle
Detta problem på en rätt stor "grid" beskrivs utförligt av Tony Hürlimann i A coin puzzle - SVOR-contest 2007 (PDF).

Min MiniZinc-implementation av problemet finns i coins_grid.mzn. Ett tips är att låta en linear programming-solver lösa problmet, dvs ECLiPSe:s eplex eller MiniZincs nya option "--solver mip". Då löses det blixsnabbt.