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

## No comments:

Post a Comment