« Map coloring problem: Lichtenstein | Main | Some other Gecode/R models, mostly recreational mathematics »

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.

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.

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.

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)