The rat-in-a-maze experiment is a classical one from experimental psychology. A rat (or mouse) is placed through the door of a large box without a top. Walls are set up so that movements in most directions are obstructed. The rat is carefully observed by several scientists as it makes it way through the maze until it eventually reaches the other exit. There is only one way out. The idea is to run the experiment repeatedly until the rat will zip through the maze without taking a single false path. The trials yield his learning curve.
We can write a computer program for getting through a maze and it will probably not be an smarter than the rat on its first try though. It may take many false paths before finding the right one. But the computer can remember the correct path far better than the rat. On its second try, it should be able to go right to the end with no false paths taken, so there is no sense re-running the program. Why don't you sit down and try to write this program yourself!!
Let us represent the maze by a 2 dimensional array, \(\texttt{maze[m][p]}\), where a value of 1 implies blocked path, while a 0 means one can walk right on through. We assume the rat starts at \(\texttt{maze[0][0]}\) and the exit is at \(\texttt{maze[m-1][p-1]}\).
\(\begin{array}{| r c c c c c c c c c c c c c l |} \hline
entrance $\rightarrow$ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 0 $\leftarrow$ exit \\
\hline
\end{array}\)
With the maze represented as a 2 dimensional array, the location of the rat in the maze can at any time be described by the row \(\texttt{i}\) and the column \(\texttt{j}\) of its position. Now let us consider the possible moves the rat can male at some point \(\texttt{[i][j]}\) in the maze.
The following figure shows the possible moves from any point \(\texttt{[i][j]}\). The position \(\texttt{[i][j]}\) is marked by an \(\texttt{X}\).
If all the surrounding squares have a 0 then the rat can choose any of these eight squares as its next position. We call these eight directions by the names of the points on a compass: north, northeast, east, southeast, south, southwest, west and northwest, or, N, NE, E, SE, S, SW, W , NW.
\(\begin{array}{c|c|c}
NW [i-1][j-1] & N [i-1][j] & NE [i-1][j+1] \\\hline
W [i][j-1] & X [i][j] & E [i][j+1] \\\hline
SW [i+1][j-1] & S [i+1][j] & SE [i+1][j+1]\\
\end{array}\)
We must be careful here because not every position has 8 neighbors. if \(\texttt{[i][j]}\) is on a border where either \(\texttt{i}=0\) or \(\texttt{m}-1\), or \(\texttt{j}=0\) or \(\texttt{p}-1\), then less than 8 and possibly only 3 neighbors exist. To avoid checking for these border conditions, we can surround the maze by a border of ones. The array will be declared as \(\texttt{maze[m+1][p+1]}\).
Another device that will simplify the problem is to predefine the possible directions to move in a table
Difficulty level
This exercise is mostly suitable for students
Send me your solution and get featured here !!Back to the list of exercises
Looking for a more challenging exercise, try this one !!
Deepest element in a binary tree