A Novel Algorithm for Solving Mazes

Conventional maze solving algorithms have revolved mainly around the "rat in the maze" approach in which a "rat" effectively runs through the maze according to set rules and backtracks only upon reaching a dead-end; implying only a local knowledge of the maze relative to the "rat's" position since it cannot "see" around corners. These algorithms are inherently recursive in nature since they require that upon encountering an intersection of paths in the maze, one path is selected at a time while "remembering" the intersection. If the selected path leads to a dead-end, the "rat" must return to the last intersection it encountered and follow another path until a dead-end or the end goal is reached. This is essentially a depth-first search on a tree with maximal degree N, where N is the number of adjacent locations the "rat" can move to next from any given location. For example, in a two-dimensional maze where only North, East, West, and South (NEWS) moves are valid, N=4. If diagonal moves are also allowed, N=8. These can easily be extended to higher dimensions where for a three-dimensional maze, N=6 for NEWS, up and down moves allowed, and N=26 if all diagonal moves are allowed. As can be seen for a large maze, the memory requirements to store such a potentially large tree and/or a stack used in traversing it in a depth-first manner can be quite substantial.

It may seem natural at this point to abandon the concept of a single "rat" with only a local knowledge of the maze and its corresponding depth-first search, and consider instead the implications of a global knowledge of the maze due to simultaneous local interactions throughout the maze. This will amount to being able to "see" the whole maze at one time.

Let's assume that we want to solve a two-dimensional maze with only NEWS moves allowed, although the algorithm can be extended to higher dimensioned mazes with other allowable moves in a straight-forward manner. The maze is represented by a two-dimensional array or grid Maze[XSize][YSize] where Maze[x][y] == 1 denotes a wall at location (x,y) and Maze[x][y] == 0 indicates that location (x,y) is free (0<= x < XSize, 0<= y < YSize). A location that is "free" at a particular time during the algorithm's execution means that it can potentially be part of the solution path or paths, with all free paths being 1 unit wide. Likewise, a location that is wall cannot be part of the solution path. In addition, the maze is bounded by walls except for the start and end positions which lie on the boundary and are considered to be permanent free locations, thus, only locations (x,y) with 0 < x < Xsize-1 and 0 < y < Ysize-1 need to be evaluated.

The heart of the algorithm is really quite simple. First, a two-dimensional array of cells is defined with each cell representing a location in the maze. A cell can change its "state" during each iteration according to a state transition rule which depends upon its current state and the current state of its NEWS adjacent cells. This is, in effect, the definition of a cellular automata, or CA.

Next, two different states are defined for each cell in the CA. A cell in the FREE state, or a "free cell", corresponds to a free location as described previously. Likewise, a cell in the WALL state, or "wall cell", corresponds to wall location.

In determining the state transition rule, the following observation can be made: A dead-end condition may be characterized by a free cell surrounded by at least N-1 wall cells, where again N denotes the number allowable adjacent moves. In our case, N=4, so a dead-end condition occurs if a free cell is surrounded by either 3 or 4 wall cells in the NEWS directions. The case where a cell is surrounded by N wall cells is a trivial case since it implies that the cell could never be accessed since it is completely surrounded by walls. The important point to note is that a free cell in a dead-end condition can never be part of the solution path since it has one entry and no exit points. Thus, the free cell can be changed to a wall cell. Changing the free cell to a wall cell will now cause free cells not on a solution path and immediately preceding the former free cells to exhibit the dead-end condition themselves. These are subsequently changed to wall cells and so on. As the process continues iteratively, dead-end paths become blocked off, and a steady state condition is reached if no free cells change during the iteration into a wall cell. At this point, the free cells will denote the solution path or paths through the maze. In the case where all the internal cells are wall cells, then no path from start to end through the maze exists.

The rule applied to each cell in the CA during each iteration can then be expressed as follows:

  1. If I am a free cell and I'm surrounded by 3 or 4 NEWS wall cells then I will become a wall cell.
  2. If I am a wall cell then I will always remain a wall cell.
  3. A free cell surrounded by less than 3 NEWS wall cells remains a free cell during the iteration.

The fact that only FREE to WALL and not WALL to FREE state transitions are allowed shows that the algorithm can never diverge, since oscillations cannot take place, and that the CA converges toward the solution or solutions of the maze with every iteration. In other words, stopping the algorithm at a certain point results in a partially solved maze whose solution space is always decreased in the next iteration unless the steady state condition is reached at which point the solution space is the solution or solutions of the maze, if any exist.

In addition, the fact that a cell only needs to store its current state means that no additional memory beyond the original cell (maze) array is required if the original maze can be overwritten. These two points also have the interesting implication that the algorithm may be stopped and restarted after any iteration using only the current states in the cell array, unlike other recursive algorithms which would require saving the entire search stack in order to restart.

The following C code fragment demonstrates how this might be implemented:

#define FALSE 0
#define TRUE  1
#define FREE  0
#define WALL  1
.
.
.
do {
    steadystate = TRUE;
    /* scan the entire CA */
    for (x=1;x<Xsize-1;x++) {
      for (y=1;y<Ysize-1;y++) {
        if (cell[x][y] == FREE) {
          /* addition can be used here to determine if */
          /* a cell is  surrounded by 3 or more walls  */
          if ((cell[x+1][y] + cell[x-1][y]
             + cell[x][y+1] + cell[x][y-1]) >= 3) {
            cell[x][y] = WALL;
            steadystate = FALSE;
          }
        }
      }
    }
  /* keep scanning the CA until */
  /* a steady state condition is reached       */
  } while(!steadystate);

  /* the cell array now contains the correct solution(s) */
  /* denoted by the remaining free cells                 */

  /* no solution if all cells are now wall cells         */

  .
  .
  .