Module: DancingLinks

Defined in:
lib/dancing_links.rb

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.



379
380
381
 
# File 'lib/dancing_links.rb', line 379

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.



361
362
363
 
# File 'lib/dancing_links.rb', line 361

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.



388
389
390
 
# File 'lib/dancing_links.rb', line 388

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.



370
371
372
 
# File 'lib/dancing_links.rb', line 370

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.



318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
 
# File 'lib/dancing_links.rb', line 318

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