Class: Doku::Puzzle Abstract

Inherits:
Object
  • Object
show all
Includes:
SolvableWithDancingLinks
Defined in:
lib/doku/puzzle.rb

Overview

This class is abstract.

Use the Sudoku, Hexadoku, or Hexamurai subclasses or make a subclass to represent your own type of Sudoku-like puzzle.

This in abstract class for creating classes that represent Sudoku-like puzzles.

Every subclass of Puzzle represents a Sudoku-like puzzle consisting of a set of glyphs, a set of squares, and a set of groups of squares. For example, the Sudoku subclass represents the famous 9x9 puzzle, Sudoku.

Every instance of a subclass of Puzzle represents a particular state of that type of puzzle, i.e. a record of which glyph is assigned to each square.

Direct Known Subclasses

Hexadoku, Hexamurai, Sudoku

Class Attribute Summary collapse

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from SolvableWithDancingLinks

#each_solution, #exact_cover_to_solution, #solutions, #solve, #to_link_matrix

Constructor Details

#initialize(glyph_state = {}) ⇒ Puzzle

Creates a new instance of the puzzle.

where the keys are squares and the values are nil or glyphs in the context of this puzzle class. For example, this represents what numbers have been written in the boxes of a Sudoku puzzle.

Parameters:

  • glyph_state (Hash) (defaults to: {}) —

    The state of the puzzle, represented as a hash



38
39
40
41
42
 
# File 'lib/doku/puzzle.rb', line 38

def initialize(glyph_state = {})
  @glyph_state = {}
  # We initialize glyph_state this way so that the data gets validated.
  glyph_state.each { |square, glyph| self[square] = glyph }
end

Class Attribute Details

.glyphs ⇒ Array (readonly)

Returns an array of all the valid glyphs for this class of puzzle. A glyph can be any type of Ruby object, and it is meant to represent a symbol which can be drawn inside a square in a Sudoku-like puzzle.

For example, the glyphs for Sudoku are the Ruby integers 1, 2, 3, 4, 5, 6, 7, 8, and 9.

The glyphs, squares, and groups, are defined at the class level, in the subclasses of Doku::Puzzle.

Returns:

  • (Array) —

    Array of objects representing glyphs.



56
57
58
 
# File 'lib/doku/puzzle.rb', line 56

def glyphs
  @glyphs
end

.groups ⇒ Array (readonly)

Returns an array of all the groups for this class of puzzle. A group should be a Set object that contains some squares. A group represents a constraint on solutions to the puzzle: every glyph must appear exactly once in every group.

For example, the groups of the Sudoku class represent the nie columns, nine rows, and nine 3x3 boxes of Sudoku.

The glyphs, squares, and groups, are defined at the class level, in the subclasses of Doku::Puzzle.

Returns:

  • (Array) —

    Array of glyphs.



79
80
81
 
# File 'lib/doku/puzzle.rb', line 79

def groups
  @groups
end

.squares ⇒ Array (readonly)

Returns an array of all the valid squares in this class of puzzle. A square can be any type of Ruby object, and it is meant to represent a square in which glyphs are drawn in a Sudoku-like puzzle.

For example, there are 81 squares defined in the Sudoku class, one for each square on the 9x9 Sudoku grid.

The glyphs, squares, and groups, are defined at the class level, in the subclasses of Doku::Puzzle.

Returns:

  • (Array) —

    Array of objects representing squares.



67
68
69
 
# File 'lib/doku/puzzle.rb', line 67

def squares
  @squares
end

Instance Attribute Details

#glyph_state ⇒ Object (readonly)

A hash that associates squares to glyphs, representing the arrangement of glyphs in the puzzle.



30
31
32
 
# File 'lib/doku/puzzle.rb', line 30

def glyph_state
  @glyph_state
end

Instance Method Details

#==(puzzle) ⇒ Object

Same as #eql?.



148
149
150
 
# File 'lib/doku/puzzle.rb', line 148

def == (puzzle)
  eql? puzzle
end

#[](square) ⇒ Object

Gets the glyph assigned to the given square.

Parameters:

  • square —

    Must be one of the squares for this puzzle.

Returns:

  • The glyph that is assigned to the given square (one of the glyphs defined for this puzzle), or nil if no glyph is assigned.

Raises:

  • (IndexError) 


105
106
107
108
 
# File 'lib/doku/puzzle.rb', line 105

def [](square)
  raise IndexError, "Square not found in #{self.class.name}: #{square}." if !squares.include?(square)
  @glyph_state[square]
end

#[]=(square, glyph) ⇒ Object

Sets the glyph assigned to the given square.

