### 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 37Statistics:

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:

- xkcd.rb: XKCD's knapsack problem. See the xkcd strip for the problem

## Comments

I agree that Gecode/R could use more example models. As a starter, I have added a link to this blog on the examples page on Gecode/R's website.

It would also be nice to include some of these examples in the distribution, assuming that they were to be released under the LGPL or something compatible.

Posted by: Andreas Launila | January 19, 2009 11:18 AM

Andreas: Thanks for a great system! And for the link.

I really enjoy working in Gecode/R.

About the license: It would be great if you include some of my programs in the distribution. Feel free to include what you want.

I don't have any specific license in mind for my programs/models. The only thing is that it would be nice with some kind of cred: my name and email address suffices, perhaps an URL. If this is too fuzzy for you to work with, then we surely can decide on a specific license.

Posted by: hakank | January 19, 2009 05:57 PM