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, TimeLimitReached

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(matrix, time_limit: nil) ⇒ CoverSolver

Returns a new instance of CoverSolver.



17
18
19
20
21
22
23
24
25
26
 
# File 'lib/exact_cover/cover_solver.rb', line 17

def initialize(matrix, time_limit: nil)
  @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
  @time_limit = time_limit
end

Instance Attribute Details

#column_count ⇒ Object (readonly)

Returns the value of attribute column_count.



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

def column_count
  @column_count
end

#matrix ⇒ Object (readonly)

Returns the value of attribute matrix.



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

def matrix
  @matrix
end

#start_time ⇒ Object (readonly)

Returns the value of attribute start_time.



15
16
17
 
# File 'lib/exact_cover/cover_solver.rb', line 15

def start_time
  @start_time
end

#time_limit ⇒ Object (readonly)

Returns the value of attribute time_limit.



14
15
16
 
# File 'lib/exact_cover/cover_solver.rb', line 14

def time_limit
  @time_limit
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



30
31
32
33
34
35
36
 
# File 'lib/exact_cover/cover_solver.rb', line 30

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