Search⌘ K
AI Features
Home
Courses
Mazes for Programmers

Implementing the Recursive Backtracker Algorithm

Explore how to implement the Recursive Backtracker algorithm using an explicit stack in Ruby to generate complex mazes. Understand how the algorithm manages visited cells, backtracks when no unvisited neighbors remain, and compares in speed and memory use to Hunt-and-Kill. This lesson equips you to create maze puzzles featuring winding corridors and efficient traversal.

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.

C++
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 ...