My Constraint Programming Blog

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.

• coins_grid.rb: Placing coins on a grid (Tony Hurlimann)
• debruijn_binary.rb: de Bruijn sequences, both "classic" and "arbitrary"
• diet.rb: simple diet problem (operations research)
• least_diff.rb: Least diff problem, an alphametic puzzle, minimize the difference ABCDE-FGHIJ where A..J is integers 0..9 (all different)
• map.rb: Simple map coloring problem.
  
• minesweeper.rb: Minesweeper problem.
  Problem files for the Minesweeper program.
  Usage: ruby minesweeper.rb problem file
  
  • Problem 0 from Gecode minesweeper.cc
  • Problem 1 from Gecode minesweeper.cc
  • Problem 2 from Gecode minesweeper.cc
  • Problem 3 from Gecode minesweeper.cc
  • Problem 4 from Gecode minesweeper.cc
  • Problem 5 from Gecode minesweeper.cc
  • Problem 6 from Gecode minesweeper.cc
  • Problem 7 from Gecode minesweeper.cc
  • Problem 8 from Gecode minesweeper.cc
  • Problem 9 from Gecode minesweeper.cc
  • From "Some Minesweeper Configurations",page 2
  • From "Some Minesweeper Configurations",page 3
  • From Richard Kaye: How Complicated is Minesweeper?, splitter (131072 solutions)
  • From Richard Kaye: How Complicated is Minesweeper?, wire
• seseman.rb: simple recreational mathematics puzzle. See the CGI-program Seseman convent problem
• survo_puzzle.rb: Survo puzzle Problem files:
  
  • survo_puzzle_126_2008.txt
  • survo_puzzle_127_2008.txt
  • survo_puzzle_128_2008.txt
• xkcd.rb: XKCD's knapsack problem. See the xkcd strip for the problem