The quantum maze

Welcome to the quantum maze! Where is the maze I hear you ask? Well, still in its many quantum-states of course. As you explore the grid the maze will collapse around you, and walls will materialise in positions dictated by your chosen route (following a simple rule). Once the maze walls have collapsed into existence, nothing will shift them. To try a different route you have to reset the entire universe!

This puzzle was introduced to me by Jonathan Welton, during one of the UK Gathering for Gardner Celebration of Mind Events in October 2010. Jonathan had first explored this concept over two decades ago, at which point he discovered the 8x8 grid had a single unique solution. More recently I discovered the 5x5 grid was also solvable and Jonathan went on to prove you can visit the blue corners in either order, left then right or vice-versa (can you find both solutions?). Explore the quantum maze below (5x5, 8x8, or the mystery bonus 12x6) and read more about its history. Both Jonathan and I have struggled to classify this puzzle. Is it actually a maze? It is certainly not a multi-state maze in the familiar sense. So then what is it? It is of course, a quantum-maze!

Move illustration
with new walls indicated

 

Aim
Start top-left (green) and aim for top-right (red) visiting both bottom corners (blue) enroute to win.

The maze starts in all possible quantum-states and will "collapse" around you as you move. Specifically walls will appear one step directly ahead of you and one more step out to both sides (as illustrated by the red arrows in the diagram).

Controls
Use the puzzle drop-list to select a grid size (5x5, 8x8, 12x6)
Use cursor-keys (or mouse-clicks) for movement
Use restart (action) or hit the space-bar, or click on green, to reset

Movement
Use the cursor keys to move (or click on the grid).


Background (Jonathan Welton)

"I created this in the late 80s or early 90s. I posted it on rec.puzzles around that time. The puzzle answers a question raised by multi-state mazes where one can visit a location in more than one state, such as in a no-left turn maze. When several states are possible the underlying maze can be simpler while maintaining the same difficulty of solution, because the multiple states make up for the lack of maze complexity.

This raises the question of whether a maze could require less information to describe it than it takes to describe the solution. Some rolling block mazes arguably achieve this feat, for example Richard Tucker's Rolling-Megalith Maze where the underlying maze consists of only three blocks.

But this maze answers the question absolutely, as the solution requires a long path to be described, with the maze objective describable in just a few bits, and the underlying maze itself empty and requiring no information at all to describe it. It could be argued that an empty grid can't be a maze at all, by the definition of a maze. And yet, as you wander through the puzzle it undoubtedly feels like a maze, one which is being slowly revealed to you as to progress through it. So there we have it: a maze which definitively requires less information to describe it than to describe the solution."


applet – © Andrea Gilbert 2010
concept - © Jonathan Welton
hosted with permission from Jonathan Welton