Background

The only hand-crafted orientation maze initially created is one I devised for G4G5 in Atlanta in April 2002. 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.