Class: CSP::Algorithms::Backtracking

Inherits:
Object
  • Object
show all
Extended by:
Forwardable
Defined in:
lib/csp/algorithms/backtracking.rb

Constant Summary collapse

ORDERING_ALGORITHM = 
Ordering::NoOrder
FILTERING_ALGORITHM = 
Filtering::NoFilter
LOOKAHEAD_ALGORITHM = 
Lookahead::NoAlgorithm

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(problem:, ordering_algorithm: nil, filtering_algorithm: nil, lookahead_algorithm: nil, max_solutions: 1) ⇒ Backtracking

Returns a new instance of Backtracking.



19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
# File 'lib/csp/algorithms/backtracking.rb', line 19

def initialize(
  problem:,
  ordering_algorithm: nil,
  filtering_algorithm: nil,
  lookahead_algorithm: nil,
  max_solutions: 1
)
  @problem = problem
  @ordering_algorithm = ordering_algorithm || ORDERING_ALGORITHM.new(problem)
  @filtering_algorithm = filtering_algorithm || FILTERING_ALGORITHM.new(problem)
  @lookahead_algorithm = lookahead_algorithm || LOOKAHEAD_ALGORITHM.new(problem)
  @max_solutions = max_solutions
  @solutions = []
end

Instance Attribute Details

#filtering_algorithm ⇒ Object (readonly)

Returns the value of attribute filtering_algorithm.



14
15
16
 
# File 'lib/csp/algorithms/backtracking.rb', line 14

def filtering_algorithm
  @filtering_algorithm
end

#lookahead_algorithm ⇒ Object (readonly)

Returns the value of attribute lookahead_algorithm.



14
15
16
 
# File 'lib/csp/algorithms/backtracking.rb', line 14

def lookahead_algorithm
  @lookahead_algorithm
end

#max_solutions ⇒ Object (readonly)

Returns the value of attribute max_solutions.



14
15
16
 
# File 'lib/csp/algorithms/backtracking.rb', line 14

def max_solutions
  @max_solutions
end

#ordering_algorithm ⇒ Object (readonly)

Returns the value of attribute ordering_algorithm.



14
15
16
 
# File 'lib/csp/algorithms/backtracking.rb', line 14

def ordering_algorithm
  @ordering_algorithm
end

#problem ⇒ Object (readonly)

Returns the value of attribute problem.



14
15
16
 
# File 'lib/csp/algorithms/backtracking.rb', line 14

def problem
  @problem
end

#solutions ⇒ Object (readonly)

Returns the value of attribute solutions.



14
15
16
 
# File 'lib/csp/algorithms/backtracking.rb', line 14

def solutions
  @solutions
end

Instance Method Details

#backtracking(assignment = {}) ⇒ Object 



34
35
36
 
# File 'lib/csp/algorithms/backtracking.rb', line 34

def backtracking(assignment = {})
  backtracking_recursion(assignment, problem_domains)
end

#consistent?(variable, assignment) ⇒ Boolean

Returns:

  • (Boolean) 


38
39
40
41
42
 
# File 'lib/csp/algorithms/backtracking.rb', line 38

def consistent?(variable, assignment)
  constraints[variable].all? do |constraint|
    constraint.satisfies?(assignment)
  end
end