RAILWAY MAZES

Stan Wagon                    Antonin Slavik

Macalester College, St. Paul       Charles University, Prague

Mazes in Mathematica

It is fun to think about how Mathematica can be used to solve mazes. Last year I was teaching Disc. Applied Math., and I saw the intriguing Railway Mazes publised by Sir Roger Penrose in the Martin Gardner conf. proceedings. I wanted to solve them algorithmically. About the same time, some WRI blogs by Jon McLoone and Danny Lichtblau appeared on more general mazes.

Given a maze in appropriate form, the naive idea for solving should work: Explore the maze in some organized fashion (breadth-first search) until the end is reached. Traditionally this required having the maze as a Graph object. The idea of the WRI blogs was to work directly from the jpeg image.

Blenheim Maze

Solved by McLoone:

Reader Challenge

A blog reader challenged Jon with this:

Solution

McLoone did it using his method.

To repeat: The idea is to get a solution directly from the image file.

Railway Mazes

In a railway maze -- these were developed by Sir Roger Penrose and his father Lionel -- one pretends one is a railway engine with no reverse gear: legal turns must follow the “track” at the junctions. One has no reverse gear.

A very simple one

My first idea was to turn it into a directed graph object, adding various gadgets (W-shapes) to enforce the rules. But the junctions need not be simple 3-way junctions. I did succeed with the one above, but not with the truly puzzling ones.

We worked on the three in the Penrose paper.

Railway Maze 3

The first one is intriguing because there is a unique solution, but it can feel as if there is no solution.

Railway Maze 2: The Luppitt (England) Maze

The second one is etched in stone in Luppitt, England.

Railway Maze 3

The third one was the hardest for us.

Then Antonin Slavik took a more image-oriented approach, and that worked to solve the Penrose mazes....

Part Two