Main

October 08, 2010

Gecode version 3.4.1 released

Gecode version 3.4.1 has been released and can be downloaded here.

From Changes:
This release adds a new global constraint for bin-packing (with extended example) and filter functions for branchers. The reference documentation has been cleaned up. In particular, information on how to obtain, install, and link Gecode has been expanded and moved to "Modeling and Programming with Gecode" (Section 2.6). Additionally, the release fixes some bugs and contains some performance improvements.
  • Kernel
    • Other changes
      • Branching now honors filter functions, where variables are considered for branching only if the filter functions returns true (see "Modeling and Programming with Gecode" for details). (major, thanks to Felix Brandt)
      • Variable implementation views are now parametric with respect to variables but not variable implementations (see "Modeling and Programming with Gecode" for details). (minor)
      • Renamed the template class for variables defined by a variable implementation from Var to VarImpVar and re-added a class Var as base class for any variable type. (minor)
  • Finite domain integers
    • Additions
      • Added a binpacking constraint and propagator. (major)
    • Bug fixes
      • Do not inline functions with variable arguments. (minor, thanks to Gustavo A. Gómez Farhat)
      • The reified dom constraint failed instead of setting the BoolVar to 0 when the minimum argument given was greater than the maximum. (minor, thanks to Kish Shen)
    • Performance improvements
      • Fixed sortedness constraint by replacing an algorithm that is linear in the width of the union of all domains with an algorithm that is quadratic in the number of variables. The previous algorithm crashed for domains with large values due to excessive memory use. (minor, thanks to Kish Shen)
      • Using ICL_DOM for binary linear equations with unit coefficients (such as x = y+3) is now implemented using the much more efficient binary equality propagator instead of the linear equation propagator (which has worst case exponential runtime). (minor)
  • Scheduling constraints
    • Bug fixes
      • Fixed initialization for unary and cumulative edge-finding (just worked accidentally). (major, thanks to Roberto Castañeda Lozano)
  • Minimal modeling support
    • Other changes
      • Added element expression for BoolVarArgs. (minor)
    • Bug fixes
      • Fixed memory allocation for non-linear expressions and made the LinExpr constructor explicit for non-linear expressions (previously the automatic cast from integers to LinExpr was sometimes ambiguous). (minor)
  • Script commandline driver
    • Additions
      • Added a class InstanceOptions that takes one additional string argument. (minor)
  • Range and value iterators
    • Performance improvements
      • Reimplemented n-ary union, minus, and cache iterators for much better efficiency. (minor)
  • Example scripts
    • Additions
      • Added a binpacking model using the binpacking constraint and CDBF (complete decreasing best fit) search. (major)
  • Gist
    • Other changes
      • Only center node on double-click if it was undetermined (otherwise inspecting several nodes becomes slightly annoying). (minor)
    • Performance improvements
      • Saved some memory for each node in Gist (one pointer per node, two integers per inner node, and some additional memory on 64 bit platforms due to optimizing alignment), and speeded up deallocation of the tree (e.g. when resetting or closing Gist). (minor)
  • Gecode/FlatZinc
    • Additions
      • Added support for global_cardinality_low_up. (minor)
    • Performance improvements
      • The FlatZinc parser now uses hash maps instead of STL maps, which significantly increases parsing performance for larger files. Furthermore, a single symbol table is used, also increasing performance and allowing to report duplicate symbol errors, which were previously ignored. (minor)
  • General
    • Documentation fixes
      • Removed obsolete Glossary in reference documentation. (minor)

May 08, 2009

Learning Constraint Programming III: decomposition of a global constraint: alldifferent_except_0

The series Learning Constraint Programming is a preparation for My talk at SweConsNet Workshop 2009: "Learning Constraint Programming (MiniZinc, JaCoP, Choco, Gecode/R, Comet, Gecode): Some Lessons Learned". Confusingly, the entries is not numbered in any logical order. Sorry about that.

Here are the previous entries:

Introduction

The global constraint alldifferent_except_0 (or the more general variant alldifferent_except_c) is one of my favorite global constraints. It is very handy to use when 0 (or any constant c) is coded as an unknown or irrelevant value. Then we can constraint the rest to be all distinct.

