Class: CombinatorialPuzzleSolver::Puzzle

Inherits:
Object
  • Object
show all
Defined in:
lib/combinatorial_puzzle_solver/puzzle.rb

Overview

Base class for a combinatorial number-placement puzzle

Direct Known Subclasses

Sudoku

Instance Attribute Summary (collapse)

Instance Method Summary (collapse)

Constructor Details

- (Puzzle) initialize(identifier_count, symbols) {|identifiers| ... }

Creates a new puzzle.

Parameters:

  • identifier_count (Fixnum)

    The number of identifiers in this puzzle

  • symbols (Array)

    The possible values each identifier can have.

Yield Parameters:

  • identifiers (Array<Identifier>)

    the identifiers of this puzzle.

Yield Returns:

  • (Array<Constraint>)

    The initialized constraints

Specifications:

should fail unless the block returns Constraint(s)



25
26
27
28
29
30
31
32
33
34
35
36
37
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 25

def initialize(identifier_count, symbols, &constraint_block)

  @symbols = symbols.uniq
  @identifiers = Array.new(identifier_count) { Identifier.new(self) }

  fail "No block for initiating constraints given" unless block_given?
  @constraints = yield @identifiers

  fail "The constraint block returned 0 constraints" if @constraints.empty?
  unless @constraints.all?{|constraint| constraint.is_a?(Constraint)} then
    fail "The constraint block may only contain Constraint"
  end
end

Instance Attribute Details

- (Array<Constraint>) constraints (readonly)

Returns the constraints of this puzzle.

Returns:

  • (Array<Constraint>)

    the constraints of this puzzle.

Specifications:

should return an array of all the constraints



12
13
14
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 12

def constraints
  @constraints
end

- (Array<Identifier>) identifiers (readonly)

Returns the identifiers of this puzzle.

Returns:

  • (Array<Identifier>)

    the identifiers of this puzzle.

Specifications:

should return an array of all the identifiers



9
10
11
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 9

def identifiers
  @identifiers
end

- (Array) symbols (readonly)

Returns an array that contains all the possible values each identifier can have.

Returns:

  • (Array)

    an array that contains all the possible values each identifier can have.

Specifications:

should return an array of all the possible symbolsfor an identifier



16
17
18
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 16

def symbols
  @symbols
end

Instance Method Details

- (String) identifier_to_s(identifier)

Returns a string representation of an identifier, in the context of this puzzle.

Returns:

  • (String)

    a string representation of an identifier, in the context of this puzzle.



60
61
62
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 60

def identifier_to_s(identifier)
  "[#{identifiers.index(identifier)}]"
end

- (String) inspect

Returns identifiers and constraints as a string representation.

Returns:

  • (String)

    identifiers and constraints as a string representation.

See Also:



54
55
56
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 54

def inspect
  (@identifiers + @constraints).collect{|obj| obj.inspect }.join("\n")
end

- (String) inspect_identifier(identifier)

Returns a string representation of an identifier (including value), in the context of this puzzle.

Returns:

  • (String)

    a string representation of an identifier (including value), in the context of this puzzle.



66
67
68
69
70
71
72
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 66

def inspect_identifier(identifier)
  if identifier.has_value? then
    identifier_to_s(identifier) << "=#{identifier.value.to_s}"
  else
    identifier_to_s(identifier)
  end
end

- (true, false) resolve!(trial_and_error = true, steps = 0, output = {})

Resolves a puzzle while writing diagnostic output to given streams.

Parameters:

  • trial_and_error (Boolean) (defaults to: true)

    whether it should resort to trial and error if a complete solution cannot be resolved.

  • steps (Fixnum) (defaults to: 0)

    how many steps it will perform before aborting (or 0).

  • output (Hash) (defaults to: {})

    a collection of output streams for diagnostic purposes.

Returns:

  • (true, false)

    whether the puzzle was completely resolved or not.

Raises:

  • (Inconsistency)

    if the solution space becomes inconsistent without any possible solution.

Specifications:

should return true when puzzle is solvable

{  [ }  ]

should raise inconsistency when the puzzle is unsolvable

when :parsed_stream is given

should write the parsed input puzzle

when :steps_stream is given

should write each resolution step

when :puzzle_stream is given

should write the puzzle for each resolution step

when :result_stream is given

should write the resulting puzzle



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 91

def resolve!(trial_and_error=true, steps=0, output={})

  # print the parsed puzzle
  output[:parsed_stream].puts to_s << "\n\n" if output[:parsed_stream]

  step_count = 0

  solution = SolutionSpace.new(self)
  solution.resolve!(solution.resolved_identifiers){|x, identifier, value|

    # print the resolved step
    identifier.set!(value)
    output[:steps_stream].puts identifier.inspect if output[:steps_stream]

    # print the entire board
    output[:puzzle_stream].puts to_s << "\n\n" if output[:puzzle_stream]

    step_count += 1
    step_count != steps
  }

  # brute force with trial and error unless we only want the resolution steps
  brute_forced = solution.resolve_by_trial_and_error! if trial_and_error
  solution = brute_forced unless brute_forced.nil?

  # print the result
  set_resolved_identifiers!(solution)
  output[:result_stream].puts to_s << "\n\n" if output[:result_stream]

  solution.resolved?
end

- (SolutionSpace?) resolved_solution_space

Returns the resolved solution space for this puzzle, or nil if the puzzle doesn't have any solution.

Returns:

  • (SolutionSpace, nil)

    the resolved solution space for this puzzle, or nil if the puzzle doesn't have any solution.



41
42
43
44
45
46
47
48
49
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 41

def resolved_solution_space
  begin
    solution_space = SolutionSpace.new(self)
    solution_space.resolve!(solution_space.resolved_identifiers)
    return solution_space.resolve_by_trial_and_error!
  rescue Inconsistency
    nil
  end
end

- (Object) set_resolved_identifiers!(solution_space)

Sets all identifiers to the value they are resolved to.

Parameters:



76
77
78
79
80
# File 'lib/combinatorial_puzzle_solver/puzzle.rb', line 76

def set_resolved_identifiers!(solution_space)
  solution_space.resolved_identifiers.each{|identifier, value|
    identifier.set!(value)
  }
end