Mazes for Programmers/

...

/

Implementing the Recursive Backtracker Algorithm

Implementing the Recursive Backtracker Algorithm

Learn how to implement the Recursive Backtracker algorithm in Ruby.

We'll cover the following...

The RecursiveBacktracker class

We’ll use an explicit stack to manage the cells that have been visited. We’ll use an array to represent the stack (which is easy in Ruby, since Ruby’s arrays come preloaded with the standard push and pop stack operators). Let's look at the code below.

Press + to interact
class RecursiveBacktracker
  def self.on(grid, start_at: grid.random_cell)
    stack = [] 
    stack.push start_at  
    while stack.any? 
      current = stack.last 
      neighbors = current.neighbors.select { |n| n.links.empty? } 
      if neighbors.empty?
        stack.pop 
      else
        neighbor = neighbors.sample 
        current.link(neighbor) 
        stack.push(neighbor) 
      end
    end
    grid
  end
end

Code explanation

Lines 4–5: Here, we initialize our stack to be an empty array and then push our starting location onto it. By default, that starting location is a cell chosen at random from the grid, though it can be configured by passing a different cell via the ...