module Doku::SolvableWithDancingLinks

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

Public Instance Methods

each_solution() { |exact_cover_to_solution exact_cover| ... } click to toggle source

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.

@yield [solution]

# 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) click to toggle source

Converts an exact cover (an array of {SquareAndGlyph} objects) to a solution of the puzzle. @return (Puzzle)

# 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() click to toggle source

An enumerator for all the solutions to the puzzle. @return (Enumerable)

# File lib/doku/solver.rb, line 17
def solutions
  enum_for :each_solution
end
solve() click to toggle source

@return (Puzzle) Returns the first solution found by the Dancing Links algorithm, or nil if there is no solution.

# File lib/doku/solver.rb, line 11
def solve
  solutions.first
end

Private Instance Methods

sets_for_exact_cover_problem() click to toggle source
# File lib/doku/solver.rb, line 68
def sets_for_exact_cover_problem
  sets = {}
  squares.each do |square|
    groups_with_square = groups.select { |g| g.include? square }
    
    glyphs.each do |glyph|
      sets[SquareAndGlyph.new(square, glyph)] = [square] +
        groups_with_square.collect do |group|
          GroupAndGlyph.new group, glyph
        end
    end
  end

  sets
end