# Constraint Processing

**URL:** <https://www.ruby-forum.com/t/constraint-processing/54780>\
**Category:** Ruby\
**Created:** [March 14, 2006, 5:29am UTC](https://www.ruby-forum.com/t/constraint-processing/54780 "2006-03-14T05:29:27Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [March 14, 2006, 5:29am UTC](https://www.ruby-forum.com/t/constraint-processing/54780/1 "2006-03-14T05:29:27Z")

</div>

I had to give this a couple tries before I just broke down and went  
for what amounts to brute force. This solution can get slow pretty  
quickly; I’m sure there are some easy speedups (i.e. narrow the search  
space) that can be done, but I figured to put this up for now.

# Helpers

class Integer  
def even?  
(self % 2).zero?  
end  
end

class Symbol  
def \<=\> other  
self.to\_s \<=\> other.to\_s  
end  
end

# Constraint Solver class

class Problem  
def initialize(&block)  
@domain = {}  
@consts = Hash.new { [] }  
instance\_eval(&block)  
end

def variable(var, domain)  
raise ArgumentError, “Cannot specify variable #{var} more than  
once.” if @domain.has\_key?(var)  
@domain[var] = domain.to\_a  
end

def constrain(\*vars, &foo)  
raise ArgumentError, ‘Constraint requires at least one  
variable.’ if vars.size.zero?  
vars.each do |var|  
raise ArgumentError, “Unknown variable: #{var}” unless  
@domain.has\_key?(var)  
end  
@consts[vars] = @consts[vars] \<\< foo  
end

def solve  
# Separate constraint keys into unary and non-unary.  
unary, multi = @consts.keys.partition{ |vars| vars.size == 1 }

```
  # Process unary constraints first to narrow variable domains.
  unary.each do |vars|
     a = vars.first
     @consts[vars].each do |foo|
        @domain[a] = @domain[a].select { |d| foo.call(d) }
     end
  end

  # Build fully-expanded domain (i.e. across all variables).
  full = @domain.keys.map do |var|
     @domain[var].map do |val|
        { var => val }
     end
  end.inject do |m, n|
     m.map do |a|
        n.map do |b|
           a.merge(b)
        end
     end.flatten
  end

  # Process non-unary constraints on full domain.
  full.select do |d|
     multi.all? do |vars|
        @consts[vars].all? do |foo|
           foo.call( vars.map { |v| d[v] } )
        end
     end
  end

```

end  
end

# A simple example

problem = Problem.new do  
variable(:a, 0…10)  
variable(:b, 0…10)  
variable(:c, 0…10)

constrain(:a) { |a| a.even? }  
constrain(:a, :b) { |a, b| b == 2 \* a }  
constrain(:b, :c) { |b, c| c == b - 3 }  
end

puts “Simple example solutions:”  
problem.solve.each { |sol| p sol }

# Calculate some primes… The constraint problem actually finds

# the non-primes, which we remove from our range afterward to get

# the primes.

problem = Problem.new do  
variable(:a, 2…25)  
variable(:b, 2…25)  
variable(:c, 2…50)

constrain(:a, :b) { |a, b| a \<= b }  
constrain(:a, :b, :c) { |a, b, c| a \* b == c }  
end

puts “The primes up to 50:”  
puts ((2…50).to\_a - problem.solve.map { |s| s[:c] }).join(", ")  
puts

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [March 14, 2006, 7:19pm UTC](https://www.ruby-forum.com/t/constraint-processing/54780/2 "2006-03-14T19:19:02Z")

</div>

I didn’t write this for the quiz, but here is a simple csp library  
written in ruby:

[http://sillito.ca/ruby-csp](http://sillito.ca/ruby-csp)

It has a few features to speed up solving including forward checking,  
dynamic variable ordering and support for specialized propagation,  
but it remains very basic. There is lots more that could be done with  
it, and I plan to release an update when I find the time. Feedback is  
definitely welcome.

Here is how the famous N-Queens problem can be modeled and solved  
with the library:

require ‘ai/csp’  
include AI::CSP

def problem(n)

```
 # variables are columns and values are rows, so assigning
 # the first variable the value 2 corresponds to placing a
 # queen on the board at col 0 and row 2.

 variables = (0...n).collect {|i|
     Variable.new(i, (0...n))
 }
 problem = Problem.new(variables)

 # None of the queens can share a row. AllDifferent is a
 # built in constraint type.
 problem.add_constraint(AllDifferent.new(*variables))

 # No pair of queens can be on the same diagonal.
 variables.each_with_index {|v1,i|
     variables[(i+1)..-1].each_with_index{ |v2,j|
         problem.add_constraint(v1, v2) { |row1,row2|
             (j+1) != (row1-row2).abs
         }
     }
 }

 problem

```

end

solver = Backtracking.new(true, FAIL\_FIRST)  
solver.each\_solution(problem(8)) { |solution|  
puts solution  
}

puts solver # prints some statistics

Cheers,  
Jonathan

---

<div class="post-metadata">

**Author:** ![mansfiem](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/fbc32d/32.png) [@mansfiem](https://www.ruby-forum.com/u/mansfiem)\
**Post date:** [March 14, 2006, 7:46pm UTC](https://www.ruby-forum.com/t/constraint-processing/54780/3 "2006-03-14T19:46:59Z")

</div>

Here’s some more puzzle solutions using Amb. This one is the one  
described in the “Learn Scheme in Fixnum days” online book (where I  
found the original Amb implementation). (see  
[http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html#node\_chap\_14](http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme-Z-H-16.html#node_chap_14))

However, this is not an exact transcription of the book’s logic, I was  
able to simplify a number of the assertions.

Enjoy!

– Jim W.

# The Kalotans are a tribe with a peculiar quirk. Their males always

# tell the truth. Their females never make two consecutive true

# statements, or two consecutive untrue statements.

# 

# An anthropologist (let’s call him Worf) has begun to study

# them. Worf does not yet know the Kalotan language. One day, he meets

# a Kalotan (heterosexual) couple and their child Kibi. Worf asks

# Kibi: ``Are you a boy?‘’ Kibi answers in Kalotan, which of course

# Worf doesn’t understand.

# 

# Worf turns to the parents (who know English) for explanation. One of

# them says: `Kibi said: `I am a boy.' '' The other adds: `Kibi is a

# girl. Kibi lied.‘’

# 

# Solve for the sex of the parents and Kibi.

require ‘amb’

# Some helper methods for logic

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

count = 0  
A = Amb.new

# Begin the solution

begin

# Kibi’s parents are either male or female, but must be distinct.

parent1 = A.choose(:male, :female)  
parent2 = A.choose(:male, :female)  
A.assert parent1 != parent2

# Kibi sex, and Kibi’s self description are separate facts

kibi = A.choose(:male, :female)  
kibi\_said = A.choose(:male, :female)

# We will capture whether kibi lied in a local variable. This will

# make some later logic conditions a bit easier. (Note: the Scheme

# implementation sets the kibi\_lied variable to a choice of true or

# false and then uses assertions to make all three variables

# consistent. This way however, is just so much easier.)

kibi\_lied = kibi != kibi\_said

# Now we look at what the parents said. If the first parent was

# male, then kibi must have described itself as male.

A.assert(  
(parent1==:male).implies( (kibi\_said == :male ) )  
)

# If the first parent is female, then there are no futher deductions

# to make. Their statement could either be true or false.

# If the second parent is male, then both its statements must be

# true.

A.assert( (parent2 == :male).implies( kibi==:female ))  
A.assert( (parent2 == :male).implies( kibi\_lied ))

# If the second parent is female, then the condition is more

# complex. In this case, one or the other of the parent 2’s

# statements are false, but not both are false. Let’s introduce

# some variables for statements 1 and 2 just to make this a bit

# clearer.

s1 = kibi\_lied  
s2 = (kibi == :female)

A.assert(  
(parent2 == :female).implies( (s1 && !s2).xor(!s1 && s2) )  
)

# Now just print out the solution.

count += 1  
puts “Solution #{count}”  
puts “The first parent is #{parent1}.”  
puts “The second parent is #{parent2}.”  
puts “Kibi is #{kibi}.”  
puts “Kibi said #{kibi\_said} and #{kibi\_lied ? ‘lied’ : ‘told the  
truth’}.”  
puts

A.failure # Force a search for another solution.

rescue Amb::ExhaustedError  
puts “No More Solutions”  
end