At any given moment, the robot can only move 1 step in one of 4 directions. Valid moves are:
Note that positions are specified in zerobased coordinates (i.e., 0...size1, where size is the size of the maze in the corresponding dimension).
The robot can only move to positions without obstacles and must stay within the maze.
The robot should search for a path from the starting position to the
goal position (a solution path) until it finds one or until it
exhausts all possibilities. In addition, it should mark the path it
finds (if any) in the maze.

A path in the maze can be marked by the '' symbol...
A path refers to either a partial path, marked while the robot is still searching:  (i.e., one that may or may not lead to a solution). Or, a solution path:  which leads from start to goal. 
Remember that a recursive algorithm has at least 2 parts:
Let's start by assuming there is already some algorithm that finds a path
from some point in a maze to the goal, call it FINDPATH(x, y)
.
Also suppose that we got from the start to position x=1, y=2 in the maze (by some method):
What we now want to know is whether there is a path from x=1, y=2 to the goal. If there is a path to the goal from x=1, y=2, then there is a path from the start to the goal (since we already got to x=1, y=2). 
To find a path from position x=1, y=2 to the goal, we can just ask
FINDPATH
to try to find a path from the
, ,
, and of
x=1, y=2:
FINDPATH()
FINDPATH()
FINDPATH()
FINDPATH()
Generalizing this, we can call FINDPATH
recursively to
move from any location in the maze to adjacent locations. In this way,
we move through the maze.
FINDPATH
recursively
to advance through the maze. We also need to determine when
FINDPATH
must stop.
One such base case is to stop when it reaches the goal.
The other base cases have to do with moving to invalid positions. For example, we have mentioned how to search of the current position, but disregarded whether that position is legal. In order words, we must ask:
Now, to our base cases and recursive parts, we must add some steps to mark positions we are trying, and to unmark positions that we tried, but from which we failed to reach the goal:
FINDPATH(x, y)
 if (x,y outside maze) return false
 if (x,y is goal) return true
 if (x,y not open) return false
 mark x,y as part of solution path
 if (FINDPATH( of x,y) == true) return true
 if (FINDPATH( of x,y) == true) return true
 if (FINDPATH( of x,y) == true) return true
 if (FINDPATH( of x,y) == true) return true
 unmark x,y as part of solution path
 return false
All these steps together complete a basic algorithm that finds and
marks a path to the goal (if any exists) and tells us whether a path
was found or not (i.e., returns true or false). This is just one such
algorithmother variations are possible.
FINDPATH
will be called at least once for each position
in the maze that is tried as part of a path.
Also, after going to another position (e.g., ):
if (FINDPATH( of x,y)¹ == true) return true²
if a path to the goal was found, it is important that the algorithm
stops. I.e., if going of x,y finds a path
(i.e., returns true¹), then from the current
position (i.e., current call of FINDPATH
) there is no
need to check ,
or . Instead, FINDPATH
just
need return true² to the previous call.
Path marking will be done with the '' symbol and unmarking with the '' symbol.
FINDPATH
to find and mark a path from the start to
the goal with our given representation of mazes, we just need to:
FINDPATH(startx, starty)
.
FINDPATH
to work correctly. That is why we remark
it at the end.
For example, suppose the algorithm just marked position x=2,
y=3 in this maze. I.e, it is in the call to FINDPATH(x=2,
y=3) . After marking...

First, it will try to find a path to the goal from the position
of x=2, y=3,
calling FINDPATH() .
Since the position is not open, the call

Next, it will go
of x=2, y=3, calling
FINDPATH() .
This position is not open, so it will backtrack to

Next, it will go
of x=2, y=3, calling call
FINDPATH() .
This position is not open, so it will backtrack to

Finally, it will go of x=2, y=3, calling
FINDPATH() .
This position is not open, so it will backtrack to
Since is the last direction to search
from x=2, y=3, it will unmark x=2, y=3, and backtrack to the
previous call, 
To better illustrate this backtracking, let's look at an example run in which a dead end is reached at some point in the search:
Feel free to follow the search algorithm using other input mazes and parameters.
FINDPATH
searchs ,
, ,
?
FINDPATH
returns false,
does that mean there is no path from the start to the goal?
FINDPATH
more
than once? If so, how can this be rectified? If not, how does the
algorithm prevent that?
FINDPATH
finds?