Why mazes make good puzzles
A maze is a natural programming problem. It has a simple description, a clear goal, and a variety of approaches that differ in cleverness and cost. It is also easy to visualize, so you can check your reasoning by drawing. And it maps neatly onto a grid: each cell is either open or a wall, and a traveler moves between neighboring open cells.
For grid-based languages the match is especially close. In a language where an instruction pointer moves across a two-dimensional surface, a maze-walking program is a pointer traversing a different two-dimensional surface, which makes the problem feel almost native.
Setting up the problem
Before choosing a method, pin down the rules, because they change the answer:
- How is the maze given? As text characters in rows, with one symbol for walls and another for open space? Is it a perfect maze (one path between any two points, no loops) or can it have cycles?
- What is the goal? Reach an exit, find the shortest route, print the route, or just report whether one exists.
- What moves are allowed? Four directions, or diagonals as well?
- Where is the knowledge? Does the program see the whole maze at once, or only the cells next to it, like a person inside the maze?
The last question divides the puzzle in two. If you can see the whole map, you can plan. If you can see only your surroundings, you need a rule of thumb for exploring.
Wall following
The simplest strategy needs almost no memory. Keep one hand on a wall, say the right one, and keep walking. In many mazes this eventually leads you to the exit, because you trace the boundary of the walls.
There is an important caveat. Wall following is known to work when the exit is connected to the outer wall, and it can loop forever if the goal is on an island, an area enclosed by walls that you never touch. So it is a handy approach, but not a universal one. Be cautious about promising it solves every maze.
As a program, the rule reduces to a small decision at each step: if the right side is open, turn right and step; otherwise if the front is open, step forward; otherwise try left; otherwise turn around. These are exactly the sorts of choices a pointer makes when its direction changes. Mapping them onto pointer direction and turning is a fun exercise, and the branches correspond to conditional branching on what the program reads from the neighboring cell.
Exploring systematically
With a map available, systematic searches are more reliable.
- Depth-first search. Follow one path as far as it goes. When you hit a dead end, back up to the last junction and try another branch. It uses a stack of choices, so it fits stack-based thinking well. It will find a path if one exists, but not necessarily the shortest.
- Breadth-first search. Explore outward in rings: first all cells one step away, then two steps, and so on, using a queue. The first time you reach the goal, you have used the fewest steps (when every step costs the same). This is the standard way to find a shortest route.
- Marking visited cells. In both methods you record which cells you have already seen so that you do not walk in circles. On a grid, the natural place to record this is the grid itself, by overwriting open cells with a mark.
Writing a recursive solution is another option in conventional languages, where the call stack acts as the stack of choices. In a language without function calls, you manage the stack yourself.
Mapping to a grid language
Here is where the puzzle gets interesting for Funge-style languages. The program and the maze can both be grids, and a few ideas help connect them.
- Storing the maze. A program can keep data in its own playfield, using get and put instructions to read and write cells, as described in the discussion of grid variables. A maze can be loaded into a region of the grid, and visited cells can be marked in place.
- Pointer as explorer. The instruction pointer’s own position and direction can represent the traveler’s. Turning the pointer is turning the traveler. Funge-98’s delta vectors allow arbitrary step sizes, though a simple maze only needs the four basic directions.
- Backtracking with the stack. Pushing each move onto the stack lets you undo them in reverse order. Popping returns you along the same path, which is the core of depth-first search.
- Several explorers. In versions of the language that support concurrent pointers, you can imagine splitting at each junction so that every branch is explored at once. This is a natural way to think about breadth-first search, though it needs careful handling of shared state.
It is easy to underestimate how much bookkeeping this takes. Even a small maze solver in a grid language involves many cells of code. Good layout and a trace visualizer are valuable aids for seeing where the pointer actually goes.
Starting small
If you want to try this, build up in stages:
- Make a tiny maze, perhaps five by five, and solve it by hand.
- Write the wall-following rule in a language you know well, and test it on several hand-drawn mazes, including one with an island.
- Switch to a systematic search and compare the paths found.
- Only then translate the idea to a grid language, one piece at a time: first reading a cell, then turning, then stepping.
Test with awkward cases: a maze with no exit, a start next to the exit, a maze with loops, a corridor one cell wide. Many bugs show up only on those.
What you learn
Maze solving teaches the difference between a heuristic and an algorithm: a rule of thumb that often works versus a method that is guaranteed within stated assumptions. It also shows how representation and algorithm affect each other. And it demonstrates how much simpler a task can feel when the data and the program share the same shape. Whether you solve a maze in Python or steer a pointer through a grid, the underlying thinking about states, choices and backing up is the same.