maze problem

The backtracking algorithm.
Here is the algorithm (in pseudocode) for doing backtracking from a given node n:

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, return true
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds, return true
        }
        return false
    }
}

The non-recursive algorithm

Backtracking is a rather typical recursive algorithm, and any recursive algorithm can be rewritten as a stack algorithm. In fact, that is how your recursive algorithms are translated into machine or assembly language.

boolean solve(Node n) {
    put node n on the stack;
    while the stack is not empty {
        if the node at the top of the stack is a leaf {
            if it is a goal node, return true
            else pop it off the stack
        }
        else {
            if the node at the top of the stack has untried children
                push the next untried child onto the stack
            else pop the node off the stack

    }
    return false 

}


Example problem: given a maze, find out the number of possible paths from (0,0) to (N,M)

non-recursive solution:

struct Pos
{
int r;
int c;
bool visited;
int neighbor;
};

int neighbor_r[4]={0,1,0,-1};
int neighbor_c[4]={-1,0,1,0};

int MazeWalk(bool* maze,int row,int col)
{
int res=0;

vector<vector<Pos>> rec;
rec.resize(row);
for(int i=0;i<row;i++)
{
rec[i].resize(col);
for(int j=0;j<col;j++)
{
Pos my_pos;
my_pos.r=i;
my_pos.c=j;
my_pos.visited=maze[i*col+j];
my_pos.neighbor=0;
rec[i][j]=my_pos;
}
}
stack<Pos> my_stack;
rec[0][0].visited=true;
my_stack.push(rec[0][0]);
while(!my_stack.empty())
{
Pos& cur_pos=my_stack.top();
int cur_r=cur_pos.r,cur_c=cur_pos.c;
if(cur_r==row-1 && cur_c==col-1)
{
res++;
rec[cur_r][cur_c].visited=false;
my_stack.pop();
continue;
}
if(cur_pos.neighbor>=4)
{
rec[cur_r][cur_c].visited=false;
my_stack.pop();
continue;
}
int new_r,new_c;
new_r=cur_r+neighbor_r[cur_pos.neighbor];
new_c=cur_c+neighbor_c[cur_pos.neighbor];
cur_pos.neighbor++;
if(new_r>=0 && new_c>=0 && new_r<row && new_c<col && rec[new_r][new_c].visited==false)
{
rec[new_r][new_c].visited=true;
my_stack.push(rec[new_r][new_c]);
}
}
return res;
}



recursive solution:



int MazeWalkRecur(bool* maze,int row,int col,int cur_r,int cur_c)
{
maze[cur_r*col+cur_c]=true;
if(cur_r==row-1 && cur_c==col-1)
return 1;

int res=0;
for(int i=0;i<4;i++)
{
int next_r=cur_r+neighbor_r[i],next_c=cur_c+neighbor_c[i];
bool flag=false;
if(next_r>=0 && next_r<row && next_c>=0 && next_c<col && maze[next_r*col+next_c]==false)
{
bool* mazeCopy=new bool[row*col];
for(int j=0;j<row*col;j++)
mazeCopy[j]=maze[j];
res+=MazeWalkRecur(mazeCopy,row,col,next_r,next_c);
delete[] mazeCopy;
}
}
return res;
}