Gecode/R 0.5.0

Ruby
1

Gecode/R version 0.5.0 has been released.

http://gecoder.rubyforge.org/

It’s still in the development, so don’t expect any form of backwards
compatibility (things will change left and right if needed to).

== What is Gecode/R? ==

Gecode/R is a Ruby interface to Gecode[1] which allows you to use
constraint programming in Ruby. It’s typically useful for problems where
you otherwise have to do a search through various assignments to find a
solution. All you have to do is describe the properties of solutions to
a problem and Gecode will find them.

== Installation ==

First install Gecode 1.3.1 (see installation[4] for links). And then do

gem install gecoder

== Features ==

See the website[5] for a more detailed list.

  • Finite domain integers, booleans and finite set variables.
  • Supports many of Gecode’s integer constraints, all of the boolean
    constraints and some of the set constraints.
  • Reification and propagation strength.

== Example ==

send+more=money is one of the many examples[2].

send

  • more

money

The following assigns digits to each letter so that the above equation
holds when the letter are substituted with the assigned digits. No two
letters are assigned the same digit and the first letter of a word is
not assigned 0 (so that no number starts with 0).

class SendMoreMoney < Gecode::Model
def initialize
# Set up the variables, 8 letters with domain 0…9.
s,e,n,d,m,o,r,y = @letters = int_var_array(8, 0…9)

# Set up the constraints.
# The equation must hold.
(equation_row(s, e, n, d) + equation_row(m, o, r, e)).must ==
  equation_row(m, o, n, e, y)

# The initial letters may not be 0.
s.must_not == 0
m.must_not == 0

# All letters must be assigned different digits.
@letters.must_be.distinct

# Set the branching.
branch_on @letters, :variable => :smallest_size, :value => :min

end

def to_s
%w{s e n d m o r y}.zip(@letters).map do |text, letter|
“#{text}: #{letter.val}”
end.join(', ')
end

private

A helper to make the linear equation a bit tidier. Takes a number of

variables and computes the linear combination as if the variable

were digits in a base 10 number. E.g. x,y,z becomes

100x + 10y + z .

def equation_row(variables)
variables.inject{ |result, variable| variable + result10 }
end
end

puts SendMoreMoney.new.solve!.to_s

Output: s: 9, e: 5, n: 6, d: 7, m: 1, o: 0, r: 8, y: 2

== Learning more ==

The documentation[3] lists examples of all the available constraints and
features (which in combination with the examples should get you going).
Questions are welcome.

== Changes since last announcement ==

=== Version 0.5.0 / 11 July 2007 ===
This release adds set variables and some of their constraints, along
with the last of the boolean constraints.

  • Added exclusive or and implication.
  • Added conjunction and disjunction for boolean enumerations.
  • Added set variables. They are created using Model{#set_var,
    #set_var_array, #set_var_matrix}.
  • Added domain constraints for set variables.
  • Added relation constraints for set variables.
  • Added set cardinality constraints.

=== Version 0.4.0 / 3 July 2007 ===
This release adds most of the integer variable constraints supported by
Gecode.

  • [#11861] Fixed a bug stopping the creation of int variables with
    non-range domains.
  • Added domain constraints for int variables.
  • Added equality constraint for int enums.
  • Matrices of integer and boolean variables can now be created using
    Model#int_var_matrix Model#bool_var_matrix.
  • Added channel constraint for int enums.
  • Added element constraints (variable array access).
  • Added count constraints.
  • Added sortedness constraints.
  • Added arithmetic constraints (min, max, abs and variable
    multiplication).

[1] http://www.gecode.org/
[2] http://gecoder.rubyforge.org/examples.html
[3] http://gecoder.rubyforge.org/documentation/
[4] http://gecoder.rubyforge.org/installation.html
[5] http://gecoder.rubyforge.org/features.html