The great Global Constraint Catalog entry alldifferent_except_0) explains this constraint as:
Purpose
Enforce all variables of the collection VARIABLES to take distinct values, except those variables that are assigned to 0.

Example
​(<5,​0,​1,​9,​0,​3>)​
The alldifferent_except_0 constraint holds since all the values (that are different from 0) 5, 1, 9 and 3 are distinct.

Models

I have modeled a decomposition of alldifferent_except_0 in the following models, where the constraint is just tested perhaps combined with some other constraint, e.g. sorted or that there must be at least some zeros:

- MiniZinc alldifferent_except_0.mzn
- Comet: alldifferent_except_0.co
- Gecode/R: all_different_except_0.rb
- Choco: AllDifferentExcept0_test.java
- JaCoP: AllDifferentExcept0_test.java
- Gecode: alldifferent_except_0.cpp

Some models using alldifferent_except_0

And here is some real use of the constraint:

- Nonogram (Comet): nonogram.co. (A faster model using the regular constraint, nonogram_regular.co, is described here and here).
- I wrote about alldifferent_except_0 in Pi Day Sudoku 2009. However, as faster way of solving the problem was found and is described in Solving Pi Day Sudoku 2009 with the global cardinality constraint). Note: the competition is still on, so there is no link to any model.
- Sudoku generate (Comet): sudoku_generate.co
- all paths graph (MiniZinc): all_paths_graph.mzn
- Cube sum (MiniZinc): cube_sum.mzn
- Message sending (MiniZinc): message_sending.mzn

As the first two entries indicates, there may be faster solutions than using (a decomposition) of alldifferent_except_0, but even as a decomposition is a great conceptual tool when modeling a problem.

Implementations

In the implementations below we also see how to define a function (predicate) in the constraint programming systems.

For the Gecode/R model there are different approaches:
- "standard" ("direct") approach where we loop over all different pairs of elements and ensures that if both values are different from 0 then they should be different
- using count
- using global cardinality ("simulated" in Gecode/R, see below)

Also, in some models we use the slighly more general version alldifferent_except_c where c is any constant (e.g. "Pi" in the Pi Day Sudoku puzzle mentioned above.

MiniZinc:

Model: alldifferent_except_0.mzn.
predicate all_different_except_0(array[int] of var int: x) =
   let {
      int: n = length(x)
   }
   in
   forall(i,j in 1..n where i != j) (
        (x[i] > 0 /\ x[j] > 0) 
        -> 
        x[i] != x[j]
   )
;

// usage:
constraint all_different_except_0(x);

Comet:

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]
           );
  }
}

// usage
exploreall {
  // ...
  alldifferent_except_0(m, x);
}

Gecode/R

Model:all_different_except_0.rb.

When modeling the constraint in Gecode/R, I experimented with different approaches. The reification variant all_different_except_0_reif is actually quite fast.
# The simplest and the fastest implementation 
# using count for 1..max (poor man's global cardinality)
def all_different_except_0
  (1..self[0].domain.max).each{|i|
    self.count(i).must <= 1
  }
end

# global cardinality version using an extra array with the counts
def global_cardinality(xgcc)
  (self[0].domain.max+1).times{|i|
    xgcc[i].must == self.count(i)
  }
end

#
# The standard approach using reification.
#
def all_different_except_0_reif(x)
  n = x.length
  b1_is_an bool_var_matrix(n,n)
  b2_is_an bool_var_matrix(n,n)
  b3_is_an bool_var_matrix(n,n)
  n.times{|i|
    n.times{|j|
      if i != j then 
        x[i].must_not.equal(0, :reify => b1[i,j]) 
        x[i].must_not.equal(0, :reify => b2[i,j]) 
        x[i].must_not.equal(x[j], :reify => b3[i,j])
        (b1[i,j] & b2[i,j]).must.imply(b3[i,j])
      else 
        b1[i,j].must.true
        b2[i,j].must.true
        b3[i,j].must.true
      end
    }
  }
