Solving mazes of the kind of size one can see tends to be an easy problem in that once you know about eg breadth first search it isn’t too hard to write a program that will solve this sort of maze. Solving them is still necessary to show there is a solution but it isn’t super interesting because it is sort of obvious that breadth-first search gives the best solution and if you know about it then it is quite easy to think of using breadth-first search.

A much harder problem is generating mazes.

The algorithm used here seems to be:

1. Know how to generate a tiny maze
2. To generate a big maze, divide it into smaller mazes, generate those, then cut some things out (the tiny maze algorithm) to connect the sub mazes.

You can see the bias in the algorithm from the grid pattern inside the generated mazes.

One might wonder how to generate mazes such that each possible valid maze has the same probability of being generated.

First one should define what a valid maze is. Here it seems the definition should be something like:

A maze is an array of cells which are either white or black such that:

1. There is no 2x2 square of white squares

2. There is no 2x2 square of black squares (maybe this could be changed?)

3. Any two white squares are connected by a unique* path of (horizontally/vertically) adjacent white squares with no loops

* one may want to drop the uniqueness requirement.

I do not know how one would uniformly generate all such mazes.

Another definition of maze that I do know how to generate uniformly is one made of thick maze cells and thin separating lines:

A maze is a spanning tree of the graph where the nodes are cells and the edges are possible passages (so for a squarish maze the graph would basically be a grid: nodes at integer coordinates and edges between any horizontally/vertically adjacent nodes).

The problem of generating such a maze uniformly is therefore the same as that of picking a spanning tree such that each spanning tree is chosen with the same probability. An algorithm for this is Wilson’s algorithm and works as follows:

1. Pick (not necessarily randomly) some node and add it to your spanning tree (so your tree has one node and no edges)

2. Pick (not necessarily randomly) some node not in your tree. If no such node exists then you are done. Say that the current path is this node.

3. Randomly (uniformly) choose an edge touching the last node of the current path (it is ok to not choose the edge which is the last edge of the current path). Add that edge and the node on the end to the current path.

4 (a). If the current path contains a loop then delete all nodes (and edges) in the loop. Go to step 3.

4 (b). If the last node of the current path is in the spanning tree, add the current path to the spanning tree. Go to step 2.

4 (c). Otherwise go to step (3).

This algorithm isn’t too hard to implement (although drawing this sort of maze is a bit annoying). A compatible definition of maze with this one that fits into a “grid of black and white cells” pattern is the following:

A maze is a rectangular array of cells which are either black or white such that:

1. All cells with odd x and y coordinates are white

2. All cells with even x and y coordinates are black

3. For any two given white cells, there is exactly one path (ie with no loops) of adjacent white cells between them.

If one redraws the spanning tree and current path occasionally as this algorithm runs, the animation of maze generating is quite interesting to watch.

I think implementing these sorts of maze drawing generating and solving algorithms is good fun and quite a varied exercise. It’s definitely one I like doing.

Here is a visualisation of Wilson’s algorithm: https://bl.ocks.org/mbostock/11363008 Observe how different the shape of the tree is between runs.

If you want to skip implementing it yourself first and just see the result then here it is for a maze: https://bl.ocks.org/mbostock/11357811