class CSP::Solver::Problem

You initialize a problem, set its variables and constraints, then can call `solve` on it.

Public Class Methods

new() click to toggle source
# File lib/csp/solver.rb, line 12
def initialize
  @vars = {}
  @gen_prefix = '__gen__'

  @unary_constraints = Hash.new { |h, k| h[k] = [] }
  @binary_constraints = Hash.new { |h, k| h[k] = [] }
end

Public Instance Methods

assign(hash) click to toggle source
# File lib/csp/solver.rb, line 57
def assign(hash)
  hash.each { |x, v| @vars[x] = [v] }
end
constrain(*vars, &pred) click to toggle source
# File lib/csp/solver.rb, line 61
def constrain(*vars, &pred)
  case vars.length
  when 1
    unary_constrain(vars[0], &pred)
  when 2
    binary_constrain(vars[0], vars[1], &pred)
  else
    nary_constrain(vars, &pred)
  end
end
solve(domains = @vars) click to toggle source

backtracking algorithm with interleaved local constraint propagation

# File lib/csp/solver.rb, line 21
def solve(domains = @vars)
  # deep-copy domains to prevent changes from "leaking" to outside
  domains = domains.each_with_object({}) { |(k, v), ds| ds[k] = v.dup; ds }

  return false unless ac3(domains)

  if domains.values.all? { |dom| dom.size == 1 }
    return domains.each_with_object({}) do |(k, v), sol|
      sol[k] = v[0] unless k.is_a?(String) && k.start_with?(@gen_prefix)
      sol
    end
  end

  var = domains.select { |_var, dom| dom.size > 1 }.keys.sort_by { |k| domains[k].size }.first
  dom = domains[var]

  dom.each do |value|
    domains[var] = [value]

    result = solve(domains)
    return result if result
  end

  domains[var] = dom

  false
end
var(id, domain) click to toggle source
# File lib/csp/solver.rb, line 49
def var(id, domain)
  @vars[id] = domain.to_a
end
vars(ids, domain) click to toggle source
# File lib/csp/solver.rb, line 53
def vars(ids, domain)
  ids.each { |id| var(id, domain.dup) }
end

Private Instance Methods

ac3(vars) click to toggle source
# File lib/csp/solver.rb, line 74
def ac3(vars)
  vars.each do |var, domain|
    next unless @unary_constraints.key? var
    domain.reject! { |x| !@unary_constraints[var].all? { |c| c.call(x) } }
    return false if domain.empty?
  end

  worklist = @binary_constraints.keys

  until worklist.empty?
    x, y = worklist.shift
    reduced_domain = vars[x].reject! { |vx| !vars[y].any? { |vy| @binary_constraints[[x, y]].all? { |c| c.call(vx, vy) } } }
    unless reduced_domain.nil?
      return false if vars[x].empty?
      worklist |= @binary_constraints.keys.select { |k| k.include?(x) && !k.include?(y) }
    end
  end

  true
end
binary_constrain(x1, x2) { |v1, v2| ... } click to toggle source
# File lib/csp/solver.rb, line 101
def binary_constrain(x1, x2, &pred)
  raise "No variable #{x1}" unless @vars.key? x1
  raise "No variable #{x2}" unless @vars.key? x2

  @binary_constraints[[x1, x2]] << pred

  # note the swapped parameter order
  @binary_constraints[[x2, x1]] << proc { |v2, v1| yield(v1, v2) }
end
nary_constrain(vars) { |*tuple| ... } click to toggle source
# File lib/csp/solver.rb, line 111
def nary_constrain(vars)
  vars.each do |x|
    raise "No variable #{x}" unless @vars.key? x
  end

  # Reduce n-way constraint to binary constraints:
  # Generate auxiliary variable to serve as binary intermediary between all constrained variables.
  # This variable's full domain is the cartesian product of all constrained variables' domains,
  # but here we filter the domain to only the values that satisfy the constraint.
  head, *tail = vars.map { |x| @vars[x] }
  dom = head.product(*tail).select { |tuple| yield(*tuple) }
  gen_id = @gen_prefix + SecureRandom.uuid

  var(gen_id, dom)

  vars.each_with_index do |x, i|
    binary_constrain(x, gen_id) { |v, tuple| v == tuple[i] }
  end
end
unary_constrain(x, &pred) click to toggle source
# File lib/csp/solver.rb, line 95
def unary_constrain(x, &pred)
  raise "No variable #{x}" unless @vars.key? x

  @unary_constraints[x] << pred
end