Exercise: Aldous-Broder as a Wall Adder

The Recursive Division algorithm is the only algorithm in this course that is described as a wall adder algorithm; all the others are passage carvers. It can be a fun puzzle, though, to try to implement other algorithms as wall adders as well.

Problem statement

Implement the Aldous-Broder algorithm as a wall-adder. Instead of carving passages as we walk between cells, we'll add walls. But which walls? That's the challenge!

Coding challenge

Think about the Aldous-Broder algorithm: it walks randomly from cell to cell, linking the current cell to the next one if the next has not been visited. But now we're turning that around; instead of starting with a grid where all the walls are present and removing them as we go, we're starting with a grid where no walls are present and adding them as we go.

Work through the algorithm one step at a time, thinking about how the algorithm might know when and where a wall should be added.

For our implementation, we'll make sure we first remove all the walls in the grid by linking each cell to all of its neighbors, just as we did for the Recursive Division algorithm. And then, to add walls, we must call Cell#unlink (to uncarve the passage between the two cells).

Write your solution code here: