Chapter XIV Exact Cover

Algorithm X in Ruby

Knuth's recursive backtracker. We'll write it without the Dancing Links optimization — Ruby's hash-of-sets reads like the spec.

Represent the problem as two lookups: per-set list of elements, and per-element list of sets containing it. Both are Hashes; both are kept consistent on remove/restore.

class ExactCover
  attr_reader :sets, :covers

  def initialize(sets)
    @sets = sets.dup    # name => Set of elements
    @covers = Hash.new { |h, k| h[k] = Set.new }
    sets.each { |name, els| els.each { |e| @covers[e] << name } }
  end
end

02

The choose step picks the element with fewest covering sets — Knuth's S-heuristic, which is what makes the search fast in practice. (Tie-break: any element will do.)
```
def choose_element
  @covers.min_by { |_, names| names.size }&.first
end
```

Search: pick an uncovered element, branch on each set covering it, recurse. The cover/uncover operations are the heart of DLX — here we do them by simple hash mutation.

def search(partial = [], &blk)
  return blk.call(partial) if @covers.empty?
  e = choose_element
  return if @covers[e].empty?
  @covers[e].dup.each do |name|
    removed = cover(name)
    search(partial + [name], &blk)
    uncover(removed)
  end
end

def cover(name)
  removed = []
  @sets[name].each do |e|
    @covers[e].each do |other|
      next if other == name
      @sets[other].each { |x| @covers[x].delete(other) unless x == e }
      removed << [other, @sets.delete(other)]
    end
    @covers.delete(e)
  end
  removed
end

def uncover(removed)
  removed.each do |name, els|
    @sets[name] = els
    els.each { |e| @covers[e] << name }
  end
end

Run it. Sudoku encodes as exact cover with 729 sets (one per (row, col, digit) cell-fill) over a 324-element universe. DLX cracks a "hard" 17-clue Sudoku in milliseconds.

sets = {
  a: Set[1, 4, 7], b: Set[1, 4],    c: Set[4, 5, 7],
  d: Set[3, 5, 6], e: Set[2, 3, 6, 7], f: Set[2, 7]
}
ExactCover.new(sets).search { |sol| puts "cover: #{sol.inspect}" }
# cover: [:b, :d, :f]

Grammar — Ruby

Ruby reads as plain English. Methods are called without parentheses; blocks (anonymous functions) are everywhere. Knuth's Algorithm X happens to fit Ruby's hash-of-sets idiom perfectly.

class C ... end: class definition. Methods go between `class` and `end`.
def name(args) ... end: method definition. Parens optional on call sites; the last expression is the return value.
attr_reader :name: auto-generates a getter for @name. Pair with attr_writer / attr_accessor for setters.
@var: an instance variable. Lives on `self`; visible to all methods of this object.
:symbol: a symbol — like an interned string. Often used as hash keys.
do |x| ... end: a block — anonymous code passed to a method. The bars wrap parameters.
&blk: in a method signature, captures the block as a Proc. Call it with `blk.call(args)` or `yield`.
Hash.new { |h, k| h[k] = [] }: hash with a default-on-miss block. Lazy initialization, no nil checks.
each / map / select / min_by: enumerable methods. Compose them with blocks to traverse, transform, filter, and find.

Algorithm X picks the element covered by the fewest sets to branch on. min_by reads exactly like the spec: among element→set-list pairs, pick the one whose list is shortest.

require 'set'

covers = {
  1 => Set[:a, :b],     # element 1 is in sets a and b
  2 => Set[:c],         # element 2 is in set c only
  3 => Set[:a, :c]      # element 3 is in sets a and c
}

# pick the element with fewest covering sets:
e, names = covers.min_by { |_, names| names.size }
# -> [2, Set[:c]]   (element 2, only one covering set)

Try Ruby — official, in-browser →