From: Matthew Moss <matthew.moss.coder@...>
Date: 2006-03-14T13:29:01+09:00
Subject: [QUIZ.SOLUTION] 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 }

# 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