Class: CSP::Solver::Problem
- Inherits:
-
Object
- Object
- CSP::Solver::Problem
- Includes:
- ConvenientConstraints
- Defined in:
- lib/csp/solver.rb
Overview
You initialize a problem, set its variables and constraints, then can call ‘solve` on it.
Instance Method Summary collapse
- #assign(hash) ⇒ Object
- #constrain(*vars, &pred) ⇒ Object
-
#initialize ⇒ Problem
constructor
A new instance of Problem.
-
#solve(domains = @vars) ⇒ Object
backtracking algorithm with interleaved local constraint propagation.
- #var(id, domain) ⇒ Object
- #vars(ids, domain) ⇒ Object
Methods included from ConvenientConstraints
#all_different, #all_pairs, #all_same
Constructor Details
#initialize ⇒ Problem
Returns a new instance of Problem.
12 13 14 15 16 17 18 |
# 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 |
Instance Method Details
#assign(hash) ⇒ Object
57 58 59 |
# File 'lib/csp/solver.rb', line 57 def assign(hash) hash.each { |x, v| @vars[x] = [v] } end |
#constrain(*vars, &pred) ⇒ Object
61 62 63 64 65 66 67 68 69 70 |
# 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) ⇒ Object
backtracking algorithm with interleaved local constraint propagation
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# 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) ⇒ Object
49 50 51 |
# File 'lib/csp/solver.rb', line 49 def var(id, domain) @vars[id] = domain.to_a end |
#vars(ids, domain) ⇒ Object
53 54 55 |
# File 'lib/csp/solver.rb', line 53 def vars(ids, domain) ids.each { |id| var(id, domain.dup) } end |