by Jay Anderson
For this quiz the goal is to make a constraint processing library for ruby. A Constraint Satisfaction Problem consists of variables, domains for each variable, and constraints among the variables. Here's a sample (Solutions DO NOT need to follow this syntax, this is just an example):
b = IntVar.new(:b, (0..4).to_a)
c = IntVar.new(:c, (0..4).to_a)
con1 = a < b #Create constraints on the problem.
con2 = a + b == c
prob = Problem.new(con1, con2) #Create a problem with the constraints
solution = prob.solve #Find a solution
p solution
There are many solutions. It could return any (or all) of the following:
{:a => 0, :b => 2, :c => 2}
{:a => 0, :b => 3, :c => 3}
{:a => 0, :b => 4, :c => 4}
{:a => 1, :b => 2, :c => 3}
{:a => 1, :b => 3, :c => 4}
Another example would be to solve the magic square:
MAX = SIDE**2
SUM = (MAX*(MAX+1))/(2*SIDE)
square = Array.new(SIDE) do |x|
Array.new(SIDE) {|y| IntVar.new("#{x},#{y}", (1..MAX).to_a ) }
end
cons = []
zero = IntVar.new(:zero, [0])
SIDE.times do |row|
ÊÊÊ sum = zero
ÊÊÊ SIDE.times {|col| sum += square[col][row] }
ÊÊÊ cons << sum == SUM
end
SIDE.times do |col|
ÊÊÊ sum = zero
ÊÊÊ SIDE.times {|row| sum += square[col][row] }
ÊÊÊ cons << sum == SUM
end
#A constraint to ensure no two variables have the same value in a solution.
cons << AllDistinct.new(*square.flatten)
prob = Problem.new(*cons)
solution = prob.solve
p solution
There are many problems that can be solved through constraint programming (even some past quizzes): gift exchanges, sudoku, magic squares, N queens, cryptoarithmetics, scheduling problems, etc... So be creative here. Pick a simple problem to solve with your Constraint Programming Engine.
Good luck!
For more information see:
On-line Guide to Constraint Programming
and:
Quiz Summary
Constraint processing is a form of declarative programming which, in the words of Dave Burt, "...allows you to find solutions to mathematical problems by stating the problem rather than the steps to the solution." As indicated in the quiz, this can be used to solve all manner of problems without the programmer needing to find clever algorithms for each one.
Generally, satisfying constraints will involve some form of backtracking search. We can try some values and then back up to make different choices when the conditions of the problem begin failing. Jim Weirich's mystical amb.rb library handles the back up with continuations, so let's see if we can make some sense of that. Here's Jim's solution to the trivial quiz example:
A = Amb.new
begin
a = A.choose(*(0..4))
b = A.choose(*(0..4))
c = A.choose(*(0..4))
A.assert a < b
A.assert a + b == c
puts "a=#{a}, b=#{b}, c=#{c}"
A.failure
rescue Amb::ExhaustedError
puts "No More Solutions"
end
Running that gives the expected results:
a=0, b=1, c=1
a=0, b=2, c=2
a=0, b=3, c=3
a=0, b=4, c=4
a=1, b=2, c=3
a=1, b=3, c=4
No More Solutions
Let's change the program ever so slightly though, so we can watch it work. Here's the same code, with a bunch of debugging statements added:
A = Amb.new
begin
a = A.choose(*(0..4))
puts "a=#{a}" if $DEBUG
b = A.choose(*(0..4))
puts "b=#{b}" if $DEBUG
c = A.choose(*(0..4))
puts "c=#{c}" if $DEBUG
puts 'Asserting a < b...' if $DEBUG
A.assert a < b
puts 'Asserting a + b == c...' if $DEBUG
A.assert a + b == c
puts "a=#{a}, b=#{b}, c=#{c}"
puts 'Forcing failure to search for the next solution...' if $DEBUG
A.failure
rescue Amb::ExhaustedError
puts "No More Solutions"
end
Now, if we run that with Ruby's -d switch, we learn a lot more:
a=0
b=0
c=0
Asserting a < b...
c=1
Asserting a < b...
c=2
Asserting a < b...
c=3
Asserting a < b...
c=4
Asserting a < b...
b=1
c=0
Asserting a < b...
Asserting a + b == c...
c=1
Asserting a < b...
Asserting a + b == c...
a=0, b=1, c=1
Forcing failure to search for the next solution...
c=2
...
Notice that initially a, b, and c all equal the first choice. When we get to the point of asserting that a < b, the program magically backs up and begins trying different choices for c. It runs through all of those choices, but none of them will satisfy a condition involving a and b. The program is then forced to back up again, but this time to try new choices for b. The first new choice finally satisfies a < b so c is set back to the first option of 0 and we get to move on. Asserting a + b == c triggers a final retry for c and then we have an actual solution that gets printed. At that point, a failure is triggered manually, so the search can continue for more solutions.
Seeing that work is almost mystical. The program leaps all over the place without a control structure in sight. How does it accomplish this? Continuations. It's time we look into amb.rb:
class ExhaustedError < RuntimeError; end
def initialize
@fail = proc { fail ExhaustedError, "amb tree exhausted" }
end
def choose(*choices)
prev_fail = @fail
callcc { |sk|
choices.each { |choice|
callcc { |fk|
@fail = proc {
@fail = prev_fail
fk.call(:fail)
}
if choice.respond_to? :call
sk.call(choice.call)
else
sk.call(choice)
end
}
}
@fail.call
}
end
def failure
choose
end
def assert(cond)
failure unless cond
end
end
Not much to it is there? Only one tricky method to resolve, but let's tackle the little stuff first. We can see that Amb creates a new error type to represent the search being exhausted and initialize() sets @fail to a Proc object that will throw this error.
Now skip down to assert(). That just checks the condition for true or false, and calls failure() if needed. failure() itself is just as simple. It's just another name for choose() with no arguments. Even choose() with no arguments is trivial. First it assigns prev_fail and steps into a continuation block, but neither of those are actually used in this case. There are no choices, so most of the method is just skipped. The only meaningful result of the call is to trigger the Proc object in @fail.
Now we are ready to tackle choose() with arguments, which is the source of the magic. Here's the method one more time, with some comments added by me:
def choose(*choices)
prev_fail = @fail
callcc { |sk|
choices.each { |choice|
callcc { |fk|
@fail = proc {
@fail = prev_fail
fk.call(:fail)
}
if choice.respond_to? :call # a feature not used in this example
sk.call(choice.call) # a feature not used in this example
else # a feature not used in this example
sk.call(choice)
end # a feature not used in this example
} # end fk: fk.call(...) will pick up execution on the next line
}
@fail.call
} # end sk: sk.call(arg) with return from the method the value of arg
end
# ...
As the comments indicate, you can safely forget about four lines of this method right off the bat. These are part of a clever, but not used in this example, feature.
Now, the sk continuation is the easier one to understand. When it is triggered, it will cause the method to return its call() argument. There's not really a lot of magic there, the continuation block is just the last statement in the method and we know that is always returned in Ruby. Furthermore, Contuation.call() always sets the value of the block to an argument, if provided. In other words, this is just used to exit from some nested constructs later in this method (similar to a labeled goto in some languages).
That leaves just one continuation between us and enlightenment. You can see that the fk continuation is used inside an each iterator for the choices. Each time a new choice is reached a continuation is generated.
The first thing that continuation block does is to change the value in @fail. When called, the new @fail will restore the previous value of @fail and then invoke the fk continuation. Remember, @fail is first set to an ExhaustedError, but because that keeps getting pushed down on this stack of Proc objects, it won't trigger until we have run out of continuations to try.
After that, the current choice is simply returned, via the sk continuation we have already discussed. Now, when the fk continuation is eventually triggered, execution will pick up right after this return. In other words, we will go to the next iteration for that set of choices, @fail will be reset, and the new choice returned. When we finally run out of choices, we will hit the @fail.call line, causing the code to back up and try another path. That's the magic that keeps the search going.
As always, all the solutions were educational and looking over them could really teach you some new tricks. My thanks to all who provided them and to Jim for taking us for a walk on the wild side with continuations.
Tomorrow's quiz will require a little cooperation from your fellow Rubyists to complete...
