The Orientation maze

The orientation maze (O-maze) is a new style of multi-state arrow maze where your choices at each move are dictated by your orientation and the symbols you can see directly ahead of you. In this maze 'you' are represented by a red pointer, and the symbols in the maze are arrows that give you the option to move one square left, right, up or down, or rotate you ninety-degrees left or right.

This first set of puzzles are straight mazes with no obstacles. All mazes were produced by Jimmy Stephens's OrientExpress puzzle generator. Read more about OrientExpress below, or visit www.puzzlebeast.com to explore more of Jimmy's computer generated puzzles.

Your challenge is to negotiate the red arrow from the bottom to the top square.

Controls
Click on top corner arrows to select a new maze.
Click on bottom right arrows to undo/redo moves.
Click and hold on the red pointer to peek underneath it.

Movement
Click on a highlighted square to move or rotate the red pointer. Only squares immediately infront of the pointer are highlighted. Clicking on a rotation symbol will cause a quarter turn.

Keys
u – undo last move
r – redo last undone move

This second set of puzzles include one or more blue obstacles called 'switchers', which hide one symbol from view and will switch places with the red pointer if the pointer is pushed onto the same square. Thus the switcher is a moveable obstacle. The switcher hugely increases the number of possible states in the maze, and thus the average length of solution. These challenges were all created by OrientExtress puzzle generator.

Your challenge is to negotiate the red arrow from the bottom to the top square.

Controls
Click on top corner arrows to select a new maze.
Click on bottom right arrows to undo/redo moves.
Click and hold on a blue-switcher or the red pointer to sneak a peek underneath.

Movement
Click on a highlighted square to move or rotate the red pointer. The blue switcher acts as an obstacle, hiding one square. The red pointer and blue switcher will swap places if the red pointer is pushed onto a square occupied by a blue switcher.

Keys
u – undo last move
r – redo last undone move


Background

The one and only hand-crafted orientation maze currently in existance is the one I devised for G4G5 in Atlanta in April 2002. You can find the original maze here. It was not until I saw the results of OrientExpress however that I realised just how much complexity and variety was possible on a 4x4 grid. Infact no O-maze featured on these pages is any larger than 4x4, which is remarkable considering most of my other puzzles start at 5x5. It turns out O-maze works best on 4x4, 5x5 works reasonably well too but there is little gain in complexity and with anything larger than 5x5 the maze-like behaviour begins to breakdown (due to having too many options at each turn). The O-maze is a good example of just how small and complex a multi-state maze can be.

Notes from the Author

The OrientExpress program for generating orientation mazes was written with the benefit of the experience gained from developing SwampBeast, the plank puzzle generator (see www.puzzlebeast.com). Although the two types of puzzles are very different, the routines used for the puzzle solver module and for the random generation and mutation modules are quite similar between the two programs.

A screen-shot of an early version of OrientExpress is shown on the right. As with SwampBeast, this program creates puzzles first by randomly generating a large number of mazes, saving only the ones which look the most promising. The top candidates are then subjected to random mutations, again saving only the best puzzles. The puzzles posted above typically resulted from several tens of thousands of random generation steps, followed by a similar number of random mutation steps.

To identify 'promising' puzzles, a method is needed for scoring puzzles once they are created. Ideally, this score should be an estimate of how difficult and/or fun the maze is to solve. Since the basic mechanics for puzzle creation and solving had already been developed for SwampBeast, much of the challenge in developing OrientExpress came in finding a good scoring metric.

The puzzles created early on were simpler in that they did not have switchers, and the length of the solution path was used as the sole measure for scoring these puzzles. However, when the switchers were added, scoring became more complicated. With switchers it became possible for the solution path to have repetitive loops in it, a feature you will notice in many of the puzzles. (For example, see puzzle #2 in the second set of puzzles above.) In fact, virtually all of the switcher puzzles OrientExpress initially produced proved to be very long, and very, very repetitive. Solving a few puzzles of this type was fun, but after solving a couple of dozen of them, the repetitive nature became a colossal drag.

So, new scoring methods were tested in an effort to bump OrientExpress out of it's loopiness. After some trial and error, the most successful metric proved to be one I call Entropy Scoring. It is based on the assumption that solution paths with high entropy will have more unexpected twists and turns, and will therefore be more interesting and difficult. (See puzzles #1, 3, 8-11, 13-16, in second set of puzzles above for puzzles created using Entropy Scoring.) In practice, mazes generated using this metric proved to be much less repetitive, and do in fact seem to be more difficult to solve for a given solution length.


Concept – © Andrea Gilbert 2002
Applet & maze designs – © James Stephens 2002