# Constraint Processing (#70)

**URL:** <https://www.ruby-forum.com/t/constraint-processing-70/54628>\
**Category:** Ruby\
**Created:** [March 10, 2006, 2:51pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628 "2006-03-10T14:51:32Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 10, 2006, 2:51pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/1 "2006-03-10T14:51:32Z")

</div>

The three rules of Ruby Q.:

1. Please do not post any solutions or spoiler discussion for this quiz  
until  
48 hours have passed from the time on this message.

2. Support Ruby Q. by submitting ideas as often as you can:

[http://www.rubyquiz.com/](http://www.rubyquiz.com/)

1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps  
everyone  
on Ruby T. follow the discussion.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

by Jay A.

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):

```
a = IntVar.new(:a, (0..4).to_a) #Set up the variables and their 

```

domains.  
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 => 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}

```

Another example would be to solve the magic square:

```
SIDE = 3
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:

```
http://ktiml.mff.cuni.cz/~bartak/constraints/

```

and:

```
http://en.wikipedia.org/wiki/Constraint_programming

```

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 15, 2006, 3:10am UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/2 "2006-03-15T03:10:46Z")

</div>

Hi,

Thanks for another quiz. I read it and thought “that looks difficult and  
ugly”, but I had a little spare time, and, to my own surprise, was able  
to  
solve it rather quickly.

My naive solution just makes big nested loops over the domains of all  
the  
variables, so it’s not going to solve a sudoku this century, but you  
wouldn’t have to change the constraint code to speed it up - the engine  
can  
be fixed keeping the same interface.

The interface is DSP-ish and blocky as seems to be the fashion in Ruby  
these  
days.