Parameters:

  • square —

    Must be one of the squares for this puzzle.

  • glyph —

    Must be one of the glyphs for this puzzle, or nil.

Raises:

  • (IndexError) 


113
114
115
116
117
118
119
120
121
122
123
124
 
# File 'lib/doku/puzzle.rb', line 113

def []=(square, glyph)
  raise IndexError, "Square not found in #{self.class}: #{square}." if !squares.include?(square)
  raise ArgumentError, "Value must be a glyph in this puzzle or nil." if !glyph.nil? && !glyphs.include?(glyph)

  # Do NOT store nils as values in the hash, because we
  # don't want them to affect equality comparisons.
  if glyph == nil
    @glyph_state.delete square
  else
    @glyph_state[square] = glyph
  end
end

#each {|square, glyph| ... } ⇒ Object

This method allows you to iterate over every square that has a glyph assigned to it.

Yields:

  • (square, glyph)

Yield Parameters:

  • square —

    A square that has a glyph assigned to it.

  • glyph —

    The glyph that is assigned to the square.



132
133
134
 
# File 'lib/doku/puzzle.rb', line 132

def each(&block)
  @glyph_state.each(&block)
end

#eql?(puzzle) ⇒ Boolean

Two puzzles are equal if they have the same class and glyph assignments.

Returns:

  • (Boolean) —

    True if the two puzzles are equal.



143
144
145
 
# File 'lib/doku/puzzle.rb', line 143

def eql?(puzzle)
  self.class == puzzle.class and glyph_state == puzzle.glyph_state
end

#filled? ⇒ Boolean

Returns true if this puzzle is completely filled in, which means every square has a glyph assigned to it. For example, a Sudoku puzzle is considered to be filled after you have written a number in every box, regardless of whether the numbers obey the rules of Sudoku or not. See also #solution? and #solution_for?.

Returns:

  • (Boolean) 


176
177
178
 
# File 'lib/doku/puzzle.rb', line 176

def filled?
  squares.size == glyph_state.keys.size
end

#glyphs ⇒ Array

Shortcut for calling the glyphs class method.

Returns:

  • (Array) —

    Array of glyphs.



84
85
86
 
# File 'lib/doku/puzzle.rb', line 84

def glyphs
  self.class.glyphs
end

#groups ⇒ Array

Shortcut for calling the groups class method.

Returns:

  • (Array) —

    Array of groups.



96
97
98
 
# File 'lib/doku/puzzle.rb', line 96

def groups
  self.class.groups
end

#hash ⇒ Fixnum

Returns a hash code based on the glyph assignments.

Returns:

  • (Fixnum) —

    Returns a hash code based on the glyph assignments.



137
138
139
 
# File 'lib/doku/puzzle.rb', line 137

def hash
  @glyph_state.hash
end

#solution? ⇒ Boolean

Returns true if the puzzle is #filled? and #valid?.

Returns:

  • (Boolean) 


195
196
197
 
# File 'lib/doku/puzzle.rb', line 195

def solution?
  filled? and valid?
end

#solution_for?(puzzle) ⇒ Boolean

Returns true if the puzzle is valid solution for the given puzzle.

Returns:

  • (Boolean) 


202
203
204
 
# File 'lib/doku/puzzle.rb', line 202

def solution_for?(puzzle)
  solution? and puzzle.subset?(self)
end

#squares ⇒ Array

Shortcut for calling the squares class method.

Returns:

  • (Array) —

    Array of squares.



90
91
92
 
# File 'lib/doku/puzzle.rb', line 90

def squares
  self.class.squares
end

#subset?(puzzle) ⇒ Boolean

Returns true if the puzzle’s glyphs assignments are a subset of the given puzzle’s glyph assignments and the two puzzles are the same class.

Every puzzle is a subset of itself.

For example, if you find a Sudoku puzzle and start working on it, you have changed the original puzzle into a new puzzle. The original puzzle will be a subset of the new puzzle, assuming you didn’t erase any numbers.

Returns:

  • (Boolean) 


164
165
166
 
# File 'lib/doku/puzzle.rb', line 164

def subset?(puzzle)
  self.class == puzzle.class and glyph_assignment_subset?(puzzle)
end

#valid? ⇒ Boolean

Returns true if this puzzle follows the rules. A puzzle is valid if no glyph appears twice in any group. For example, a Sudoku puzzle would be invalid if you wrote a “3” twice in the same column.

Returns:

  • (Boolean) 


186
187
188
189
190
191
 
# File 'lib/doku/puzzle.rb', line 186

def valid?
  groups.all? do |group|
    glyphs = group.collect { |square| self[square] } - [nil]
    glyphs.uniq.size == glyphs.size
  end
end