A
Andreas Launila
Gecode/R version 0.9.0 has been released.
http://gecoder.rubyforge.org/
This release contains all functionality planned for 1.0.0.
== What is Gecode/R?
Gecode/R is a Ruby interface to the Gecode constraint programming
library[1]. Gecode/R is intended for people with no previous experience
of constraint programming, aiming to be easy to pick up and use.
Constraint programming means that you describe the problem to the
solver, using variables and constraints, and then let the solver find
the solution. It is useful for solving problems where you have to do a
search through various assignments to find the best solution (or just
any solution). This includes problems such as scheduling and sudoku.
== Installation
Install Gecode and Gecode/R:
gem install gecoder-with-gecode
== Example
The send+more=money problem, covered in a Ruby Quiz[3], is one of many
examples[2].
send
+ more
------
money
The problem is to assign 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). Using Gecode/R
to solve the problem is simple and much faster than a naive solution.
require 'rubygems'
require 'gecoder'
solution = Gecode.solve do
# 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
# 100*x + 10*y + z .
def equation_row(*variables)
variables.inject{ |result, variable| variable + result*10 }
end
# Set up the variables.
# Let "letters" be an array of 8 integer variables with domain 0..9.
# The elements represents the letters s, e, n, d, m, o, r and y.
letters_is_an int_var_array(8, 0..9)
s,e,n,d,m,o,r,y = letters
# 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
# Tell Gecode what variables we want to know the values of.
branch_on letters, :variable => :smallest_size, :value => :min
end
puts 's e n d m o r y'
puts solution.letters.values.join(' ')
Output:
s e n d m o r y
9 5 6 7 1 0 8 2
== Future plan
The current plan is to get ready for a 1.0.0 release by focusing on the
website documentation and checking for performance problems (cases when
Gecode/R does a poor translation of constraints to Gecode). Feedback on
how the website documentation could be improved and/or reorganized is
valued highly, especially if it comes from someone who is new to
constraint programming.
This is also the last chance to make backwards-compatibility breaking
changes before putting stakes in the ground. If you have any such
suggestions then this would be the time to present them.
== Changes
See http://gecoder.rubyforge.org/details/changes.html for the list of
changes.
[1] http://www.gecode.org/
[2] http://gecoder.rubyforge.org/examples.html
[3] http://rubyquiz.com/quiz128.html
http://gecoder.rubyforge.org/
This release contains all functionality planned for 1.0.0.
== What is Gecode/R?
Gecode/R is a Ruby interface to the Gecode constraint programming
library[1]. Gecode/R is intended for people with no previous experience
of constraint programming, aiming to be easy to pick up and use.
Constraint programming means that you describe the problem to the
solver, using variables and constraints, and then let the solver find
the solution. It is useful for solving problems where you have to do a
search through various assignments to find the best solution (or just
any solution). This includes problems such as scheduling and sudoku.
== Installation
Install Gecode and Gecode/R:
gem install gecoder-with-gecode
== Example
The send+more=money problem, covered in a Ruby Quiz[3], is one of many
examples[2].
send
+ more
------
money
The problem is to assign 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). Using Gecode/R
to solve the problem is simple and much faster than a naive solution.
require 'rubygems'
require 'gecoder'
solution = Gecode.solve do
# 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
# 100*x + 10*y + z .
def equation_row(*variables)
variables.inject{ |result, variable| variable + result*10 }
end
# Set up the variables.
# Let "letters" be an array of 8 integer variables with domain 0..9.
# The elements represents the letters s, e, n, d, m, o, r and y.
letters_is_an int_var_array(8, 0..9)
s,e,n,d,m,o,r,y = letters
# 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
# Tell Gecode what variables we want to know the values of.
branch_on letters, :variable => :smallest_size, :value => :min
end
puts 's e n d m o r y'
puts solution.letters.values.join(' ')
Output:
s e n d m o r y
9 5 6 7 1 0 8 2
== Future plan
The current plan is to get ready for a 1.0.0 release by focusing on the
website documentation and checking for performance problems (cases when
Gecode/R does a poor translation of constraints to Gecode). Feedback on
how the website documentation could be improved and/or reorganized is
valued highly, especially if it comes from someone who is new to
constraint programming.
This is also the last chance to make backwards-compatibility breaking
changes before putting stakes in the ground. If you have any such
suggestions then this would be the time to present them.
== Changes
See http://gecoder.rubyforge.org/details/changes.html for the list of
changes.
[1] http://www.gecode.org/
[2] http://gecoder.rubyforge.org/examples.html
[3] http://rubyquiz.com/quiz128.html
