Fun with recursion–or how to solve a maze
When I was really young, maybe ten years old, I loved mazes, both solving them and creating them. That was decades ago, prior to personal computers (I’m dating myself with that disclosure) and so the only mazes we could really solve were in small books my friend and I bought (or could get a parent to buy). The mazes in those books were often done in shapes of dinosaurs or dragons or what have you, and the mazes were (sometimes) made more difficult because of those shapes. We learned to draw mazes, in both the original between the lines and in the style of on the lines. Depending on details such as curves, hatch marks, and size, these mazes we made were easy or hard.
When I got my first “personal computer” (a TRS-80 Model I, with 16K of RAM with a display that showed 16 rows of 64 columns of uppercase-only text, with the ability to switch into graphics mode that allowed 48 rows of 128 columns of blocky pixels), I (somehow) found a BASIC program that I typed in that would create and solve mazes; at least I’m pretty sure I didn’t create the algorithms by myself, but it’s been so long ago (45 years) that maybe I actually did create it myself. If so, I apologize to my smarter younger self.
Then, for decades I forgot about all that until we purchased the game quoridor at a local bookstore , where the goal of the game is to get a pawn from your side to the opposite side where the path to the other side can be (will be) blocked by walls that you and your opponent put up between the squares. After playing it I thought about writing a program that would play it better than humans could (even though the branching factor on each move is well over 100–more than chess has, if I recall correctly).
One of the rules of the game–which is what prompted my recall of all the maze-making and -solving days in my past–is that no placement of a wall can totally block a player from reaching the other side. This translates to making sure that there’s some path from the current position to the finish, which is essentially the same as solving a maze.
There are significant differences between a well-crafted maze (i.e., a single non-trivial path from start to finish) and the path problem presented by quoridor rules (i.e., sparse wall placement, allowing many paths from start to finish), but the general problem is the same.
So I started a quick prototype of a computer game and got sidetracked on the movement rule that disallows a complete block to the finish, and after a false start on a generalized maze-solving algorithm, I got a simple algorithm fully working, and it’s this algorithm that I’m covering in this post, mostly because it brings back a lot of good memories of just working through a completely abstract problem.
What is a maze?
From a conceptual perspective (with a big, big, lean toward computer science concepts), a maze is just a tree with the start position as the root of the tree and some leaf node (or nodes) being the finish. This is packed into a visual 2D form that is intended to make it difficult to see the path from root to leaf. (Note: if the maze is not a tree, then there is at least one node that has two distinct paths to it, which can make it easier to solve the maze.)
So in essence solving a maze is equivalent to walking a tree structure, and the algorithm presented here does indeed traverse a tree structure in a typical recursive fashion.
What is recursion?
I’m not sure who will end up reading this post, so I don’t know what to expect in terms of knowledge of computers and programming, so I’ll cover the concept of recursion very briefly.
To recurse is for some operation to refer back to itself only with simpler information. The prototypical mathematical function that’s defined in terms of recursion is the fibonacci number:
fib(n) = fib(n-1) + fib(n-2) ; for n > 1
fib(0) = 1
fib(1) = 1In some sense recursion breaks down a problem into a simpler one until the problem size gets to an easily solved (or defined) case.
Tree walking
If the goal of solving a maze is equivalent to finding a path from the root of a tree to a specific leaf node(s), then we just need to walk the tree keeping track of just how we got from root to leaf. There are two general ways of tree walking: breadth-first and depth-first. The basic difference between the two is that depth-first walking usually uses recursion and a parallel stack to keep track of the (current) path while breadth-first uses a queue to visit all the tree nodes.
As this post is implying that recursion is fun, it should be clear that for this problem that recursion was chosen as the way to solve a maze.
Problem details
For our purposes, let’s say the maze is on a square grid of size n, meaning that there are n^2 “cells”. Let’s further say that it’s possible–subject to wall placement–to move only in one of four directions from a given cell: up, left, down, right. Walls between adjacent cells disallow a move between the cells, and a move from one side of the grid directly to the opposite side (via “wrapping around”) is never allowed.
Additionally, let’s say the start position is given as start and can be any cell on the edge, and finish is also any cell on the edge (things get more interesting if a few things are relaxed: if start and finish are not on the edges and the maze is not a tree, then I believe it might not be always solvable as the algorithm could end up going in circles).
Finally, let’s say that the maze maker did the proper job and the maze is actually solvable, meaning that there really is a path from the root of the tree to the finish leaf–if that’s not the case then there wouldn’t be a single tree that represents the problem.
With the above, we’re now ready to jump into the recursive algorithm…
Recursive solution
As mentioned above, the idea of recursion is to break the problem down to a smaller problem and the apply the same algorithm to the smaller problem. In our case, the “smaller problem” is looking for a path that’s one move shorter than where we currently are in the maze–basically we’ll see if we can take a step in the right direction and then try to solve the maze from that just-stepped-into position in the maze.
Let’s assume (with good reason) that the current position (cell) in the maze that we’re currently at is a valid position, meaning very specifically that there’s a path from the start position to the current position. This is trivially true if we start at the start position–there’s a path (of zero steps) from the start to there. From that point on, if we only take valid steps then there will still be a path from the start to the current position. So we just have to define what a valid move is, which is pretty easy: a valid move is one that meets the following conditions:
- it doesn’t go outside the grid
- it doesn’t go through a wall
- it doesn’t go into a cell that’s already been visited
The final point is to check if we’ve actually solved the maze–that we’ve reached the finish. This is equivalent to defining what fib(0) and fib(1) are above. So, if our current cell is the finish, then we’re done–we’ve found a path from start to finish.
With that in mind, the basic algorithm in sort-of-code for solve() is
solve(position)
IF at-finish(position)
RETURN true
visited[position] = true
IF ((can-move(position, UP) AND solve(move(position, UP)) OR
(can-move(position, RIGHT) AND solve(move(position, RIGHT)) OR
(can-move(position, DOWN AND solve(move(position, DOWN)) OR
(can-move(position, LEFT AND solve(move(position, LEFT)))
success = true
visited[position] = false
RETURN success The core algorithm really is that simple–and it doesn’t matter what order the UP, RIGHT, DOWN, LEFT are done in, as long as all four directions are tried. I’ve left out the definition of “can-move” but it really just tests the three conditions above.
Getting the path
While it’s true that the algorithm to find a path from start to finish is as simple as what’s shown above, the path from start to finish is held only in the recursion info of which particular line of code above that’s doing the can-move(position, direction) AND solve(move(position, direction))— each correct step (can-move line) is encoded by which one of the four lines was chosen.
In order to be able to extract the path in a more convenient form, it’s necessary to use a stack, where a position is pushed to the top of the stack when it’s visited, and then removed from the top when we’re done visiting it. On success at finding the finish, we just don’t remove anything from the stack, and then the path is the whole set of cells from the stack.
Finally, some code…
Here’s some (verbose) Java code that puts all the above together (and that is a bit more generalized in that it can find all solutions):
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Visitor
{
private int[][] visited;
private int size;
private Grid grid;
/**
* Non-static class so it has access to visited grid
*/
private class VisitContext
{
private List<List<Cell>> solutions = new ArrayList<>();
private Stack<Cell> path = new Stack<>();
private int depth;
private int maxDepth;
private Cell finish;
private boolean stopAtFirst;
VisitContext(boolean stopAtFirst)
{
this.stopAtFirst = stopAtFirst;
}
void enter(Cell pos)
{
path.push(pos);
depth++;
maxDepth = Math.max(depth, maxDepth);
visited[pos.getCol()][pos.getRow()]++;
}
void exit(Cell pos, boolean solved)
{
visited[pos.getCol()][pos.getRow()]--;
if (!solved)
pos = path.pop();
depth--;
}
boolean addSolution()
{
solutions.add(new ArrayList<Cell>(path));
return stopAtFirst;
}
boolean finished(Cell pos)
{
return ((pos.getCol() == finish.getCol()) &&
(pos.getRow() == finish.getRow()));
}
Stack<Cell> getPath()
{
return path;
}
int getMaxDepth()
{
return maxDepth;
}
}
/**
* Grid is what has the walls defined to make the maze
*/
public Visitor(Grid grid)
{
this.grid = grid;
size = grid.getSize();
visited = new int[size][size];
}
/**
* Find a path(s) from start to finish, returning true if a path was found
*/
public boolean findFinish(Cell start, Cell finish)
{
VisitContext context = new VisitContext(true);
boolean solved;
context.finish = finish;
solved = solve(start, DirVec.RIGHT, context);
if (!solved)
{
System.out.println("No solution found");
}
else
{
for (List<Cell> soln : context.solutions)
System.out.println("solution: " + soln);
grid.setPath(context.solutions.get(0));
}
return solved;
}
/**
* The recursive algorithm
*/
private boolean solve(Cell pos, DirVec dir, VisitContext ctx)
{
boolean solved = false;
if (ctx.finished(pos))
return ctx.addSolution();
ctx.enter(pos);
if (canMove(pos, dir) && solve(dir.apply(pos), dir, ctx))
solved = true;
else if (canMove(pos, (dir = dir.rotateLeft())) &&
solve(dir.apply(pos), dir, ctx))
solved = true;
else if (canMove(pos, (dir = dir.rotateLeft())) &&
solve(dir.apply(pos), dir, ctx))
solved = true;
else if (canMove(pos, (dir = dir.rotateLeft())) &&
solve(dir.apply(pos), dir, ctx))
solved = true;
ctx.exit(pos, solved);
return solved;
}
private boolean canMove(Cell pos, DirVec dir)
{
return (grid.canMove(pos.getCol(), pos.getRow(), dir.asBits()) && notVisited(dir.apply(pos)));
}
private boolean notVisited(Cell pos)
{
return visited[pos.getCol()][pos.getRow()] == 0;
}
}