Exercise: Optimizing Aldous-Broder

Problem statement

Looking specifically at the Aldous-Broder algorithm, we've noticed that it takes a lot of time and effort to visit and revisit the same cells repeatedly.

What gains might we find if we were to have the algorithm prefer neighboring cells that have been visited fewer times? Can you make such a change without introducing bias into the algorithm?

Coding challenge

In this challenge, use any or all of the code we've written so far to create a modified version of the Aldous-Broder algorithm that keeps track of how many times each cell has been visited. Then, when choosing which neighbor cell to visit next, it chooses from the neighbors that have been visited the least number of times.

Note that a cell might have multiple neighbors that have all been visited the same number of times. Make sure your solution chooses randomly between them rather than just picking (for example) the first one. We want to avoid introducing bias if we can.

When you're done, compare the mazes generated by this new algorithm to those of the unmodified Aldous-Broder algorithm. Do you think your modified algorithm is biased or not? Why?

Write your solution code for the modified version of the Aldous-Broder algorithm here: