# Constraint Processing

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 }

# 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

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

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.

# 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|
(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

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)

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.

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

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

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

kibi_lied = kibi != kibi_said

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

A.assert(
(parent1==:male).implies( (kibi_said == :male ) )
)

# true.

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

# 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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.