Here’s N-Queens (n=4 so it works with my naive constraint processor):  
[http://www.dave.burt.id.au/ruby/constraints/nqueens.rb](http://www.dave.burt.id.au/ruby/constraints/nqueens.rb)

And here’s the thing itself:  
[http://www.dave.burt.id.au/ruby/constraints/constraint\_processor.rb](http://www.dave.burt.id.au/ruby/constraints/constraint_processor.rb)

Cheers,  
Dave

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 13, 2006, 11:15pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/3 "2006-03-13T23:15:13Z")

</div>

Here is my own solution to this week’s Ruby Q… I built a simple  
constraint library and used it to solve a sudoku puzzle. First the  
library (constraint.rb):

#!/usr/local/bin/ruby -w

class Problem  
def initialize  
@vars = Hash.new { |vars, name| vars[name] = Array.new }  
@rules = Hash.new { |rules, var| rules[var] = Array.new }

```
 yield self if block_given?

```

end

def var( name, \*choices )  
if choices.empty?  
values = @vars[name]  
values.size == 1 ? values.first : values  
else  
@vars[name].push(\*choices)  
end  
end

def rule( name, &test )  
@rules[name] \<\< test  
end

def solve  
loop do  
changed = false  
@vars.each do |name, choices|  
next if choices.size \< 2

```
     failures = choices.select do |choice|
       @rules[name].any? { |rule| !rule[choice] }
     end
     unless failures.empty?
       @vars[name] -= failures
       changed = true
     end
   end

   break unless changed
 end

 self

```

end  
end

def problem( &init )  
Problem.new(&init).solve  
end

**END**

And here is my sudoku solver (sudoku.rb), using that library:

#!/usr/local/bin/ruby -w

require “constraint”

# sudoku conveniences

indices = (0…8).to\_a  
boxes = Hash.new  
[(0…2), (3…5), (6…8)].each do |across|  
[(0…2), (3…5), (6…8)].each do |down|  
squares = across.map { |x| down.map { |y| “#{x}#{y}” } }.flatten  
squares.each { |square| boxes[square] = squares - [square] }  
end  
end

solution = problem do |prob|

# read puzzle, setting problem variables from data

(ARGV.empty? ? DATA : ARGF).each\_with\_index do |line, y|  
line.split.each\_with\_index do |square, x|  
prob.var("#{x}#{y}", \*(square =~ /\d/ ? [square.to\_i] : (1…9)))  
end  
end

# apply the rules of the game

indices.each do |x|  
indices.each do |y|  
col = (indices - [y]).map { |c| “#{x}#{c}” } # other cells in  
column  
row = (indices - [x]).map { |r| “#{r}#{y}” } # other cells in  
row  
box = boxes["#{x}#{y}"] # other cells in  
box  
[col, row, box].each do |set| # set rules requiring a cell to  
be unique  
prob.rule("#{x}#{y}") { |n| !set.map { |s| prob.var  
(s) }.include?(n) }  
end  
end  
end  
end

# pretty print the results

puts “+#{’-------+’ \* 3}”  
indices.each do |y|  
print “| "  
indices.each do |x|  
print “#{solution.var(”#{x}#{y}”).inspect} "  
print "| " if [2, 5].include? x  
end  
puts “|”  
puts “+#{’-------+’ \* 3}” if [2, 5, 8].include? y  
end

**END**  
7 \_ 1 \_ \_ \_ 3 \_ 5  
\_ 8 \_ 1 \_ 5 \_ 6 \_  
2 \_ \_ \_ \_ \_ \_ \_ 9  
\_ \_ 6 5 \_ 1 2 \_ \_  
\_ 3 \_ \_ \_ \_ \_ 1 \_  
\_ \_ 8 3 \_ 4 9 \_ \_  
9 \_ \_ \_ \_ \_ \_ \_ 8  
\_ 2 \_ 6 \_ 9 \_ 4 \_  
6 \_ 5 \_ \_ \_ 7 \_ 1

Running that on the included puzzle produces the following output:

±------±------±------+  
| 7 6 1 | 9 4 2 | 3 8 5 |  
| 3 8 9 | 1 7 5 | 4 6 2 |  
| 2 5 4 | 8 6 3 | 1 7 9 |  
±------±------±------+  
| 4 9 6 | 5 8 1 | 2 3 7 |  
| 5 3 2 | 7 9 6 | 8 1 4 |  
| 1 7 8 | 3 2 4 | 9 5 6 |  
±------±------±------+  
| 9 1 3 | 4 5 7 | 6 2 8 |  
| 8 2 7 | 6 1 9 | 5 4 3 |  
| 6 4 5 | 2 3 8 | 7 9 1 |  
±------±------±------+

Thanks for the quiz, Jav. I learned a lot!

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 16, 2006, 11:04am UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/4 "2006-03-16T11:04:54Z")

</div>

Hi

Here is my CSP language. I have actually been doing this for a class,  
so I got an extra week to work on it. As test cases, I have been  
modeling typical CSP problems so right now, I can do cryptarthemtic,  
sudoku, mastermind, map coloring, and the zebra problem.

I use forward checking with the MRV heuristic and the variable with the  
most constraints heuristic for tie breaking. I have also been working  
on a domain specific language that uses my CSP library. Some of the  
test cases use the language and some of them use the library.

The language uses generic variables and requires user defined domain  
constricting functions for non-trival constraints.

I would love some feedback on what I have done so far, including the  
syntax of the domain language and methods for the library. I plan to  
put the library on RubyForge at the end of the class.

Here is the link to the files needed to try it out:  
[http://reducto.case.edu/projects/team2/attachment/wiki/FileDump/CSP.zip?format=raw](http://reducto.case.edu/projects/team2/attachment/wiki/FileDump/CSP.zip?format=raw)

Chris Parker

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 16, 2006, 3:25pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/5 "2006-03-16T15:25:31Z")

</div>

On Mar 16, 2006, at 7:20 AM, Jim W. wrote:

> I’ve been having a lot of fun with this quiz. Pit C. sent me a  
> improved version of Amb that is more “Rubyish” and much easier to read  
> (my original was a direct translation of the scheme version).

Oh sure, you would do that after I summarized the trickier version. 😉

> # Make a choice amoung a set of discrete values.
> 
> def choose(\*choices)  
> choices.each { |choice|  
> callcc { |fk|  
> @back \<\< fk  
> return choice  
> }  
> }  
> failure  
> end

I tried to eliminate the outer continuation when I was summarizing,  
convinced it wasn’t needed. My attempt wasn’t successful though. :  
( It’s good to know I wasn’t completely wrong.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 16, 2006, 3:31pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/6 "2006-03-16T15:31:42Z")

</div>

On Mar 16, 2006, at 4:03 AM, Chris Parker wrote:

> Here is my CSP language. I have actually been doing this for a class,  
> so I got an extra week to work on it.

This is a great glimpse at a more robust solution. Thanks for  
sending it in!

> As test cases, I have been  
> modeling typical CSP problems so right now, I can do cryptarthemtic,  
> sudoku, mastermind, map coloring, and the zebra problem.

Ooo, I liked the Mastermind example. We need to do that as a Ruby  
Quiz at some point…

James Edward G. II

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 16, 2006, 2:19pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/7 "2006-03-16T14:19:54Z")

</div>

I’ve been having a lot of fun with this quiz. Pit C. sent me a  
improved version of Amb that is more “Rubyish” and much easier to read  
(my original was a direct translation of the scheme version). I’ve  
added comments and a bit of polish to his cleanup, so here’s the new and  
improved version of Amb along with another puzzle (just for fun).

## – BEGIN AMB

#!/usr/bin/env ruby

# Copyright 2006 by Jim W. (removed\_email\_address@domain.invalid). All rights

reserved.

# Permission is granted for use, modification and distribution as

# long as the above copyright notice is included.

# Amb is an ambiguous choice maker. You can ask an Amb object to

# select from a discrete list of choices, and then specify a set of

# constraints on those choices. After the constraints have been

# specified, you are guaranteed that the choices made earlier by amb

# will obey the constraints.

# 

# For example, consider the following code:

# 

# amb = Amb.new

# x = amb.choose(1,2,3,4)

# 

# At this point, amb may have chosen any of the four numbers (1

# through 4) to be assigned to x. But, now we can assert some

# conditions:

# 

# amb.assert (x % 2) == 0

# 

# This asserts that x must be even, so we know that the choice made by

# amb will be either 2 or 4. Next we assert:

# 

# amb.assert x \>= 3

# 

# This further constrains our choice to 4.

# 

# puts x # prints ‘4’

# 

# Amb works by saving a contination at each choice point and

# backtracking to previousl choices if the contraints are not

# satisfied. In actual terms, the choice reconsidered and all the

# code following the choice is re-run after failed assertion.

# 

# You can print out all the solutions by printing the solution and

# then explicitly failing to force another choice. For example:

# 

# amb = Amb.new

# x = Amb.choose(\*(1…10))

# y = Amb.choose(\*(1…10))

# amb.assert x + y == 15

# 

# puts “x = #{x}, y = #{y}”

# 

# amb.failure

# 

# The above code will print all the solutions to the equation x + y ==

# 15 where x and y are integers between 1 and 10.

# 

# The Amb class has two convience functions, solve and solve\_all for

# encapsulating the use of Amb.

# 

# This example finds the first solution to a set of constraints:

# 

# Amb.solve do |amb|

# x = amb.choose(1,2,3,4)

# amb.assert (x % 2) == 0

# puts x

# end

# 

# This example finds all the solutions to a set of constraints:

# 

# Amb.solve\_all do |amb|

# x = amb.choose(1,2,3,4)

# amb.assert (x % 2) == 0

# puts x

# end

# 

class Amb  
class ExhaustedError \< RuntimeError; end

# Initialize the ambiguity chooser.

def initialize  
@back = [  
lambda { fail ExhaustedError, “amb tree exhausted” }  
]  
end

# Make a choice amoung a set of discrete values.

def choose(\*choices)  
choices.each { |choice|  
callcc { |fk|  
@back \<\< fk  
return choice  
}  
}  
failure  
end

# Unconditional failure of a constraint, causing the last choice to

# be retried. This is equivalent to saying

# `assert(false).`

def failure  
@back.pop.call  
end

# Assert the given condition is true. If the condition is false,

# cause a failure and retry the last choice.

def assert(cond)  
failure unless cond  
end

# Report the given failure message. This is called by solve in the

# event that no solutions are found, and by +solve\_all+ when no more

# solutions are to be found. Report will simply display the message

# to standard output, but you may override this method in a derived

# class if you need different behavior.

def report(failure\_message)  
puts failure\_message  
end

# Class convenience method to search for the first solution to the

# constraints.

def Amb.solve(failure\_message=“No Solution”)  
amb = self.new  
yield(amb)  
rescue Amb::ExhaustedError =\> ex  
amb.report(failure\_message)  
end

# Class convenience method to search for all the solutions to the

# constraints.

## def Amb.solve\_all(failure\_message=“No More Solutions”) amb = self.new yield(amb) amb.failure rescue Amb::ExhaustedError =\> ex amb.report(failure\_message) end end – END AMB

And a new puzzle to go along with the new version of Amb:

## – BEGIN PUZZLE

#!/usr/bin/env ruby

# Two thieves have being working together for years. Nobody knows

# their identities, but one is known to be a Liar and the other a

# Knave. The local sheriff gets a tip that the bandits are about to

# commit another crime. When the sheriff arrives at the seen of the

# crime, he finds three men, A, B, and C. C has been stabbed with a

# dagger. He cries out, “A stabbed me” before anybody can say anything

# else; then, he falls down dead from the stabbing.

# 

# Not sure which of the three men are the crooks, the sheriff takes

# the two suspects to the jail and interrogates them. He gets the

# following information.

# 

# A’s statements:

# 1. B is one of the crooks.

# 2. B?s second statement is true.

# 3. C was telling the truth.

# 

# B’s statements:

# 1. A killed the other guy.

# 2. C was killed by one of the thieves.

# 3. C?s next statement would have been a lie.

# 

# C’s statement:

# 1. A stabbed me.

# 

# The sheriff knows that the murderer is among these three people. Who

# should the sheriff arrest for killing C?

# 

# NOTE: Liars always lie, knights always tell the truth and knaves

# strictly alternate between truth and lies.

require ‘amb’

# Some helper methods for logic

class Object  
def implies(bool)  
self ? bool : true  
end  
def xor(bool)  
self ? !bool : bool  
end  
end

# True if the given list of boolean values alternate between true and

# false.

def alternating(\*bools)  
expected = bools.first  
bools.each do |item|  
if item != expected  
return false  
end  
expected = !expected  
end  
true  
end

# A person class to keep track of the information about a single

# person in our puzzle.

class Person  
attr\_reader :name, :type, :murderer, :thief  
attr\_accessor :statements

def initialize(amb, name)  
@name = name  
@type = amb.choose(:liar, :knave, :knight)  
@murderer = amb.choose(true, false)  
@thief = amb.choose(true, false)  
@statements = []  
end

def to\_s  
“#{name} is a #{type} " +  
(thief ? “and a thief.” : “but not a thief.”) +  
(murderer ? " He is also the murderer.” : “”)  
end  
end

# Some lists used to do collective assertions.

people = Array.new(3)  
thieves = Array.new(2)

# Find all the solutions.

Amb.solve\_all do |amb|  
count = 0

# Create the three people in our puzzle.

a = Person.new(amb, “A”)  
b = Person.new(amb, “B”)  
c = Person.new(amb, “C”)  
people = [a, b, c]

# Basic assertions about the thieves.

thieves = people.select { |p| p.thief }  
amb.assert thieves.size == 2 # Only two thieves  
amb.assert thieves.collect { |p| # One is a knave, the other a liar  
p.type.to\_s  
}.sort == [“knave”, “liar”]

# Basic assertions about the murderer.

amb.assert people.select { |p| # There is only one murderer  
p.murderer  
}.size == 1  
murderer = people.find { |p| p.murderer }  
amb.assert ! c.murderer # No suicides

# Create the logic statements of each of the people involved. Note

# we are just creating them here. We won’t assert the truth of them

# until a bit later.

c1 = a.murderer # A stabbed me  
c2 = case c.type # (hypothetical next statement)  
when :knight  
false  
when :liar  
true  
when :knave  
!c1  
end  
c.statements = [c1, c2]

b1 = a.murderer # A killed the other guy  
b2 = murderer.thief # C was killed by one of the thieves  
b3 = ! c2 # C’s next statement would have been  
true  
b.statements = [b1, b2, b3]

a1 = b.thief # B is one of the crooks  
a2 = b2 # B’s second statement is true  
a3 = c1 # C was telling the truth.  
a.statements = [a1, a2, a3]

# Now we make assertions on the truthfulness of each of persons

# statements based on whether they are a Knight, a Knave or a Liar.

people.each do |p|  
amb.assert(  
(p.type == :knight).implies(  
p.statements.all? { |s| s }  
))

```
amb.assert(
  (p.type == :liar).implies(
    p.statements.all? { |s| !s }
    ))

amb.assert(
  (p.type == :knave).implies(
    alternating(*p.statements)
    ))

```

end

# Now we print out the solution.

## count += 1 puts “Solution #{count}:” people.each do |p| puts p end puts end – END PUZZLE

– Jim W.

---

<div class="post-metadata">

**Author:** ![bbazzarrakk](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/47e85d/32.png) [@bbazzarrakk](https://www.ruby-forum.com/u/bbazzarrakk)\
**Post date:** [March 16, 2006, 3:42pm UTC](https://www.ruby-forum.com/t/constraint-processing-70/54628/8 "2006-03-16T15:42:00Z")

</div>

James G. wrote:

> Oh sure, you would do that after I summarized the trickier version. 😉

😉

> I tried to eliminate the outer continuation when I was summarizing,  
> convinced it wasn’t needed. My attempt wasn’t successful though. :  
> ( It’s good to know I wasn’t completely wrong.

Yes, the new version is SO much easier on the eyes. Eliminating the  
extra continuation not only makes it easier to read, but a bit faster as  
well. The other simplification is that the original version supported  
delayed choices, i.e. passing in a lambda as a choice where that lambda  
wouldn’t get evaluated until the choice was needed. Although a cool  
idea, I don’t think I ever used it in any of the puzzles. So, it was  
extra baggage that wasn’t really needed.

–  
– Jim W.