" /> My Constraint Programming Blog: January 2009 Archives

« December 2008 | Main | February 2009 »

January 31, 2009

Some Comet constraint programming (CP) models

Earlier this week, I wrote about Comet in Comet version 1.1. For more about Comet, see the link mentioned above and newly created My Comet Page.

A year ago, when I first tested Comet, it was with the constraint-based local search module (LocalSolver, LS), but now I've modelled some of my standard problems in Comet's "classic" constraint programming module (CP). I hopefully will write more about local search modelling in Comet later.

Notes about constraint modelling in Comet

I really like working with Comet's constraint programming module (cotfd, finite domain). The comments below (and the models) should be read in the light that this is the first modelling using this CP module. There probably are other/better ways to do things.

My main experience with modelling in constraint programming is in MiniZinc so I use that system as a comparison.

The Comet models below were mostly translated from the MiniZinc models, and it was quite easy to do this translation, with some exceptions, e.g. the declaration of variables.

Comet has some features that I have really missed in MiniZinc:
- command line arguments and I/O. See minesweeper.co for an example.

- seamless conversion of floats and integers, and between integers and booleans.

- recursion. Well, I haven't have to use recursion in Comet yet, but it's nice to know it works.

- generating and colleting all solutions. Using exploreall all solutions to a problem may be obtained with in the model. In some of the MiniZinc solvers (Gecode and ECLiPSe) all solutions can be generated, but not collected in the model. Also, in Comet it is easy to modelling a problem with different input values (see send_more_money_any_base.co for an example).

