Module: Doku::SolvableWithDancingLinks

Included in:
Puzzle
Defined in:
lib/doku/solver.rb

Overview

This module is included into the Puzzle class to provide methods for solving the puzzles using the DancingLinks algorithm.

Defined Under Namespace

Classes: GroupAndGlyph, SquareAndGlyph

Instance Method Summary collapse

Instance Method Details

#each_solution {|solution| ... } ⇒ Object

This method lets you iterate over each solution. Each solution is a puzzle object of the same class such that solution.solution_for?(puzzle) is true.

Yields:

  • (solution) 


26
27
28
29
30
 
# File 'lib/doku/solver.rb', line 26

def each_solution
  to_link_matrix.each_exact_cover do |exact_cover|
    yield exact_cover_to_solution exact_cover
  end
end

#exact_cover_to_solution(exact_cover) ⇒ Puzzle

Converts an exact cover (an array of SquareAndGlyph objects) to a solution of the puzzle.

Returns:



57
58
59
60
61
62
63
64
 
# File 'lib/doku/solver.rb', line 57

def exact_cover_to_solution(exact_cover)
  solution = dup
  exact_cover.each do |sg|
    solution[sg.square] = sg.glyph
  end

  solution
end

#solutions ⇒ Enumerable

An enumerator for all the solutions to the puzzle.

Returns:

  • (Enumerable) 


17
18
19
 
# File 'lib/doku/solver.rb', line 17

def solutions
  enum_for :each_solution
end

#solve ⇒ Puzzle

Returns the first solution found by the Dancing Links algorithm, or nil if there is no solution.

Returns:



11
12
13
 
# File 'lib/doku/solver.rb', line 11

def solve
  solutions.first
end

#to_link_matrix ⇒ DancingLinks::LinkMatrix

Returns a DancingLinks::LinkMatrix that represents this puzzle. Every row is a SquareAndGlyph object representing a choice to assign a certain glyph to a certain square. Every column is a GroupAndGlyph object representing the requirements that needs to be satisfied (every group must have exactly one of each glyph assigned to a square in the group).

Returns:



39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
# File 'lib/doku/solver.rb', line 39

def to_link_matrix
  # Create the link matrix.  This is a generic matrix
  # that does not take in to account the state of this instance.
  sm = DancingLinks::LinkMatrix.from_sets sets_for_exact_cover_problem
  
  # Take into account the state of this instance
  # by "choosing" rows.  This removes them from the matrix
  # by covering all the columns they touch.
  each do |square, glyph|
    sm.row(SquareAndGlyph.new(square,glyph)).choose
  end

  sm
end