Two A-maze-ing Programs

Published: December 17, 2008

by Ted Holt

Note: The code accompanying this article is available for download here.

My family and I are preparing to celebrate Christmas. I'm enjoying the lights, the carols, and the decorations. I feel festive. I feel like doing something just for fun. Thus, the two programs I wrote for today's Four Hundred Guru are of no practical value of which I'm aware, but goodness, did I have fun writing them!

Consider the following text file, the contents of which is a maze.

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IB             I         I I I         I
IIIIIIIIIIIIII I IIIIIII I I   II IIIIII
II             I I       I I I I       I
II IIIIIIIIIIIII I IIIIIII I I IIIIIIIII
I  I             I I       I I         I
I I  IIIIIIIII III I IIIII I IIIIIIIII I
I   I        I I   I     I           I I
IIIII IIIIIIII I IIIIIII IIIIIIIIIIIII I
I              I         I             I
I IIIIIIIIIIIIIIIIIIIIII I IIIIIII I III
I       I   IIII       I I I       I I I
I I III I I I IIIIIIII   I I IIIII I I I
I I I   I I I  I       I I I I     I   I
I IIIIIII IIII IIIIIIIIIII I IIIIIIIIIII
I          IE              I           I
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

The beginning and ending points are cleverly indicated by the letters "B" and "E", respectively. How does one go about writing a computer program that finds a path from point B to point E?

A Recursive Method

One way to tackle this problem is to use recursion. Starting at point B, try to move up. If that way is blocked or turns out to be a dead end, try to move left. If that way is blocked or turns out to be a dead end, try to move right. If that way is blocked or turns out to be a dead end, try to move down.

All of this logic is implemented in a short routine, which in my program is called "Try". Try takes three parameters--a row number, a column number, and whether or not a solution has been found.

P Try             b                               
D                 pi                              
D   Row                          5i 0 value       
D   Col                          5i 0 value       
D   Solved                        n               
D*** locals                                       
D CurrentChar     s              1a               
 /free                                            
    CurrentChar = %subst(Maze: Offset(Row:Col):1);
    select;                                       
    when CurrentChar = 'E';                       
       Solved = *on;
       PrintMaze();                               
       return;                                    
    when CurrentChar = *blank                     
    or   CurrentChar = 'B';                       
       Mark(Row: Col);                            
       Try (Row: Col: Solved);                    
       if not Solved;                             
          Try (Row-1: Col: Solved);   // look up  
       endif;                                     
       if not Solved;                             
          Try (Row: Col-1: Solved);   // look left
       endif;                                     
       if not Solved;                             
          Try (Row: Col+1: Solved);   // look right
       endif;                                      
       if not Solved;                              
          Try (Row+1: Col: Solved);   // look down 
       endif;                                      
       UnMark(Row: Col);                           
    endsl;                                         
 /end-free                                         
P                 e                                

How can something so short and so simple solve such a complicated problem?

Notice that Try calls itself. In this example, the call to Try (2, 2) calls Try (2, 3), which calls Try (2, 4) and so on. Whenever an invocation of Try runs into a dead end, it backtracks and tries the next direction. Eventually it finds the E and prints the maze.

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
I**************I*********I I I         I
IIIIIIIIIIIIII*I*IIIIIII*I I***II IIIIII
II*************I*I*******I I*I*I       I
II*IIIIIIIIIIIII*I*IIIIIII I*I*IIIIIIIII
I**I*************I*I*******I*I*********I
I*I**IIIIIIIII III*I*IIIII*I*IIIIIIIII*I
I***I        I I***I*****I***        I*I
IIIII IIIIIIII I*IIIIIII*IIIIIIIIIIIII*I
I              I*********I*************I
I IIIIIIIIIIIIIIIIIIIIII I*IIIIIII I III
I       I   IIII       I I*I       I I I
I I III I I I IIIIIIII   I*I IIIII I I I
I I I   I I I  I       I I*I I     I   I
I IIIIIII IIII IIIIIIIIIII*I IIIIIIIIIII
I          IE**************I           I
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

Notice that the path to the end is marked with asterisks.

An Iterative Method

Several years ago, I learned an iterative way to solve mazes from a Dr. Dobbs Journal article. I wish I could find the article in order to give proper credit to the author, but I can't, and my Google search only turned up references to Basem A. Nayfeh's cellular automata method, which I'm quite sure is not the article I read.

Anyway, here's the idea. Beginning at point B, examine each square, row by row, column by column. If a blank square is surrounded on three sides by wall or dead end, mark the square as a dead end. An iteration ends when you reach the end of the maze. Continue until an iteration finds no dead ends.

Consider the following portion of a maze. The last blank in the second row is surrounded by three squares of wall, which means that it's a dead end.

IIIIIIIIII
I        I
I IIIIIIII

After the first iteration, that square has been marked with an X as a dead end.

IIIIIIIIII
I       XI
I IIIIIIII

The square before the new dead end, which is now the last blank square on the second line, is surrounded by two walls and a dead end. The second iteration flags this square as a dead end, and the maze looks like this.

IIIIIIIIII
I      XXI
I IIIIIIII

And so it goes. Here is the final state of the maze. Follow the blank squares to find the path to the end.

IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII
IB             I         IXIXIXXXXXXXXXI
IIIIIIIIIIIIII I IIIIIII IXI   IIXIIIIII
II             I I       IXI I IXXXXXXXI
II IIIIIIIIIIIII I IIIIIIIXI I IIIIIIIII
I  I             I I       I I         I
I I  IIIIIIIIIXIII I IIIII I IIIIIIIII I
I   IXXXXXXXXIXI   I     I   XXXXXXXXI I
IIIIIXIIIIIIIIXI IIIIIII IIIIIIIIIIIII I
IXXXXXXXXXXXXXXI         I             I
IXIIIIIIIIIIIIIIIIIIIIIIXI IIIIIIIXIXIII
IXXXXXXXIXXXIIIIXXXXXXXIXI IXXXXXXXIXIXI
IXIXIIIXIXIXIXIIIIIIIIXXXI IXIIIIIXIXIXI
IXIXIXXXIXIXIXXIXXXXXXXIXI IXIXXXXXIXXXI
IXIIIIIIIXIIIIXIIIIIIIIIII IXIIIIIIIIIII
IXXXXXXXXXXIE              IXXXXXXXXXXXI
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII

My Programs

My code is available for download . I quickly threw it together, so it is not elegant, and I'm sure you can improve on it, because I know I could.

There are two RPG programs, MAZERECUR and MAZELOOP, which implement the recursive and iterative methods. You will also find a file containing the maze I used in the examples.

Before you call the programs, you'll have to create a maze in a source physical file member. You can use SEU or WDSC to enter the maze. The rows can't contain more than eighty characters. You can have as many rows as you like, as long as the number of rows times the number of columns does not exceed 32K.

After you compile the programs, call a program with the qualified name of the file containing the maze in the first parameter and the name of the member containing the maze in the second parameter. For instance, if you put the maze in member MYMAZE in source physical file MYLIB/QRPGLESRC, these are the calls you can use.

CALL MAZERECUR ('MYLIB/QRPGLESRC' MYMAZE)
CALL MAZELOOP ('MYLIB/QRPGLESRC' MYMAZE)

Have fun! Merry Christmas!

                     Post this story to del.icio.us
               Post this story to Digg
    Post this story to Slashdot