Module: DancingLinks

Defined in:
lib/dancing_links.rb

Overview

This module provides an implementation of the “dancing links” algorhthm to solve the “exact cover” problem.

The “exact cover” problem:

  • Given a set of vectors containing 0’s and 1’s:

  • Find a subset of these vectors that collectively contain one and only one 1 in each and every column.

For example the follwing set of vectors:

  • A = [ 0, 1, 0]

  • B = [ 1, 1, 0]

  • C = [ 1, 0, 0]

  • D = [ 0, 0, 1]

Has two solutions:

  • A = [ 0, 1, 0]

  • C = [ 1, 0, 0]

  • D = [ 0, 0, 1]

and

  • B = [ 1, 1, 0]

  • D = [ 0, 0, 1]

A better description of the problem can be found here: en.wikipedia.org/wiki/Exact_cover

The “dancing links” algorithm is a commonly used solution for this problem, and was found by Donald Knuth. The algorithm involves the construction of a sparse matrix containing nodes that are doubly-linked both horizontally and vertically. The matrix itself simply facilitates the depth-first search (aka backtracking) part of the algorithm.

The importance of the doubly-linked nodes are that they allow for quick removal/restoration of rows/columns of nodes, which is exactly what a backtracking algorithm for the “exact cover” problem needs.

horizontal removal:

  • node.left.right = node.right

  • node.right.left = node.left

horizontal restoration:

  • node.left.right = node

  • node.right.left = node

A better description of the algorithm can be found here: en.wikipedia.org/wiki/Dancing_Links

Defined Under Namespace

Classes: SparseMatrix

Instance Method Summary collapse

Instance Method Details

#convert_row_boolean_to_fixnum(ary) ⇒ Object

This utility method will convert an array of booleans to an array of 0’s and 1’s

Used to facilitate the displaying of 0's and 1's in problems/solution, which is easier to read.



429
430
431
 
# File 'lib/dancing_links.rb', line 429

def convert_row_boolean_to_fixnum ary
  Array.new(ary.length) { |i| ary[i] ? 1 : 0 } unless ary == nil
end

#convert_row_fixnum_to_boolean(ary) ⇒ Object

This utility method will convert an array of 0’s and 1’s to an array of booleans.

Used to facilitate the displaying of 0's and 1's in problems/solution, which is easier to read.



411
412
413
 
# File 'lib/dancing_links.rb', line 411

def convert_row_fixnum_to_boolean ary
  Array.new(ary.length) { |i| ary[i] == 1 } unless ary == nil
end

#convert_rows_boolean_to_fixnum(ary) ⇒ Object

This utility method will convert an array of boolean arrays to an array of fixnum arrays (0’s and 1’s).

Used to facilitate the displaying of 0's and 1's in problems/solution, which is easier to read.



438
439
440
 
# File 'lib/dancing_links.rb', line 438

def convert_rows_boolean_to_fixnum ary
  Array.new(ary.length) { |i| convert_row_boolean_to_fixnum ary[i] } unless ary == nil
end

#convert_rows_fixnum_to_boolean(ary) ⇒ Object

This utility method will convert an array of fixnum arrays (0’s and 1’s) to an array of boolean arrays.

Used to facilitate the displaying of 0's and 1's in problems/solution, which is easier to read.



420
421
422
 
# File 'lib/dancing_links.rb', line 420

def convert_rows_fixnum_to_boolean ary
  Array.new(ary.length) { |i| convert_row_fixnum_to_boolean ary[i] } unless ary == nil
end

#solve_exact_cover(available, existing = [], &block) ⇒ Object

Attempts to solve an “exact cover” problem represented by the given arrays.

  • available - an array of boolean arrays. Each boolean array represent one of the available vectors. true <-> 1, false <-> 0. Available vectors will be added to the existing vectors to form the resulting solution.

  • existing - an array of boolean arrays. Each boolean array represent one of the vectors. true <-> 1, false <-> 0. Existing vectors are assumed to be non-conflicting, and will used as part of the resulting solution.

  • block - a “block” or Proc. This block will be called for each solution found.

The return value:

  • If no block is given then the first solution found will be returned.

  • If a block is given, and when called returns any value other than false or nil, the algorithm will stop, and return the result from the block.

  • If a block is given, but the block never returns any value other than false or nil, the total number of solutions found will be returned.



368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
 
# File 'lib/dancing_links.rb', line 368

def solve_exact_cover(available, existing = [], &block)
  matrix = SparseMatrix.new available
  existing.each do |row|
    row.each_index do |i|
      if row[i]
        node = matrix.root.right
        unless until node == matrix.root
            if node.index == i
              remove_rows_for_header node
              remove_horizontal node
              break true
            end
            node = node.right
          end
        then
          throw "Column conflict or not found."
        end
      end
    end
  end
  
  solution = existing.clone
  solve(matrix.root, [], 0) do |sel|
    sel.each do |row|
      solution.push(available[row])
    end

    unless block == nil
      if(result = block.call(solution))
        return result
      end
    else
      return solution
    end
    solution = existing.clone
  end
end