To display, consruct, or solve the maze, click on the bluish button, labeled "Show the maze". Depending on your security setting, a yellow bar at the top of the page may appear warning you that running this applet ("ActiveX controls" it will say) maybe dangerous. In that case, click on this yellow bar and allow the applet to be run. Trust me. In any case, after you click on the bluish button, the tree will appear in a separate window. You may resize the window, minimize it, in which case its icon will appear in the bottom tray so you can restore it, or close it altogether. If this last action is taken, you must click on the bluish button again to restore the applet.

The idea is as follows: we start with an array of rectangles, something like this:

Inside each rectangle we place a vertex of a graph, marked in red. We then go and randomly select an interior wall between some two adjacent rectangles. If the corresponding vertices are

To illustrate a point, assume that after removing few of the walls, and joining the corresponding vertices, we arrive at the following situation:

The wall between the vertices

We continue to choose one of the remaining walls at random, and either keep it, or remove it and join the two relevant components together. We do this until all the vertices are in one connected component which forms a tree, i.e., it is possible to get from any vertex to any other vertex. At this point the path between any two vertices is unique, which in terms of the maze means there is only one solution. To make the maze a bit more spicier, we additionally remove 30 randomly selected walls.

The Union-Find algorithm is a method which allows us to decide quickly if given wall is to be removed or not. Check it out. The maze is actually solved either by the depth first search using a stack, or the breadth first search using a queue: Start at the entrance and search until you stumble on the exit. The queue solution actually produces the shortest solution.

Any comments are always welcomed: drobot@vdrobot.com

Back to Drobot's home page