class ExactCover::CoverSolver

Solves the cover problem with algorithm “X”

Attributes

column_count[R]
matrix[R]
start_time[R]
time_limit[R]

Public Class Methods

new(matrix, time_limit: nil) click to toggle source
# 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

Public Instance Methods

call() click to toggle source

Solve the exact cover problem for the given matrix @return [Enumerator] An enumeration of the all the possible solutions

# 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

Private Instance Methods

choose_column(root) click to toggle source
# File lib/exact_cover/cover_solver.rb, line 106
def choose_column(root)
  # Minimize the branching factor by choosing the column with the lowest size
  min_size = root.right.size
  min_size_column = root.right

  current_column = min_size_column.right
  loop do
    break if current_column == root

    if current_column.size < min_size
      min_size = current_column.size
      min_size_column = current_column
    end

    current_column = current_column.right
  end

  min_size_column
end
cover_column(column) click to toggle source

removes c from the header list @param column [ColumnObject]

# File lib/exact_cover/cover_solver.rb, line 128
def cover_column(column)
  column.right.left = column.left
  column.left.right = column.right

  i = column.down
  loop do
    break if i == column

    j = i.right
    loop do
      break if j == i

      j.down.up = j.up
      j.up.down = j.down
      j.column.size -= 1

      j = j.right
    end

    i = i.down
  end
end
format_solution(solution) click to toggle source

@solution consists in an array of DataObject, formats it to an array of 0 and 1 rows (corresponding to some rows of the given matrix) @return [Array<Array>] Subset of the matrix rows corresponding to an exact cover

# File lib/exact_cover/cover_solver.rb, line 91
def format_solution(solution)
  rows = []
  solution.each do |data_object|
    row = Array.new(column_count, 0)
    current = data_object
    loop do
      row[current.column.name.to_i] = 1
      current = current.right
      break if current == data_object
    end
    rows << row
  end
  rows
end
uncover_column(column) click to toggle source
# File lib/exact_cover/cover_solver.rb, line 151
def uncover_column(column)
  i = column.up
  loop do
    break if i == column

    j = i.left
    loop do
      break if j == i

      j.column.size += 1
      j.down.up = j
      j.up.down = j

      j = j.left
    end

    i = i.up
  end

  column.left.right = column
  column.right.left = column
end