end

    # ...
    # usage:
    x.all_different_except_0
    # all_different_except_0_gcc(x)
    # all_different_except_0_reif(x)

Choco

Model: AllDifferentExcept0_test.java.

Note that here alldifferent_except_0 is derived from the more general version alldifferent_except_c.
//
// decomposition of alldifferent except 0
//
public void allDifferentExcept0(CPModel m, IntegerVariable[] v) {
    allDifferentExceptC(m, v, 0);
}

//
// slightly more general: alldifferent except c
//
public void allDifferentExceptC(CPModel m, IntegerVariable[] v, int c) {
    int len = v.length;
    for(int i = 0; i < v.length; i++) {
        for(int j = i+1; j < v.length; j++) {
            m.addConstraint(ifThenElse(
                                       and(
                                           gt(v[i], c), 
                                           gt(v[j], c)
                                           ), 
                                       neq(v[i], v[j]),
                                       TRUE
                                       )
                            );
        }
    }    
}

// ...
// usage: 

    m.addConstraint(allDifferent(queens));

JaCoP

Model: AllDifferentExcept0_test.java

This is exactly the same approach as the Choco version.
//
// decomposition of alldifferent except 0
//
public void allDifferentExcept0(FDstore m, FDV[] v) {
    allDifferentExceptC(m, v, 0);
} // end allDifferentExcept0


//
// slightly more general: alldifferent except c
//
public void allDifferentExceptC(FDstore m, FDV[] v, int c) {
    int len = v.length;
    for(int i = 0; i < v.length; i++) {
        for(int j = i+1; j < v.length; j++) {
            m.impose(new IfThen(
                                       new And(
                                           new XneqC(v[i], c), 
                                           new XneqC(v[j], c)
                                           ), 
                                       new XneqY(v[i], v[j])
                                       )
                            );
        }
    }        
} // end allDifferentExceptC


        // ...
        // usage:
        allDifferentExcept0(store, x);

Gecode

alldifferent_except_0.cpp

The Gecode version is very succint since it use overloaded boolean operators. Very nice.
void alldifferent_except_0(Space& space, IntVarArray x, IntConLevel icl = ICL_BND) {
  for(int i = 0; i < x.size(); i++) {
    for(int j = i+1; j < x.size(); j++) {
      post(space,
           tt(
           imp(x[i] != 0 && x[j] != 0, 
           // =>
           x[i] != x[j])),
           icl
           );
    }
  }
} // alldifferent_except_0


// ...
// usage:
    alldifferent_except_0(*this, x, opt.icl());

February 04, 2009

Some of my models now at the Gecode/R site

In the comments of Some models in Gecode/R (Ruby interface to Gecode), Andreas Launila - the maintainer of Gecode/R - indicated that he wanted to include some of my models in the Gecode/R distribution.

As of writing, he has included two models in the Examples collection (as well as the SVN repository):
* nonogram.rb: Nonogram, painting by numbers
* minesweeper.rb: Minesweeper

Please note that Andreas has made some modifications which makes them much neater. For comparison, my original models is at My Gecode/R page.

Thanks Andreas!

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
x.must_be.distinct
diffs.must_be.distinct
(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
(@n).times{|i|
gcc[i].must == self.count(i)
}
end
end

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.

row_rules
2,2
4,4
1,3,1
2,1,2
1,1
2,2
2,2
3
1

col_rules
3
2,3
2,2
2,2
2,2
2,2
2,2
2,3
3

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)]
a.each_with_index{|e,i|
r << repeat(1,e,e)
if i < a.length-1 then
r << at_least_once(0)
end
}
r << repeat(0)
return r
end

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
end

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


SEND + MOST = MONEY


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
end

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:

n.times{|i|
sets[i].size.must == 3
(i+1..n-1).each{|j|
(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.


Pattern
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

Statistics:
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
r.times{|i|
c.times{|j|
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
end

The full program is here: survo_puzzle.rb, and three data files:
survo_puzzle_126_2008.txt
survo_puzzle_127_2008.txt
survo_puzzle_128_2008.txt


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.