Reskill Americans
Code Challenge --
Maze Generator

In this code challenge, you will write a Maze Generator. The problem is to determine how to remove walls in a grid to form a proper maze. A proper maze should have:
  1. Reachability: Allow a wanderer to start at any cell in the grid, and reach any other cell in the grid - without walking through any walls.
  2. No Loops: There should be exactly one path between any two cells in the grid (not counting back-tracking). Note that a grid with this property will have N - 1 walls removed if it has N cells.
You can watch a sample solution, by pressing the Run button, below. When you are ready to try writing your own solution, open this CodePen Template.
Note the API reference at the bottom of this page.

API Reference

Your solution should be defined in the form of a JavaScript generator function. You're not required to be familiar with that. Only to know that your function name should have an "*" in front of it, and that you should use the yield statement in the inner loop of your solution. This will allow the grid visualization to display the workings of your program and for you to control the execution speed with the buttons beneath the grid.


The sample generator shown in this demo works by starting with the center cell of the maze. It "marks" it as being included in the set of cells reachable from the center cell.

It then picks a random cell and a direction. If the cell, and it's neighbor in that direction are on opposite sides of a wall with one cell being "marked" and the other cell being "unmarked", then it can remove the wall and increase the number of reachable cells from the center. It then marks the previously unmarked cell, and chooses another random cell in the grid.

The algorithm returns when N - 1 walls have been removed (for a grid with N cells in it), since, by that criteria, all cells will be reachable from the center (as well as every other cell).

There is an entire Wikipedia article on Maze Generation.

If you'd like to see how the Grid visual simulator was implemented - you can find the source code on our Github repo.