Long ago, I came into possession of an Oskar’s Cube and have often wondered how difficult it is to create mazes of that type.  Clearly it could be more complicated than a simple 2D maze.  So, I decided to find out.

Initial observation:

While the Oskar’s Cube looks like three simple mazes on the faces of a cube, solving all three of them simultaneously is considerably more difficult than solving each one individually.

Question:

While generating and solving two dimensional mazes is quite easy, is generating multiple interacting mazes similarly more difficult?  Additionally, can the process be extended to higher dimensions?

Expectation:

With the additional constraints of generating several interacting mazes, it seems likely that some positions would likely be unreachable.

Procedure:

To explore the question of maze cube generation, a C program (MazeCubeGen), was written which attempts to create maze cubes.  The maze generation picks a random starting point then performs a random walk that adheres to the additional movement constraints imposed by mapping the mazes onto the faces of a cube.  As expected parts of the cube may sometimes become unreachable during the random walks.  When this occurs, an additional starting point is chosen and a new random walk started.  Solutions to such maze cubes can easily be found using standard depth first search.

Results:

To test the implementation of the maze cube generator three mazes were used.  The first maze was a manually entered version of Oskar’s Cube, which is 11x11x11.  The second maze was a randomly generated 21x21x21 maze cube.  The final was a randomly generated 11x11x11x11 maze hypercube.

The first maze used was a recreation of Oskar’s Cube to verify that the internal representation of the mazes was correct and that the solver could handle a maze with a known solution.  An STL file of this model and its solution are available.

The second maze demonstrates that the maze generation can produce maze cubes with a larger size.  It is a 21x21x21 maze, which is approximately 8 times the size of the original Oskar’s Cube. An STL file of this model and its solution are also available.

The final maze is a four dimensional maze hypercube that is 11x11x11x11, to test the ability to produce higher dimensional mazes and solve them.  For obvious reasons, an STL model which is a 3D format cannot be created for a 4D model.

Conclusion:

With surprisingly little additional modification, common maze creation techniques can be used to generate maze cubes.  These techniques can also be extended to higher dimensional mazes.

Future Questions:

Currently the maze generation just performs random restarts whenever constraints are not met or it gets “stuck” and cannot find ways to extend the maze paths.  Would it be possible to use a recursive backtracking algorithm to avoid restarts?