Solution: Aldous-Broder as a Wall Adder

class AldousBroder_WallAdder
  def self.on(grid, start: grid.random_cell)
    # first, link every cell to its neighbors (removing all walls), so
    # that we can add the walls back as we go
    grid.each_cell { |cell| cell.neighbors.each { |n| cell.link(n, false) } }
    cell = start
    visited = Set.new([ cell ])
    while visited.count < grid.size
      neighbor = cell.neighbors.sample
      # here's the key: if the neighbor hasn't been visited before, look at
      # each of ITS neighbors. There must be a wall between it and any
      # neighbor that HAS been visited before---EXCEPT for the current
      # cell.
      if !visited.include?(neighbor) 
        neighbor.neighbors.each do |n|
          next if n == cell
          neighbor.unlink(n) if visited.include?(n) 
          end
      end 
      visited.add(neighbor) 
      cell = neighbor
    end
    grid
  end
end