Making Deventer's Mazes

In my previous post (the very first one!) I described how to solve an unique 3D maze puzzle by using RRT path planner provided by RobWorkStudio.

The original puzzle was designed by Oscar van Deventer and it consists of three orthogonal flat plates, each carved with the 2-dimensional maze. The three plates restrict the movement of a star-shaped cursor within the cube, such that it can only move on an invisible 3-dimensional path projected by the mazes on the side (see fig. 1).

Fig. 1. Deventer's maze recreation. The cursor is the star-shaped orange-ish shape inside the cube.

We were left with an open question of how to programmatically generate a new puzzle just like this.

The naive extension of backtracking algorithm into 3D works well, but it is not suitable to make Deventer's Maze without modification. The projection of 3D path generated by the algorithm on the orthogonal walls of the puzzle would inevitably contain loops. Indeed, the absence of loops on the walls seem to be the leading constraint in this problem.

A simple idea would be to build 4 separate mazes in parallel using the backtracking algorithm. 3 of these mazes would be two dimensional, representing the sides of the cube, while the fourth one would be fully 3D. The 3D maze would be the primary one used for the construction: the backtracker would explore the cells at will, except that while finding neighbouring adjacent unvisited cells, the side mazes would be used to guard against forming loops. Simply put, if the new candidate unvisited cell's projection is visited, and  no direct connection exists to that cell on the side maze, it is not elligible to be the candidate for the neighbour. Unvisited projection cells and those that already have connection (including to itself) are allowed.

This generation procedure has to be repeated, since not all of the cells will be visited on the first call of the backtracker. Some of the cells will be inaccessible from any one given path, and thus the backtracker has to be called again, starting from the next unvisited cell found.

This is perhaps a little obfuscated explanation; please check the code for the details.

I made an implementation of the Deventer Maze generator in Javascript HERE.

The repository is available at: https://github.com/dagothar/deventer.

.

Fig. 2. JS implementation of the generator. Take a look!

This is how the algorithm looks in action (fig. 3):

Fig. 3. Generating a new 8 x 8 x 8 maze.

The result is presented below (fig. 4):

Fig. 4. The result.

Of course, it is also possible to build larger puzzles (see fig. 5), although it quickly becomes a computational challenge.

Fig. 5. Generating large mazes may take a while (25 x 25 x 25).

I programed the generator such that you can try solving the generated mazes as well. The black star shape is the cursor, and you can move it using the W / A / S / D / Q / E keys:

• W / S move the cursor in the X direction (away / towards the red maze),
• A / D move the cursor left / right (away / towards the green maze),
• Q / E move the cursor down / up (towards / away the blue maze).

It is quite difficult to solve even the simplest mazes (see 3 x 3 x 3 in fig. 6)! In case you get stuck, you can use the input fields for the cursor position in the panel on the right to move without the path constraints.

Fig. 6. Navigating the 3 x 3 x 3 maze.

The panel on the right also provides some information. First, it indicates if the current maze corners all belong to a single path component. This will not always be the case. Next, the number of separate paths is provided. The first path will most likely be the largest component and its size is also provided.

There are still a couple of problems with this approach though. Very often, no path is generated that connects all corners of the maze. Such a result I do not consider to be a proper puzzle, since not all of the corners can be reached from single chosen starting configuration. The issue could perhaps be amended by growing separate and unbiased trees at every corner of the cube and then prioritizing the merging of the trees. I am not sure that would guarantee that the generated puzzle is proper.

Of course, it is likely not possible to make a nice random and aesthetic tree exploring all cells of the puzzle. The original creation itself did have cells which were not reachable from the starting configuration.

It would be nice to create the actual 3D models based on the generator presented here. I will work on that in the future.