- writing search heuristics. Search heuristics can be a real time saver. Comet supports writing your own labelling functions. I have not used this feature very much, but experimented with it in some models, e.g. langford.co (Langford's number problem). For my models, the built in labeling functions label or labelFF (first-fail) seems to be enough. The examples in the distribution use more advanced labeling techniques.

Comet is a big system, with many more features than those used in my first models, e.g. the local search, writing user defined constraints, tuples, classes etc etc.

In summary:
I have not found any great differences in speed, propagations etc between MiniZinc (and its solvers) and Comet, but these problems are not especially demanding, and I didn't the models. This would be a future work.

Comet is a great system and fun to use. I've now started to reread the book Constraint-Based Local Search by Pascal van av Hentenryck and Laurent Michel, about the constraint-based local search (LS module) in Comet, which has features that solve very large problems.

Code example

In Comet 1.1 two Comet models were shown. Here is some small examples of coding in Comet. Since I like recreational mathematics, let's convert between an array of numbers and an integer.

function void toNum(Solver m, var{int}[] x, var{int} num, int base) {
  m.post(num == sum(i in 1..x.getSize()) base^(x.getSize()-i)*x[i]);

It is then used in the model using the Solver as argument like this, where we also constrain the integer variable z to 123. The output of x will - of course - be [0,0,1,2,3]

Solver m();
var{int} x[i in 1..5](m, Digits);
var{int} z(m, 0..100000);
exploreall {
toNum(m, x, z, base);
m.post(z == 123);
} using {
cout << x << endl;

This whole test model is toNum.co.

Here are two other function, alldifferent_except_0 , and increasing (enure that an array is sorted). Both are used in the model alldifferent_except_0.co.

function void alldifferent_except_0(Solver m, var{int}[] x) {
int n = x.getSize();
forall(i in 1..n, j in i+1..n) { m.post(x[i] > 0 && x[j] > 0 => x[i] != x[j]); }

function void increasing(Solver m, var{int}[] x) {
  forall(i in 2..x.getSize()) m.post(x[i-1] <= x[i]);

My Comet models

Below are some of my Comet models for (classic) constraint programming. Explanation of the problem, and references are in each specific file.

For all model, with one exception, the constraint programming module (CP) was used. The Coin grid, however, uses the mixed integer programming (MIP in the LP module). I first did a constraint programming variant but it was too slow (as where all the classic constraint programming models I've written in MiniZinc, Gecode/R etc). Integer programming really shines there.

So, here's the models.

Most of these models were translated from my models in other constraint programming systems, which see:

January 25, 2009

Comet version 1.1

The other day the constraint-based local search system Comet version 1.1 was released.

The release contains the following new features (mailed to the mailing list, and slightly edited):

Dynadec is proud to announce Comet Release 1.1. New features in thi rrelease include:
* Addition of a priority to user-defined constraints.
* Addition of the function sqrt for the local solver.
* Addition of the method "tryPost" on the CP solver for postin constraints in user-defined constraints.
* Addition of the total number of failures (i.e., across restarts).
* Addition of a method startWithRestart to start LNS with a restart which may generate an initial solution.
* Function minAssignment now includes an alldifferent and a computation of the cost
* Added the ability to select from a set of strings
* Added a onFailure clause to select to handle elegantly the case where no value is selected
* Text based debugger on all platforms. (-gtext)
* GUI for debugger on OSX and Linux (-ggui) [experimental]
* C++ API: with good packaging

We encourage all current customers and evaluators to download the latest at http://www.dynadec.com/support/downloads/index.php

The distribution includes 18 examples of using Comet with three different paradigms (modules):
* constraint-based local search
* traditional constraint programming
* linear programming

It also contains detailed descriptions of the API (HTML).Note that the distribution is now via Dynadec, not Comet online (which links to an older version).

An earlier version of Comet is documented in the great book Constraint-Based Local Search by Pascal van av Hentenryck and Laurent Michel, the main developers of Comet.The book explains Comet and the principles of constraint-based local search very well, and I really recommend it. The newer development of Comet have been published in papers by the Comet developers, see Publications. (By the way, I also recommend Van Hentenryck's classic and pathbreaking book "Constraint Satisfaction in Logic Programming", which was my second read in this field, and I still enjoy re-reading it.)

I like Comet, but have been somewhat frustrated when the version 1.02 (the former version) broked older code (sometimes only slight changes was needed, though)), but now it has been stabilized. In the future I hope to come back with some of my own models.

Example: N-queen
As can been seen from the examples below the Comet language is quite C++-ish (or maybe rather OPL-ish?).

Here is two model of the n-queens problem. First using constraint-based local search (the example ls/queens.co)

import cotls;
int t0 = System.getCPUTime();
Solver m();
int n = 16;
range Size = 1..n;
UniformDistribution distr(Size);
var{int} queen[Size](m,Size) := distr.get();
ConstraintSystem S(m);
S.post(alldifferent(all(i in Size) queen[i] + i));
S.post(alldifferent(all(i in Size) queen[i] - i));
int it = 0;
while (S.violations() > 0 && it < 50 * n) {
selectMax(q in Size)(S.violations(queen[q]))
selectMin(v in Size)(S.getAssignDelta(queen[q],v))
queen[q] := v;
cout << queen << endl;

It solves the 1000-queens problem in about 1.5 seconds.

Here is the same problem, using the (traditional) constraint programming module (the example cp/queens.co)

import cotfd;
Solver m();
int t0 = System.getCPUTime();
int n = 8; //1000;
range S = 1..n;
var{int} q[i in S](m,S);
Integer np(m.getNPropag());
cout << "Initiating search..." << endl;
Integer c(0);
solveall {
m.post(alldifferent(all(i in S) q[i] + i),onBounds);
m.post(alldifferent(all(i in S) q[i] - i),onBounds);
} using {
forall(i in S) by (q[i].getSize()) { // : !q[i].bound()) by (q[i].getSize()) {
tryall(v in S : q[i].memberOf(v))
c := c + 1;
cout << "Nb : " << c << endl;
int t1 = System.getCPUTime();
cout << "Solution = " << q << endl;
cout << "time: " << t1 - t0 << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail = " << m.getNFail() << endl;
cout << "#propag = " << m.getNPropag() - np << endl;

Also see
Download Comet
Dyandec forums (Dynadec)

Comet online
publications, which contains many publications about Comet
mailing list
Wiki. Note: the wiki have not been updated for a while. For documentation about the API, see the documentation in the distribution.

January 22, 2009

New Gecode/R models: langford, all_interval, alpha, golomb_ruler and some more

I have now started to model some of the Gecode examples, and some other things, in Gecode/R.

Langford's number problem (CSPLib problem 24

Langford's number problem is a classic problem in constraint programming. It is the problem 24 in the CSPLib collection.

The problem is defined as:

Arrange 2 sets of positive integers 1..k to a sequence,
such that, following the first occurence of an integer i,
each subsequent occurrence of i, appears i+1 indices later
than the last.
For example, for k=4, a solution would be 41312432

Also see
* John E. Miller: Langford's Problem
* Encyclopedia of Integer Sequences for the number of solutions for each k
* My MiniZinc model langford2.mzn

The Gecode/R model for this problem is langford.rb.

All interval problem (CSPLib problem 7)

Another CSP classic. CSPLib formulates the problem such:

Given the twelve standard pitch-classes (c, c#, d, ...), represented by
numbers 0,1,...,11, find a series in which each pitch-class occurs exactly
once and in which the musical intervals between neighbouring notes cover
the full set of intervals from the minor second (1 semitone) to the major
seventh (11 semitones).


The constraints in the Gecode/R model all_interval.rb are simply

 x_is_an int_var_array(n, 1..n)         # The sequence
diffs_is_an int_var_array(n-1, 1..n-1) # The differences
(0..n-2).each{|k| diffs[k].must == (x[k+1] - x[k]).abs }

And two symmetry breaking constraints which, for n=12, which reduces the number of unique solution from 1328 (in 11 seconds) to 332 solutions (in 3 seconds).

x[0].must < x[1]
diffs[0].must > diffs[n-2]

The Gecode model all-interval (implemented in C++) solves the problem for n=1000 in 1 seconds. This Gecode/R model takes about 7 seconds after some tweaking with the :strength parameter.

Maybe I should benchmark the propagation strategies as for the Golomb ruler problem, see below.

Golomb ruler (CSPLib problem 6)

Yet another classic. See CSPLib problem number 6 for a formulation, and here for more references. Wikipedia's Golomb ruler has more info.

This Gecode/R model golomb_ruler.rb was quite slow at first. When testing for m = 10 it took about 15 seconds, which was about twice as slow as the MiniZinc model (this is from the MiniZinc online examples).

Gecode's program golomb-ruler solves n = 12 slightly under 1 seconds (with default settings). Something had to be done!

After some tweaking, like setting :strength => :bounds without any satisfying result, I decided on a more "scientific" approach, and benchmarked (some of) the different branch/search strategies for the branch_on method. There is a lot of these in Gecode/R.

After about 30 minutes of running, the ranking list below was completed. Note: the time is for running the specific model, not counting the time for startup of the program.

The winner was

:variable => :largest_size, :value =>: split_min 

which is used for all three variables in the model. Now m = 10 takes about 1 second.

The listing below states the time for the combination of the different strategies as
variable strategy ":" value strategy "->" running time

largest_size:split_min -> 1.114403
smallest_min:split_min -> 5.275035
smallest_min_regret:split_min -> 5.289433
none:split_min -> 5.320299
smallest_degree:split_min -> 5.344738
smallest_degree:min -> 5.551923
none:min -> 5.556326
smallest_min:min -> 5.567722
largest_max_regret:split_min -> 5.621116
smallest_min_regret:min -> 5.657271
largest_max_regret:min -> 5.783116
largest_size:min -> 6.067107
smallest_size:split_min -> 7.006949
largest_min:split_min -> 8.229713
smallest_size:min -> 11.800805
largest_min:split_max -> 14.558584
largest_min:min -> 14.736679
largest_min:max -> 17.301876
largest_size:split_max -> 17.564312
largest_min:med -> 23.655615
largest_size:max -> 26.835556
smallest_min:split_max -> 60.566207
largest_max_regret:split_max -> 60.605995
smallest_min_regret:split_max -> 60.79834
smallest_degree:split_max -> 60.948791
none:split_max -> 63.229398
smallest_size:split_max -> 80.155812
smallest_min_regret:max -> 84.988649
none:max -> 85.208536
smallest_degree:max -> 85.541162
largest_max_regret:max -> 85.64104
smallest_min:max -> 85.859321
smallest_size:max -> 93.474409
none:med -> 102.263753
largest_max_regret:med -> 103.352322
smallest_degree:med -> 103.688327
smallest_min:med -> 103.78953
smallest_size:med -> 131.829423
largest_size:med -> 160.26752
smallest_min_regret:med -> 181.760703

It is quite a span from the fastest to the slowest. It seems that :value => :med is bad for this problem.

alpha (alphametic problem)

Gecode/R model alpha.rb.

This alphametic problem asks for a solution of the equations below. The letters "a".."z" shall be unique assigned one and each of the numbers 1..26.

b+a+l+l+e+t       == 45 
c+e+l+l+o         == 43 
c+o+n+c+e+r+t     == 74 
f+l+u+t+e         == 30 
f+u+g+u+e         == 50 
g+l+e+e           == 66 
j+a+z+z           == 58 
l+y+r+e           == 47 
o+b+o+e           == 53 
o+p+e+r+a         == 65 
p+o+l+k+a         == 59 
q+u+a+r+t+e+t     == 50 
s+a+x+o+p+h+o+n+e == 134
s+c+a+l+e         == 51 
s+o+l+o           == 37 
s+o+n+g           == 61 
s+o+p+r+a+n+o     == 82 
t+h+e+m+e         == 72 
v+i+o+l+i+n       == 100
w+a+l+t+z         == 34 

See also
* the Gecode program alpha.ccp
* the MiniZinc models crypto.mzn, crypto_ip.mzn (integer programming model).

global cardinality

global_cardinality.rb implements the global constraint global_cardinality (the link is to the wonderful collections of global constraints: Global Constraint Catalog).

Nothing fancy, just this method, using the built in method count:

class Array
def global_cardinality(gcc)
@n = self.length
gcc[i].must == self.count(i)

Please note that this global constraint is just on the modellering level; there is no special (Gecode) code with optimized propagations etc. Even of they are not faster than "inline code", I see global constraints as conceptual building blocks, very useful in the modelling.

I intend to implement more global constraints in the future.

sliding sum

sliding_sum.rb implements another global constraint: sliding_sum, which constrain all sliding (running) sums to be between low and high.

January 19, 2009

Nonogram in Gecode/R

I have now implemented a model for solving Nonograms in Gecode/R: nonogram.rb. See My Gecode/R page for more about Gecode/R).

Wikipedia explains Nonogram in this way (Nonogram

Nonograms or Paint by Numbers are picture logic puzzles in which cells in a
grid have to be colored or left blank according to numbers given at the
side of the grid to reveal a hidden picture. In this puzzle type, the
numbers measure how many unbroken lines of filled-in squares there are
in any given row or column. For example, a clue of "4 8 3" would mean
there are sets of four, eight, and three filled squares, in that order,
with at least one blank square between successive groups.

A problem file may looks like this (see the file nonogram_heart.txt). First are the rules for the rows, then the rules for the columns.



The solution is a heart:

## ##
#### ####
# ### #
## # ##
# #
## ##
## ##

The program parses a nonogram problem file (or uses a default problem sans a problem file) and translates the rules to "regular expressions", e.g. the rule 3,2 is translated to the "regular expression" [repeat(0), repeat(1,3,3), at_least_once(0),repeat(1,2,2),repeat(0)] (i.e. the regexp /^0*1{3}0+1{3}0*$/), which means:
* start with 0 or more 0's
* then exactly 3 1's
* then 1 or more 0's
* then exactly 2 1's
* and last 0 or more 0's

For more about regular expressions in Gecode/R, see Integer Enum operands

The code
The translation is done via this method (debug printouts has been omitted):

def parse_regex(a, debug = false)
r = [repeat(0)]
r << repeat(1,e,e)
if i < a.length-1 then
r << at_least_once(0)
r << repeat(0)
return r

The constraint part is

def initialize(row_rules, col_rules)
rows = row_rules.length
cols = col_rules.length
x_is_an int_var_matrix(rows, cols, 0..1) # decision matrix
rows.times{|i| # rows
x.row(i).must.match(parse_regex(row_rules[i], debug))
cols.times{|j| # columns
x.column(j).must.match parse_regex(col_rules[j], debug)
branch_on x, :variable => :none, :value => :max

Except for the P200 problem, all problem listed below was solved in about a second or two. For the P200 problem the solution is printed in about 3 seconds, then it takes nearly a minute to very that there are no other solution.

Most problems are from Gecode examples:
* nonogram.rb: The model
* nonogram_simple.txt: Very simple problem
* nonogram_bear.txt: Bear
* nonogram_crocodile.txt: Crocodile
* nonogram_difficult.txt: Difficult
* nonogram_dragonfly.txt: Dragonfly
* nonogram_heart.txt: Heart
* nonogram_house.txt: House
* nonogram_nonunique.txt: Non unique problem (43 solutions)
* nonogram_p200.txt: P200
* nonogram_pinwheel.txt: Pinwheel
* nonogram_soccer_player.txt: Soccer player
* nonogram_unknown.txt: "Unkwnown"

Also see my MiniZinc model nonogram.mzn, which is way more complicated and often much slower.

January 18, 2009

Some other Gecode/R models, mostly recreational mathematics

Here are some new Gecode/R models. They are mostly in recreation mathematics since I still learning the limits of Gecode/R and want to use simple problems.


This is a simple alphametic puzzle: SEND + MOST = MONEY and the model is based on the example in the Gecode/R distribution (send_most_money.rb). The difference with its cousin SEND + MORE = MONEY is that there are many solutions, and we want to maximize the value of MONEY (10876).

The model is send_most_money2.rb.

Now, there are actually 4 different solutions for MONEY = 10876 which we want to find.

s e n d m o s t y
3 7 8 2 1 0 9 4 6
5 7 8 2 1 0 9 4 6
3 7 8 4 1 0 9 2 6
5 7 8 4 1 0 9 2 6

In order to do that, the model first solves the maximation problem and assigns the value (10876) to max_value; the second steps finds all 4 solutions. These two steps use the same code with the difference that the second step activates the following constraint

if (max_money > 0) then
money.must == max_money

Nothing fancy, but it quite easy to to it in Ruby and Geocde/R.

Steiner triplets

This is another standard problem in the constraint programming (and recreational mathematics) community: Find a set of triplet of numbers from 1 to n such that any two (different) triplets have at most one element in common.

For more about this, see Mathworld: SteinerTripleSystem, and Wikipedia Steiner_system.

The Gecode/R model is steiner.rb.

The problem can be simply stated as:

nb = n * (n-1) / 6 # size of the array
sets_is_an set_var_array(nb, [], 1..n)
sets.must.at_most_share_one_element(:size => 3)
branch_on sets, :variable => :smallest_unknown, :value => :min

This, however, is very slow (and I didn't care to wait that long for a solution). I tried some other branch strategies but found none that made some real difference.

When the following constraint was added, it really fasten things up. This in effect the same as the constraint sets.must.at_most_share_one_element(:size => 3) above:

sets[i].size.must == 3
(sets[i].intersection(sets[j])).size.must <= 1

The first 10 solutions for n = 7 took about 1 seconds. The first solution is:

Solution #1
{1, 2, 3}
{1, 4, 5}
{1, 6, 7}
{2, 4, 6}
{2, 5, 7}
{3, 4, 7}
{3, 5, 6}
memory: 25688
propagations: 302
failures: 0
clones: 2
commits: 16

For n = 9, 10 solutions took slightly longer, 1.3 seconds.

Devil's Words

Gecode/R model: devils_word.rb.

Devil's word is a "coincidence game" where a the ASCII code version of a name, often a famous person's, is calculated to sum up to 666 and some points is made about that fact (which of course is nonsense).

There are 189 different ways my own name HakanKjellerstrand (where the umlaut "å" in my first name is replaced with "a") can be "devilized" to 666. With output it took about 2 seconds to generate the solutions, without output it took 0.5 seconds.

The first solution is:

+72 +97 +107 +97 +110 -75 +106 +101 +108 -108 -101 +114 +115 +116 +114 -97 -110 -100

Also, see
* MiniZinc model: devils_word.mzn
* my CGI program: Devil's words.

And see Skeptic's law of truly large numbers (coincidence) for more about coincidences. The CGI program mentioned above was presented in the swedish blog post Statistisk data snooping - att leta efter sammanträffanden ("Statistical data snooping - to look for coincidences") which contains some more references to these kind of coincidences.

Pandigital Numbers, "any" base

Pandigital numbers are a recreational mathemathics construction. From MathWorld Pandigital Number

A number is said to be pandigital if it contains each of the digits
from 0 to 9 (and whose leading digit must be nonzero). However,
"zeroless" pandigital quantities contain the digits 1 through 9.
Sometimes exclusivity is also required so that each digit is
restricted to appear exactly once.

The Gecode/R model pandigital_numbers.rb extends this to handle "all" bases. Or rather bases from 2 to 10, since larger bases cannot be handled by the Gecode solver.

For base 10 using the digits 1..9 there are 9 solutions:

4 * 1738 = 6952 (base 10)
4 * 1963 = 7852 (base 10)
18 * 297 = 5346 (base 10)
12 * 483 = 5796 (base 10)
28 * 157 = 4396 (base 10)
27 * 198 = 5346 (base 10)
39 * 186 = 7254 (base 10)
42 * 138 = 5796 (base 10)
48 * 159 = 7632 (base 10)

For base 10, using digits 0..9, there are 22 solutions.

Here is the number of solutions for base from 5 to 10 and start either 0 or 1 (there are no solutions for base 2..4):
* base 2, start 0: 0
* base 2, start 1: 0
* base 3, start 0: 0
* base 3, start 1: 0
* base 4, start 0: 0
* base 4, start 1: 0
* base 5, start 0: 0
* base 5, start 1: 1
* base 6, start 0: 0
* base 6, start 1: 1
* base 7, start 0: 2
* base 7, start 1: 2
* base 8, start 0: 4
* base 8, start 1: 4
* base 9, start 0: 10
* base 9, start 1: 6
* base 10, start 0: 22
* base 10, start 1: 9

See also the MiniZinc model pandigital_numbers.mzn with a slightly different approach using the very handy MiniZinc construct exists instead of looping through the model for different len1 and len2.

SEND + MORE = MONEY (any base)

And talking of "all base" problems, send_more_money_any_base.rb is a model for solving SEND+MORE=MONEY in any base from 10 and onward.

The number of solutions from base 10 and onward are the triangle numbers, i.e. 1,3,6,10,15,21,... I.e.

* Base 10: 1 solution
* Base 11: 3 solutions
* Base 12: 6
* Base 13: 10
* Base 14: 15
* Base 15: 21
* etc

For more about triangle numbers, see Wikipedia Triangular numbers.

There seems to be a pattern of the solutions given a base b:

           S  E  N  D  M  O  R  Y
 Base 10:  9  5  6  7  1  0  8  2
 Base 11: 10  7  8  6  1  0  9  2
          10  6  7  8  1  0  9  3
          10  5  6  8  1  0  9  2
 Base 12:
          11  8  9  7  1  0 10  3
          11  8  9  6  1  0 10  2
          11  7  8  9  1  0 10  4
          11  6  7  9  1  0 10  3
          11  6  7  8  1  0 10  2
          11  5  6  9  1  0 10  2
 Base 23:
          22 19 20 18  1  0 21 14
          22 19 20 17  1  0 21 13

Some patterns:

S: always base-1 e.g. 9 for base 10
M: always 1 e.g. 1 any base
0: always 0 e.g. 0 any base
R: always base-2 e.g. 8 for base 10
E, N, D: from base-3 down to 5 e.g. {5,6,7,8,9} for base 10
Y: between 2 and ??? e.g. {2,3,4} for base 12

I haven't read any mathematical analysis of these patterns. There is an article in math Horizons April 2006: "SENDing MORE MONEY in any base" by Christopher Kribs-Zaleta with the summary: Dudeney's classic "Send More Money" cryptarithmetic puzzle has a unique solution in base ten. This article generalizes explores solutions in bases other than ten. I haven't read this article, though.

Also, see my MiniZinc model send_more_money_any_base.mzn.

January 15, 2009

Some models in Gecode/R (Ruby interface to Gecode)

Gecode/R is a great Ruby interface to Gecode (implemented in C++). At last I now have done some modeling in Gecode/R and it's nice.

The models and some other information about Gecode/R can be seen at My Gecode/R page.

Since Ruby is a very high level language, the modelling can be done "high levelish", more so than for example with the Java solvers Choco and JaCoP. And that is a feature I really like.

I'm still learning Gecode/R and have surely missed some stuff. There are not many examples in the package (these are also commented at Examples). Some things have been of great help
* The Sitemap
* The Documentation, especially the RDocs
* The test files in the specs directory.

An example: Survo Puzzle
From Wikipedia's Survo Puzzle

In a Survo puzzle the task is to fill an m * n table by integers 1,2,...,m*n so
that each of these numbers appears only once and their row and column sums are
equal to integers given on the bottom and the right side of the table.
Often some of the integers are given readily in the table in order to
guarantee uniqueness of the solution and/or for making the task easier.

E.g. the puzzle 128/2008 is presented with the following clues:

* * * * * * 30
* * 18 * * * 86
* * * * * * 55
22 11 42 32 27 37

where * marks a digit to find. The number to the right is the row sums which the row must sum to, and the last row is the column sums.

The unique solution of the problem is (by running the program ruby survo_puzzle.rb survo_puzzle_128_2008.txt)

Solution #1
4 1 10 5 3 7 = 30
12 8 18 16 15 17 = 86
6 2 14 11 9 13 = 55
= = = = = =
22 11 42 32 27 37

propagations: 3784
failures: 174
clones: 179
memory: 25740
commits: 461
Number of solutions: 1

The relevant constraint programming code is below (slightly edited). I think it's quite nice.

def initialize(clues, rowsums, colsums)
r = rowsums.length # number of rows
c = colsums.length # number of columns
x_is_an int_var_matrix(r, c, 1..r*c) # the solution matrix
x.must_be.distinct # all values in x must be distinct
# values in clues with values > 0 are copied straight off to x
x[i,j].must == clues[i][j] if clues[i][j] > 0
r.times{|i| x[i,0..c-1].sum.must == rowsums[i] } # check row sums
c.times{|j| x.transpose[j,0..r-1].sum.must == colsums[j] } # check column sums
branch_on x, :variable => :smallest_size, :value => :min

The full program is here: survo_puzzle.rb, and three data files:

The Gecode/R models
Below are the models shown at My Gecode/R page. The selection is mostly for comparison with models implemented in other constraint programming languages, see respectively:
My MiniZinc page (which has a lot more models)
My JaCoP page
My Choco page

The models first written (e.g. diet, least_diff) are very "un-Rubyish" since I wanted to model straight after the MiniZinc models. Maybe I Rubyfi these later.

After a while the modeling went quite easy, and both de Bruijn and Minesweeper was done surprisingly fast. I do, however, miss MiniZinc's sum construct, since it which make some things easier (e.g. the neighbour summing in minesweeper.rb).

The execution time of the models os approximately the same time as the corresponding MiniZinc model with the Gecode/flatzinc solver which is normally quite fast. The big exception of these examples is coins_grid which seems to be slow for the constraint programming systems, but fast with linear programming systems, e.g. with the MiniZinc solvers ECLiPSe/ic and MiniZinc/mip.

References to the problems etc are in the header of the model.

January 06, 2009

Map coloring problem: Lichtenstein

In The Chromatic Number of Liechtenstein bit-player asked (2008-10-28)) the following about coloring the map of Lichtenstein:

It seems that Liechtenstein is divided into 11 communes, which emphatically do not satisfy the connectivity requirement of the four color map theorem. Just four of the communes consist of a single connected area (Ruggell, Schellenberg and Mauren in the north, and Triesen in the south). All the rest of the communes have enclaves and/or exclaves.


In the map above, each commune is assigned its own color, and so we have an 11-coloring. It’s easy to see we could make do with fewer colors, but how many fewer? I have found a five-clique within the map; that is, there are five communes that all share a segment of border with one another. It follows that a four-coloring is impossible. Is there a five-coloring? What is the chromatic number of Liechtenstein?

I wrote a MiniZinc model for this minimizing problem: lichtenstein_coloring.mzn.

The model has two variable arrays:
* color_communes: the color of the 11 communes
* color: the color of the 29 en-/exclaves

Objective: minimize the number of colors used.

The Gecode/flatzinc solver gives the following solutions in less than 1 second, which states that 5 different colors (n_colors) is sufficient. The model allows for up to 11 different colors, hence the large color numbers.

n_colors: 5
color_communes: [1, 1, 10, 8, 8, 1, 9, 9, 8, 10, 11]
color: [1, 1, 1, 1, 1, 1, 10, 10, 8, 8, 8, 8, 8, 1, 9, 9, 9, 9, 9, 9, 8, 10, 10, 11, 11, 11, 11, 11, 11]

Optimal solution found.

runtime: 290
solutions: 4
propagators: 1235
propagations: 1992711
failures: 1045
clones: 1046
commits: 2757
peak memory: 1414 KB

Times for other MiniZinc solvers:
* Minizinc's flatzinc: 2 seconds,
* Minizinc's fdmip: 2 seconds,
* ECLiPSe's ic: 4 seconds
* tinifz: 5.5 seconds

Also see
The chromatic number of Lichtenstein by Michi (from whom I borrowed the edges).

January 05, 2009

Tom Schrijvers: "Monadic Constraint Programming" (in Haskell)

Tom Schrijvers presents in the blog post Monadic Constraint Programming a draft version of the paper Monadic Constraint Programming written by him, Peter Stuckey, and Philip Wadler:

A constraint programming system combines two essential components: a constraint solver and a search engine. The constraint solver reasons about satisfiability of conjunctions of constraints, and the search engine controls the search for solutions by iteratively exploring a disjunctive search tree defined by the constraint program. In this paper we give a monadic definition of constraint programming where the solver is defined as a monad threaded through the monadic search tree. We are then able to define search and search strategies as first class objects that can themselves be built or extended by composable search transformers. Search transformers give a powerful and unifying approach to viewing search in constraint programming, and the resulting constraint programming system is first class and extremely flexible.

Prototype code in Haskell can be downloaded here.

Some constraint programming news

Note: This is an abridged translation of my swedish blog post Constraint programming-nyheter samt nya MiniZinc-modeller, written 2008-12-27

Here is some news in constraint programming since about october 2008

My Constraint Programming page
In order to collect my constraint programming models/references, I have created My constraint programming page, which right now just links to my other constraint programming pages, i.e. "My XXXXXX page" where "XXXXX" in {MiniZinc, Choco, JaCoP}, see below.


(The model mortgage.mzn has been in the test directory for a while, due to a bug report.)

See My MiniZinc page


See My JaCoP page.


  • version is released

Also, see My Choco page.

Tailor is a nice modelling system which translates a Essence' (a a simpler version of the modelling language Essence) to Minion. Tailor is implemented in Java and contains a basic GUI for modelling.

I have written some Tailor models but they are not yet public, in part because the specification of Tailor/Essence' has not been stable. I will hopefully return to this later.

A note in passing: Some of my MiniZinc models are translations of Tailor/Essence' examples, e.g. futoshiki.mzn and K4P2GracefulGraph.mzn.

Global Constraint Catalog
The great Global constraint catalog was updated 2008-11-15, and has some new constraints, e.g. geost and other packning-constraints.

The site now have a new URL scheme. Instead of URL:s like http://www.emn.fr/x-info/sdemasse/gccat/sec4.5.html (for the global constraint alldifferent_cst), the URL is now http://www.emn.fr/x-info/sdemasse/gccat/Calldifferent_cst.html, i.e. .../C followed by the constraint name.

Most of the references to this site in my MiniZinc global constraint models use the old scheme. This may be adjusted in the future.

Gecode has not released any new version since august 2008. However, the SVN version of Gecode/flatzinc (the MiniZinc solver) has been updated to support the new MiniZinc versions.

Gecode/R is a Ruby interface to Gecode:

Gecode/R provides access to many, but not all, of the features in Gecode 2.2.0. Gecode/R is only a modelling interface, it does not provide support for e.g. creating new propagators.

Version 1.0 was released in september (2008).

I have - somewhat surprisingly - not worked with Gecode/R that much. Hopefully this will be corrected in the future.

Comet is a constraint programming system which uses "local search". It is now "commercialized" and version 1.02 (time limited) can be download via Dynadec.

This version is more competent and complete than the former beta version, but there is now even more differences to the great book Constrant-based local search written by Pascal Van Hentenryck and Laurent Michel.