CODEWITHSUNDEEP
algorithm
doubleE
doubleE

Reputation: 1063

Maze Solving Algorithm does not work with 4 directions

This is my solution to classic Maze problem. It works perfect if I just allow 2 moves(down or right) and there is a path that can be established using only those 2 moves. However, if I want to allow all 4 possible movements(down,right,left,up) the program never give a solution(Seems the recursive stack grows and overflows eventually). I tried with mazes as small as 4x4, but no success. Can you help me? # is blocked, . is free. For increasing the allowable movements, increase or decrease the #define MOVES (2) to #define MOVES (4)

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define ROW (10)
#define COL (10)

int start_index[]={0,0};
int end_index[]={9,9};

// char maze[R][C]={ // Can't solve this maze with 4 allowable moves
//     {'.','#','.','.','.','.','.','.','.','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','#','.','#','#','#','#','#','#','.'},
//     {'.','.','.','#','#','#','#','#','#','.'}
// };

char maze[ROW][COL]={ // Can solve this maze with 2 allowable moves
    {'.','.','#','.','.','.','.','.','.','#'},
    {'#','.','.','.','.','.','.','.','.','.'},
    {'#','.','#','.','.','.','.','.','.','.'},
    {'#','.','#','.','.','.','.','.','.','.'},
    {'.','.','.','.','.','.','.','.','#','.'},
    {'.','.','#','.','.','.','.','.','.','#'},
    {'#','.','.','.','#','#','.','.','.','.'},
    {'#','.','#','.','.','#','.','.','.','.'},
    {'.','.','#','.','.','#','.','.','#','.'},
    {'.','.','#','.','.','.','.','.','.','.'}
};

char sol[ROW][COL]={
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
    {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}
};

int move_x[]={0,1,0,-1};
int move_y[]={1,0,-1,0};

#define MOVES (4)

bool is_safe(int x,int y);
bool is_target(int x,int y);
bool solve_maze(int x,int y);
void print_mazes(bool solvable);

int main(){
    printf("\nStarting");
    bool solvable=solve_maze(start_index[0],start_index[1]);
    print_mazes(solvable);
    printf("\nEnd.");
}

bool solve_maze(int x,int y){
    int next_x,next_y;
    static int count=0;
    bool tmp_res=false;
    sol[x][y]='.';
    printf("\n%d: (%d,%d)",count++,x,y);
    for(int i=0;i<MOVES;i++){
        next_x=x+move_x[i];
        next_y=y+move_y[i];
        if(is_safe(next_x,next_y)){
            if(is_target(next_x,next_y)){
                sol[next_x][next_y]='.';
                return true;
                }
            else{
                tmp_res=solve_maze(next_x,next_y);
                if(tmp_res){
                    sol[next_x][next_y]='.';
                    return true;
                }
                else{
                    sol[next_x][next_y]='#';
                }
            }
        }
    }
    return false;
}

bool is_safe(int x,int y){
    if(x<COL && y<ROW && maze[x][y]!='#')
    return true;
    else return false;
}

bool is_target(int x,int y){
    if(x==end_index[0] && y==end_index[1]) return true;
    else return false;
}

// prints the original maze and the solution
void print_mazes(bool solvable){
    printf("\n\n   <<%sSolvable>>",(solvable)? "":"Not ");
        printf("\n   0 1 2 3 4 5 6 7 8 9\t\t   0 1 2 3 4 5 6 7 8 9\n");

        for(int i=0;i<ROW;i++){
            printf("%d: ",i);
            for(int j=0;j<COL;j++)
                printf("%c ",maze[i][j]);

            printf("\t\t%d: ",i);
            for(int j=0;j<COL;j++)
                printf("%c ",sol[i][j]);
        printf("\n");
        }
        printf("   0 1 2 3 4 5 6 7 8 9\t\t   0 1 2 3 4 5 6 7 8 9 \n");
}

Upvotes: 0

Views: 330

Answers (1)

Garrett Gutierrez
Garrett Gutierrez

Reputation: 767

You should mark cells that you have visited as soon as you visit them (rather than at the end, as you do with sol[next_x][next_y]='#'; Your current algorithm has no way of returning if it enters a cell that has already been entered by a frame lower down on the stack, leading to a certain infinite loop (and thus the stack overflow).

Try making the first thing you do in solve_maze be if (sol[x][y]=='#') return false; and the second thing be sol[x][y] = '#';. The first statement:

if (sol[x][y]=='#') return false;

Says "if this cell has been marked as visited, don't revisit it". The second statement:

sol[x][y] = '#';

Says "mark this cell as visited." Alternatively, you can use some character other than '#' to mark cells as visited. I am not sure if that was what you intended '#' to indicate (seems like it was meant to indicate cells that are not on some path to the exit, but in reality in a solvable maze all explorable cells are on some path to the exit).

Upvotes: 2

Related Questions