Why does this C maze solving algorithm give an unexpected result?-CodePudding

I have created a maze-solving algorithm like this:

#include <stdio.h>
 
// Maze size
#define N 6

//define boolean
#ifndef MYBOOLEAN_H
#define MYBOOLEAN_H

#define false 0
#define true 1
typedef int bool;
#endif

int startX = 0;
int startY = 0;

//function prototype
bool solveMazeUtil(char maze[N][N], int x, int y, char sol[N][N]);

int main()
{
    char maze[N][N] = {{'.','#','#','#','#','#'},
                       {'.','.','.','.','.','#'},
                       {'#','.','#','#','#','#'},
                       {'#','.','#','#','#','#'},
                       {'.','.','.','#','.','G'},
                       {'#','#','.','.','.','#'}};
 
    mazeGo(maze);
    return 0;
}

//print the solution
void printSolution(char sol[N][N])
{
    for (int i = 0; i < N; i  ) {
        for (int j = 0; j < N; j  )
            printf(" %c ", sol[i][j]);
        printf("\n");
    }
}
 
//checking if in correct path
bool isSafe(char maze[N][N], int x, int y)
{
    // if not, return false
    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == '.')
        return true;
    else
        return false;
}
 
bool mazeGo(char maze[N][N])
{
    char sol[N][N] = {{'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'}};
 
    if (solveMazeUtil(maze, startX, startY, sol) == false) {
        printf("No solution");
        return false;
    }
 
    printSolution(sol);
    return true;
}
 
//actual maze solving
bool solveMazeUtil(char maze[N][N], int x, int y, char sol[N][N])
{
    // if (x, y) is goal return true
    if (maze[x][y] == 'G') {
        sol[x][y] = ' ';
        return true;
    }
 
    // Check if maze[x][y] is valid
    if (isSafe(maze, x, y) == true) {
        // mark x, y
        sol[x][y] = ' ';
        maze[x][y] = '#'; 
        //try move right
        if (solveMazeUtil(maze, x   1, y, sol) == '.')
            sol[x 1][y] = ' ';
            maze[x 1][y] = '#'; 
            return true;
        //try move down
        if (solveMazeUtil(maze, x, y   1, sol) == '.')
            sol[x][y 1] = ' ';
            maze[x][y 1] = '#';  
            return true;
        //try move left
        if (solveMazeUtil(maze, x - 1, y, sol) == '.')
            sol[x-1][y] = ' ';
            maze[x-1][y] = '#'; 
            return true;
        //try move up
        if (solveMazeUtil(maze, x, y - 1, sol) == '.')
            sol[x][y-1] = ' ';
            maze[x][y-1] = '#'; 
            return true;    
        // If none of the above movements work then unmark x, y
        sol[x][y] = '#';
        maze[x][y] = '.'; 
    }
    return false;
}

Which should start from (0,0) and end at G, and I'm expecting an output of

    #  #  #  #  # 
       #  #  #  # 
 #     #  #  #  # 
 #     #  #  #  # 
 #        #       
 #  #           #

But getting a result of

    #  #  #  #  # 
    #  #  #  #  # 
 #  #  #  #  #  # 
 #  #  #  #  #  # 
 #  #  #  #  #  # 
 #  #  #  #  #  #

I've tried to delete the 'return true' in line 101, which makes the program go further but is still not giving the expected output.

Can anyone help me determine where I made the mistake?

CodePudding user response：

There are multiple problems:

the indentation in solveMazeUtil is misleading: use a block delimited by { and } when more than a single statement follows an if, for, while or do statement.
these statements are actually useless once you have found a solution. Just return true if any of the recursive calls returns true.
the recursive calls return true or false, comparing the return value to '.' is incorrect.
avoid tautological statements and expressions such as if (condition) return true; else return false; or if (isSafe(maze, x, y) == true)

Here is a modified version:

#include <stdio.h>

// Maze size
#define N 6

//define boolean
#ifndef MYBOOLEAN_H
#define MYBOOLEAN_H
#define false 0
#define true 1
typedef int bool;
#endif

//function prototype
bool solveMazeUtil(char maze[N][N], int x, int y, char sol[N][N]);
bool mazeGo(char maze[N][N], int startX, int startY);

int main() {
    char maze[N][N] = {{'.','#','#','#','#','#'},
                       {'.','.','.','.','.','#'},
                       {'#','.','#','#','#','#'},
                       {'#','.','#','#','#','#'},
                       {'.','.','.','#','.','G'},
                       {'#','#','.','.','.','#'}};

    mazeGo(maze, 0, 0);
    return 0;
}

//print the solution
void printSolution(char sol[N][N]) {
    for (int i = 0; i < N; i  ) {
        for (int j = 0; j < N; j  )
            printf(" %c ", sol[i][j]);
        printf("\n");
    }
}

//checking if in correct path
bool isSafe(char maze[N][N], int x, int y) {
    // if not, return false
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == '.');
}

bool mazeGo(char maze[N][N], int startX, int startY) {
    char sol[N][N] = {{'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'},
                      {'#','#','#','#','#','#'}};

    if (solveMazeUtil(maze, startX, startY, sol)) {
        printSolution(sol);
        return true;
    } else {
        printf("No solution");
        return false;
    }
}

//actual maze solving
bool solveMazeUtil(char maze[N][N], int x, int y, char sol[N][N]) {
    // if (x, y) is goal return true
    if (maze[x][y] == 'G') {
        sol[x][y] = ' ';
        return true;
    }

    // Check if maze[x][y] is valid
    if (isSafe(maze, x, y)) {
        // mark x, y
        sol[x][y] = ' ';
        maze[x][y] = '#';
        // try all four directions
        if (solveMazeUtil(maze, x   1, y, sol)
        ||  solveMazeUtil(maze, x, y   1, sol)
        ||  solveMazeUtil(maze, x - 1, y, sol)
        ||  solveMazeUtil(maze, x, y - 1, sol)) {
            return true;
        }
        // If none of the above movements work then unmark x, y
        sol[x][y] = '#';
        maze[x][y] = '.';
    }
    return false;
}

CodePudding user response：

There are several problems with your program, but the most significant ones are

solveMazeUtil() tests whether the current position is the goal position without first verifying that it is a valid ("safe") position. This can produce a buffer overrun.
solveMazeUtil() returns either 0 or 1, never '.' (unless your execution character set is highly unusual). Thus, it seems that the several appearances of expressions of the form
```
solveMazeUtil(maze, x   1, y, sol) == '.'
```
should instead be
```
solveMazeUtil(maze, x   1, y, sol) == true
```
. Or simply
```
solveMazeUtil(maze, x   1, y, sol)
```

You appear to have omitted braces around what appear intended to be multi-line if bodies. For example, here:

        if (solveMazeUtil(maze, x   1, y, sol) == '.')
            sol[x 1][y] = ' ';
            maze[x 1][y] = '#'; 
            return true;

... only the sol[x 1][y] = ' '; is guarded by the if statement. The other two are executed unconditionally. Probably you meant this:

        if (solveMazeUtil(maze, x   1, y, sol) == '.') {
            sol[x 1][y] = ' ';
            maze[x 1][y] = '#'; 
            return true;
        }

Note also, however, that you do not need to mark the solution or the maze after return from solveMazeUtil() prior to returning true. They will have already been marked appropriately by the recursive call.

Moreover, note that when solveMazeUtil() visits a position, it tests all possible paths onward from that position. Therefore, it is not necessary ever to test any additional paths through that position. This is an efficiency consideration that doesn't much matter for small mazes, but which might become important for larger ones.