Class: ExactCover::CoverSolver

Inherits:
Object
  • Object
show all
Defined in:
lib/exact_cover/cover_solver.rb

Overview

Solves the cover problem with algorithm “X”

Defined Under Namespace

Classes: InvalidMatrixSize

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(matrix) ⇒ CoverSolver

Returns a new instance of CoverSolver.



14
15
16
17
18
19
20
21
22
 
# File 'lib/exact_cover/cover_solver.rb', line 14

def initialize(matrix)
  @matrix = matrix
  # sanity check
  if !matrix.is_a?(Array) || matrix.size == 0 || matrix[0].size == 0
    raise(InvalidMatrixSize, "non-empty 2-dimensional array expected, got #{matrix.inspect}")
  end

  @column_count = matrix[0].size
end

Instance Attribute Details

#column_count ⇒ Object (readonly)

Returns the value of attribute column_count.



12
13
14
 
# File 'lib/exact_cover/cover_solver.rb', line 12

def column_count
  @column_count
end

#matrix ⇒ Object (readonly)

Returns the value of attribute matrix.



11
12
13
 
# File 'lib/exact_cover/cover_solver.rb', line 11

def matrix
  @matrix
end

Instance Method Details

#call ⇒ Enumerator

Solve the exact cover problem for the given matrix

Returns:

  • (Enumerator) —

    An enumeration of the all the possible solutions



26
27
28
29
30
31
 
# File 'lib/exact_cover/cover_solver.rb', line 26

def call
  root = MatrixPreprocessor.new(matrix).call
  Enumerator.new do |y|
    search(0, root, y)
  end
end