Class: CombinatorialPuzzleSolver::SolutionSpace

Inherits:
Hash
  • Object
show all
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)

Instance Method Summary (collapse)

Constructor Details

- (SolutionSpace) initialize(puzzle)

Creates a solution space for a given puzzle.

Parameters:

  • puzzle (Puzzle, SolutionSpace)

    the puzzle that this solution space is based on, or a clone if a SolutionSpace is given.

Specifications:

is a Hash mapping between identifiers and their possible values

creates a clone if another SolutionSpace is given as argument



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.

Returns:

  • (Puzzle)

    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.

Returns:

  • (Hash<Identifier,Object>)

    a Hash of all identifiers that can be resolved by iterating possible values of each constraint.

Specifications:

should return a Hash

should return the identifiers that can be resolved by constraints



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.

Parameters:

  • implications (Hash<Identifier,Object>)

    a mapping between identifiers and their assumed value.

Yield Parameters:

  • solution_space (SolutionSpace)

    the solution space in the state right before a resolution is made.

  • identifier (Identifier)

    an identifier that is resolved.

  • value (Object)

    the value the identifier is resolved to.

Yield Returns:

  • (true, nil)

    the resolution will abort unless the block returns true for each identifier that is resolved.

Returns:

  • (true, false)

    true if the solution space became completely resolved.

Raises:

  • (Inconsistency)

    if the solution space becomes inconsistent without any possible solution.

Specifications:

should return true if the solution space becomes resolved

should return false if the solution space is still not resolved

should raise Inconsistency if a solution is impossible

should yield solution space, identifier and value for every step

Given the 4x4 sudoku puzzle:

   |4  
1  |   
---+---
   |  3
  1|   

Yielded [2,4]=2.

   |4  
1  |  2
---+---
   |  3
  1|   

Yielded [4,3]=2.

   |4  
1  |  2
---+---
   |  3
  1|2  

Yielded [2,3]=3.

   |4  
1  |3 2
---+---
   |  3
  1|2  

Yielded [1,4]=1.

   |4 1
1  |3 2
---+---
   |  3
  1|2  

Yielded [4,4]=4.

   |4 1
1  |3 2
---+---
   |  3
  1|2 4

Yielded [3,3]=1.

   |4 1
1  |3 2
---+---
   |1 3
  1|2 4

Yielded [2,2]=4.

   |4 1
1 4|3 2
---+---
   |1 3
  1|2 4

Yielded [4,1]=3.

   |4 1
1 4|3 2
---+---
   |1 3
3 1|2 4

Yielded [3,2]=2.

   |4 1
1 4|3 2
---+---
  2|1 3
3 1|2 4

Yielded [1,1]=2.

2  |4 1
1 4|3 2
---+---
  2|1 3
3 1|2 4

Yielded [3,1]=4.

2  |4 1
1 4|3 2
---+---
4 2|1 3
3 1|2 4

Yielded [1,2]=3.

2 3|4 1
1 4|3 2
---+---
4 2|1 3
3 1|2 4


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.

Returns:

  • (SolutionSpace)

    a solution space that is completely resolved

Raises:

Specifications:

should return a completely resolved solution space if possible

should raise Inconsistency if no solution is possible



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.

Returns:

  • (true, false)

    true if all identifiers have been resolved.

Specifications:

should return true if the puzzle is completely resolved, false otherwise



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.

Returns:

  • (Hash<Identifier,Object>)

    a Hash of all identifiers that are resolved, mapped to the value they are resolved to.

Specifications:

should return a Hash

should return all identifiers that are resolved

should not include identifiers that have value



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.

Returns:

  • (SolutionSpace, nil)

    a solution space that is completely resolved, or nil if no complete solution was found.

Specifications:

should return SolutionSpace resolved with the the identifier and value

should return nil if the identifier and value makes it irresolvable.



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.

Returns:

Specifications:

should return a Hash

should return all 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