Learning constraint programming (languages) - part I
This part is a description of the problems I tend to start modeling in a new constraint programming system.
The first model to run is probably SEND+MORE=MONEY or n-queens, since either one of them are distributed in the package. This is to make sure that the system works, environment variables are correct, compilation works, how is the constraints and search strategies stated in the system, what to expect in terms of output, etc.
If either SEND+MORE=MONEY or n-queens is not in the distribution (which would be a surprise), I start with that model.
The models below are all the first problems I start with, sorted in the way they usually are implemented. Also there is a a short explanation what is learned about the system. After all these models are done, or a larger part of them, I publish them at a My [CP System] Page..
The list is very personal and may not be suited for everybody (if anyone, except me). One reason is that my goal has been to learn about modeling problems using constraint programming, and not so much about implementing propagators etc (and that is why I tend use decompositions a lot). However, lately I have somewhat shifted the focus to more gory details.
Also, I think it is important that when learning new stuff (especially by oneself) is to use examples that are well known, fun, and perhaps even with a personal history. Some examples of this "personal attachment" of a problem:
- The Least Diff problem was a problem in a company competition 1998 and was actually one of my inspiration to start learning constraint programming. The first version was programmed in a Prolog system, SICStus Prolog.
- Seseman problem: this was a problem stated by a fellow blogger in 2005, and I blogged about (in swedish) in Sesemans matematiska klosterproblem samt lite Constraint Logic Programming).
- de Bruijn sequences is a personal favorite problem since long time.
- MiniZinc (feb 2008)
- Choco (first "touch" in 2006, and then more in september 2008)
- JaCoP (august 2008)
- Gecode/R (january 2009)
- Comet (local search module 2007, constraint programming module: january 2009)
- Gecode (march 2009)
- SEND+MORE=MONEY or n-queens
* learning how to handle the CP system. See above.
- Least Diff
* minimize the difference ABCDE - FGHIJ (digits all distinct)
* this was actually my first "real" (i.e. non-standard) constraint programming problem
* how to optimize (here minimize) a solution
* simple OR problem
* how to interact with integer arrays and variable arrays
* one of my earliest constraint programming (modeled in ECLiPSe)
* generating one or all solutions
* handling of matrices
- Coins grid
* Tony Hubermann's grid puzzle, minimize distances in the grid
* how does a CP system handle this MIP problem (mostly quite bad compared to MIP)
- de Bruijn sequence
* a personal favorite
* see how large problem an implementation can handle
* command line options to the model
JaCoP: DeBruijnIterate.java (alternative version generating arbitrary number of solutions)
* how to implement a (decomposition of a) global constraint
* logical operators on variables: implication (if then), &&, !=
- Furniture Moving
* scheduling, the cumulative constraint
* not in all systems (Gecode and Gecode/R)
* more advanced example (quite simple to implement, though)
* reading problems from a file or handling different problems in some other way
Gecode: N/A (No Gecode model since there is one in the Gecode distribution)
- Quasigroup Completion
* yet another grid puzzle/problem
* alldifferent on rows/columns * handling matrices
* handling of different problems (file or some other way)
- Survo puzzle
* yet another grid puzzle
* handling of different problems (file etc)
- Young Tableaux and partitions
* combinatorial problem, easy to state and sometimes tricky to model
- Send Most Money in any base
* learning how to get parameters to the program (command line)
* in some versions: first optimize, then generating all solutions
- simple map coloring
* using graph/matrix
* fun problem
* testing different search strategies
* using "real" regular expressions (Gecode/R)
* using global constraint regular (MiniZinc/Comet)
* simple problem (easy to understand)
* knapsack / set covering
* very simple crossword example
* using strings/chars (instead of ints)
* a study in non-trivial Element constraint (array/matrix access)
- Word square
* continue from Crosswords
* a study in another non-trivial Element (actually simpler than for Crosswords)
* how to read a file (the word list)
- Who killed Agatha?
* logical problem
* Element constraint