Maze solving in C-CodePudding

I'm working on a maze solving algorithm in C but having some output not expected, here's my code:

#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 endX = 5;
int endY = 4;
int startX = 0;
int startY = 0;
//function prototype
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

int main()
{
    int maze[N][N] = {{1,0,0,0,0,0},
                      {1,1,1,1,1,0},
                      {0,1,0,0,0,0},
                      {0,1,0,0,0,0},
                      {1,1,1,0,1,1},
                      {0,0,1,1,1,0}};
 
    mazeGo(maze);
    return 0;
}

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

I am expecting an output like this:

 1  0  0  0  0  0
 1  1  0  0  0  0 
 0  1  0  0  0  0 
 0  1  0  0  0  0 
 0  1  1  0  1  1 
 0  0  1  1  1  0

But the result is:

 1  0  0  0  0  0
 1  1  0  0  0  0 
 0  1  0  0  0  0 
 0  1  0  0  0  0 
 0  1  1  0  0  0 
 0  0  1  1  1  0

And if I set the endX and endY (the position of goal) to (4,4), it works:

 1  0  0  0  0  0 
 1  1  0  0  0  0 
 0  1  0  0  0  0 
 0  1  0  0  0  0 
 0  1  1  0  1  0 
 0  0  1  1  1  0

But if I set endX to 0 and endY to 1 the program run but print nothing. May I ask that where have I made the mistake?

CodePudding user response：

Below is a corrected version of your code and it gives the expected output. Just a few lines have changed. You can see them with a diff utility. The main idea is that once a spot is occupied, it is no longer safe, so you should keep track of occupied spots and restore them if needed. Also, endY and andX must have been swapped.

#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 endY = 5;
int endX = 4;
int startX = 0;
int startY = 0;
//function prototype
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);

int main()
{
    int maze[N][N] = {{1,0,0,0,0,0},
                      {1,1,1,1,1,0},
                      {0,1,0,0,0,0},
                      {0,1,0,0,0,0},
                      {1,1,1,0,1,1},
                      {0,0,1,1,1,0}};
 
    mazeGo(maze);
    return 0;
}

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

CodePudding user response：

The other answer probably works, but two quick things with this part of the code:

        //try move right
        if (solveMazeUtil(maze, x   1, y, sol) == true)
            return true;
        //try move down
        if (solveMazeUtil(maze, x, y   1, sol) == true)
            return true;
        //try move left
        if (solveMazeUtil(maze, x - 1, y, sol) == true)
            return true;
        //try move up
        if (solveMazeUtil(maze, x, y - 1, sol) == true)
            return true;
        // If none of the above movements work then unmark x, y
        else
        sol[x][y] = 0;
        return false;

First, the else should have brackets since it is a multiline statement. There's another return false below it, so it's redundant without brackets.

Second, the solveMazeUtil() function gets called, then returned before checking the if statement. So for example, you go from (0,0) to (1,0) to (2,0) but there's no 1 at (2,0), then back up and go back to (1,1).