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
search(k, root, y, solution = [])
click to toggle source
@param k [Integer] solution “deepness” @param root [ColumnObject] root @param y [Yielder] enumerator yielder @param solution [Array<DataObject>] current solution
# File lib/exact_cover/cover_solver.rb, line 44 def search(k, root, y, solution = []) if time_limit && start_time + time_limit < Time.now raise TimeLimitReached, "Ran for more than #{time_limit} seconds" end if root.right == root y.yield format_solution(solution) return end column = choose_column(root) cover_column(column) r = column.down loop do break if r == column solution[k] = r j = r.right loop do break if j == r cover_column(j.column) j = j.right end search(k + 1, root, y, solution.dup) j = r.left loop do break if j == r uncover_column(j.column) j = j.left end r = r.down end uncover_column(column) 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