comp.lang.ruby

Jonathan Sillito

3/14/2006 6:18:00 PM

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

http://sillito.c...

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


On 13-Mar-06, at 8:29 PM, Matthew Moss wrote:

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