Class: CombinatorialPuzzleSolver::SolutionSpace
 Inherits:

Hash
 Object
 Hash
 CombinatorialPuzzleSolver::SolutionSpace
 Defined in:
 lib/combinatorial_puzzle_solver/solution_space.rb
Overview
A mapping between each identifier of a puzzle and their possible values.
Instance Attribute Summary (collapse)

 (Puzzle) puzzle
readonly
The Puzzle that this solution space is associated with.
Instance Method Summary (collapse)

 (SolutionSpace) initialize(puzzle)
constructor
Creates a solution space for a given puzzle.

 (Hash<Identifier,Object>) resolvable_from_constraints
A Hash of all identifiers that can be resolved by iterating possible values of each constraint.

 (true, false) resolve!(implications) {solution_space, identifier, value ... }
Resolves the given implications and the new implications they yield (including those resolved from constraints, if no implications are given) until no more identifiers can be resolved.

 (SolutionSpace) resolve_by_trial_and_error!
Iterates the possible values of unresolved identifiers and returns the solution space for the first attempt that yields a complete solution.

 (true, false) resolved?
True if all identifiers have been resolved.

 (Hash<Identifier,Object>) resolved_identifiers
A Hash of all identifiers that are resolved, mapped to the value they are resolved to.

 (SolutionSpace^{?}) try_resolve_with(identifier, value)
Creates a clone of the solution space and tries to solve it with the assumption that the given identifier has the given value.

 (Hash<Identifier,Possibilities>) unresolved_identifiers
The unresolved identifiers and their possible values.
Constructor Details
 (SolutionSpace) initialize(puzzle)
Creates a solution space for a given puzzle.
14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 14 def initialize(puzzle) if puzzle.is_a?(Puzzle) then @puzzle = puzzle @puzzle.identifiers.each{identifier self[identifier] = Possibilities.new(self, identifier) } select{identifier identifier.has_value? }.each{identifier, possibilities possibilities.dependent_identifiers_cannot_be!(identifier.value) } elsif puzzle.is_a?(SolutionSpace) puzzle.each{identifier, possibilities clone = Possibilities.new(self, identifier) clone.clear clone.concat(possibilities) self[identifier] = clone } @puzzle = puzzle.puzzle end end 
Instance Attribute Details
 (Puzzle) puzzle (readonly)
Returns the Puzzle that this solution space is associated with.
8 9 10 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 8 def puzzle @puzzle end 
Instance Method Details
 (Hash<Identifier,Object>) resolvable_from_constraints
Returns a Hash of all identifiers that can be resolved by iterating possible values of each constraint.
58 59 60 61 62 63 64 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 58 def resolvable_from_constraints resolvable=Hash.new @puzzle.constraints.each{constraint constraint.resolvable_identifiers(self, resolvable) } resolvable end 
 (true, false) resolve!(implications) {solution_space, identifier, value ... }
Resolves the given implications and the new implications they yield (including those resolved from constraints, if no implications are given) until no more identifiers can be resolved.
If the solution space does not become #resolved? by this, it is necessary to #resolve_by_trial_and_error! to find a complete solution.
If a block is given it will yield the solution space with the corresponding identifier and value before each time a resolution is made (Possibilities#must_be!), and it will abort unless the block returns true.
88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 88 def resolve!(implications) loop do resolvable = Hash.new implications.each{identifier, value if block_given? then return false unless yield(self, identifier, value) == true end self[identifier].must_be!(value, resolvable) } if resolvable.empty? then implications = resolvable_from_constraints else implications = resolvable end break if implications.empty? end resolved? end 
 (SolutionSpace) resolve_by_trial_and_error!
Iterates the possible values of unresolved identifiers and returns the solution space for the first attempt that yields a complete solution. It will return itself if it becomes resolved by eliminating the attempts that failed.
119 120 121 122 123 124 125 126 127 128 129 130 131 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 119 def resolve_by_trial_and_error! unresolved_identifiers.each{identifier, possibilities until possibilities.resolved? do maybe_value = possibilities.first maybe_solution = try_resolve_with(identifier, maybe_value) return maybe_solution unless maybe_solution.nil? resolve!(self[identifier].cannot_be!(maybe_value)) end } self end 
 (true, false) resolved?
Returns true if all identifiers have been resolved.
153 154 155 156 157 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 153 def resolved? all?{identifier,possibilities identifier.has_value?  possibilities.resolved? } end 
 (Hash<Identifier,Object>) resolved_identifiers
Returns a Hash of all identifiers that are resolved, mapped to the value they are resolved to.
37 38 39 40 41 42 43 44 45 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 37 def resolved_identifiers resolved = {} each{identifier, possibilities if !identifier.has_value? && possibilities.resolved? then resolved[identifier] = possibilities.first end } resolved end 
 (SolutionSpace^{?}) try_resolve_with(identifier, value)
Creates a clone of the solution space and tries to solve it with the assumption that the given identifier has the given value.
137 138 139 140 141 142 143 144 145 146 147 148 149 150 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 137 def try_resolve_with(identifier, value) possible_solution_space = SolutionSpace.new(self) assumption = {identifier => value} begin if possible_solution_space.resolve!(assumption) then return possible_solution_space else return possible_solution_space.resolve_by_trial_and_error! end rescue Inconsistency return nil end end 
 (Hash<Identifier,Possibilities>) unresolved_identifiers
Returns the unresolved identifiers and their possible values.
49 50 51 52 53 
# File 'lib/combinatorial_puzzle_solver/solution_space.rb', line 49 def unresolved_identifiers select{identifier, possibilities !identifier.has_value? && !possibilities.resolved? } end 