Generate and Test in Ruby

The Generate and Test algorithm (GT) is without comparison the simplest and most inefficient way of solving constraints. Actually, it's not useful for anything but very, very small problems. But it is serves as a nice little illustrating of the concept of constraint solving. Just for fun I wrote a very small GT constraint solver in Ruby the other day, that I decided sharing.

Here is a small toy problem for it to solve and a demonstration of how it works:

gt = GT.new
 
gt.add_var("a", 0..4)
gt.add_var("b", 0..4)
gt.add_var("c", 0..4)
 
gt.add_constraint("a % 3 == 0")
gt.add_constraint("b + a < c")
gt.add_constraint("c-a > b")
gt.solve

Running this code will print:

Solutions:
{"a"=>0, "b"=>0, "c"=>1}
{"a"=>0, "b"=>0, "c"=>2}
{"a"=>0, "b"=>0, "c"=>3}
{"a"=>0, "b"=>0, "c"=>4}
{"a"=>0, "b"=>1, "c"=>2}
{"a"=>0, "b"=>1, "c"=>3}
{"a"=>0, "b"=>1, "c"=>4}
{"a"=>0, "b"=>2, "c"=>3}
{"a"=>0, "b"=>2, "c"=>4}
{"a"=>0, "b"=>3, "c"=>4}
{"a"=>3, "b"=>0, "c"=>4}


The implementation:

class GT
  def initialize
    @variables = Hash.new
    @constraints = Array.new
  end
  
  def add_var(varname, domain)
      @variables[varname] = domain
  end
  
  def add_constraint(constraint)
    constraint.freeze
    @constraints << constraint
  end
  
  def generate
    gen(@variables, Hash.new,nil)
  end
  
  def gen(variables, partial_assignment, solutions)
    solutions = Array.new if solutions.nil?

    if variables.empty?
      if test(partial_assignment)
        solutions << partial_assignment.clone
      end
      return nil # termination
    end

    # pick the first available variable:
    vars = variables.clone
    var_name = variables.keys.first
    domain = vars[var_name] 
    vars.delete(var_name)
    
    # Loop over each variable in domain
    domain.each do |value|
      partial_assignment[var_name] = value
      gen(vars, partial_assignment, solutions)
    end
    solutions
  end
    
  def test(assignment)
    @constraints.each do |constraint|
      c = String.new(constraint)
      assignment.each do |key,val|
        c.gsub!(key,val.to_s)
      end
      result = instance_eval(c)
      return false if result == false
    end
  end
  
  def solve
    puts "Solutions:"
    solutions = generate
    solutions.each do |s|
      pp s
    end

  end
end

It is not useful for solving anything interesting though. I tried to make it solve the the send more money puzzle. But this poor algorithm searches it self to death in vain. It took so long, that it was never allowed to terminate...

[ "s", "e", "n", "d", "m", "o", "r", "n", "y" ].each { |var| gt.add_var(var, 0..9) }

gt.add_constraint("m != 0")
gt.add_constraint("s != 0")
gt.add_constraint("m < 3")
gt.add_constraint("(1000*s + 100*e + 10*n + d + 1000*m + 100*o + 10*r + e) == (10000*m + 1000*o + 100*n + 10*e + y)")  

gt.solve

Update:Also heck out amb