Thread: Having a significant trouble

I've a serious problem that I'm struggling about not one day or two, about three days respectively or abit more for coding a code to find all possible path of binary maze(just included values 0 and 1, we can just go down/left/up..not diagonally)-tried many methods for coding it and at last I decided a recursion method-I've done with the serious recursion part and all go well -appearing below-, but I dont know why when I compile it, showing there're errors and it gives also a wrong result of, can anyone please help me!!? I'm not meaning forcing you for writing a code, actually the code is already done just need some modifications/tips-as I'm a new programmer and apparently that's considered as a difficult part for noobs, I appreciate your attitudes and cooperation.
Here's the code I've done with:

Code:

#include <stdio.h>#include<string.h>
#define M 4 // M is a symbol of a maze's rows.
#define N 4 // N is a symbok of a maze's verticals. 
// Symbols:
// '1' = open-safe way.
// '0' = closed/blocked.
bool validCell(int maze[M][N], int r_idx, int c_idx);
bool findPath(int maze[M][N], int r_idx, int c_idx, int path[N][N]);
void display_maze(void);
int main(void)
{
    char maze[N][M] = 
    {{ 0,0,1,0 },
                     { 1,1,1,0 },
                     { 0,1,1,0 },
                     { 0,1,1,1 }};
    int i,j;
    //find the path if available//
      if (findPath(maze,0,0,path)) 
      {
          printf("success");}
      else
          printf("failed");
    return 0;
}
// check if we can move to a particular cell//
bool validCell(int maze[M][N], int r_idx, int c_idx) {
   if (r_idx < 0 || r_idx >= M) {
      // invalid M index      
      return false;
   }
   if (c_idx < 0 || c_idx >= N) {
      // inavlid N index
      return false;
   }
   if (maze[r_idx][c_idx] != 1) {
      // cannot move to this cell
      return false;
   }
   return true;
}
/* finds a path from cell (0,0) to cell (M-1,N-1) if a path exists
   (r_idx,c_idx) -> M index and N index of the cell
*/
bool findPath(int maze[M][N], int r_idx, int c_idx, int path[N][N]) {
   if ((r_idx == M-1) && (c_idx == N-1)) {
      // we have reached the last cell
      // this implies we have found a path
      path[r_idx][c_idx] = 1;
      return true;
   }
   if (validCell(maze,r_idx,c_idx)) {
      // cell is valid i.e we can move to the cell
      path[r_idx][c_idx] = 0;


      // recursively check if a path exists from the current valid (safe) cell
      // start checking from cell (r_idx+1,c_idx)
      if (findPath(maze,r_idx+1,c_idx,path)) {
         return true;
      }
      // start checking from cell (r_idx,c_idx+1)
      if (findPath(maze,r_idx,c_idx+1,path)) {
         return true;
      }
      path[r_idx][c_idx] = 1;
      return false;
   }
   return;
}

I really dont know what's wrong with my code!! and I assure that the recursion part is correct absolutely, I deeply think the error in int main body not in the function itselfs.. If you can tell me what should be re-edited in my code to works finely as appreciated very much.

You say you got the wrong result -- I have no idea how you managed to wrestle a compiler into compiling this! It's not that there are a lot of mistakes, just a couple that you really can't away with (like not defining the "path" variable anywhere). I think these should be resolved easily.... and there are a couple of minor bits and pieces that you should be able to spot.

Anyway - so far as I can tell your big mistake is starting your path hunt from 0,0, which has value 0, aka "closed/blocked". So your first check of validCell fails, and imaginary maze man goes nowhere.

I noticed that you're using arr[row][col] rather than arr[col][row]. I wouldn't have even noticed except for that the initialisation of "maze" looked nothing like the display. I know it doesn't actually matter -- but it's a bit easier to fiddle with the maze initialisation when you're not trying to mentally flip it over at the same time.

It looks like you only try moving right and downwards. So a maze where you needed to head in one of the other directions would presumably not be solvable. I don't think you can fit that in a 4x4, but since you made it so easy to grow your maze, unfortunately this one wasn't solved despite being solvable:

Code:

Maze:
1 1 1 1 0 0 
1 0 0 1 0 0 
0 0 1 1 0 0 
1 1 1 1 0 0 
1 0 0 0 0 0 
1 1 1 1 1 1 
failed


Path:
1 1 1 1 0 0 
1 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

I've no idea how you'd solve that.

I'm a beginner myself, but is there really a bool type in C? I know there are libraries for it, but I don't see one included here.

You need to be able to do 2 things, then. You need to compile as C99 and #include <stdbool.h>
Note that if you only do one or the other, you won't get what you want.

And if you can't get what you want, then you will have to make do with the the type-specific difference between 0 and nonzero, as in older days. Nonzero is true, and 0 is false.

Originally Posted by whiteflags

You need to be able to do 2 things, then. You need to compile as C99 and #include <stdbool.h>
Note that if you only do one or the other, you won't get what you want.

And if you can't get what you want, then you will have to make do with the the type-specific difference between 0 and nonzero, as in older days. Nonzero is true, and 0 is false.

I really worked hard and that's what I got at the end for finding the path...

Code:

#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
// Maze size
#define N 9
 
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]);
/* A utility function to print solution matrix sol[N][N] */
void printSolution(int sol[N][N])
{
    int i,j;
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            printf(" %d ", sol[i][j]);
        printf("\n");
    }
}
 
/* A utility function to check if x,y is valid index for N*N maze */
bool isSafe(int maze[N][N], int x, int y, int gone[N][N])
{
    // if (x,y outside maze) return false
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1 && gone[x][y]==0)
        return true;
    return false;
}
/* A recursive utility function to solve Maze problem */
bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N])
{
    // if (x,y is goal) return true
    static int gone[N][N];
    if(x == N-1 && y == N-1)
    {
        sol[x][y] = 1;
        return true;
    }


    // Check if maze[x][y] is valid
    if(isSafe(maze, x, y, gone) == true)
    {
        // mark x,y as part of solution path
        sol[x][y] = 1;
        gone[x][y]=1;
 
        if (solveMazeUtil(maze, x+1, y+1, sol) == true)
            return true;
 
        if (solveMazeUtil(maze, x+1, y, sol) == true)
            return true;
 
        if (solveMazeUtil(maze, x, y+1, sol) == true)
            return true;
 
        if (solveMazeUtil(maze, x-1, y, sol) == true)
            return true;
 
        if (solveMazeUtil(maze, x+1, y-1, sol) == true)
            return true;
 
        if (solveMazeUtil(maze, x-1, y+1, sol) == true)
            return true;
 
        if (solveMazeUtil(maze, x-1, y-1, sol) == true)
            return true;
 
        if (solveMazeUtil(maze, x, y-1, sol) == true)
            return true;
 
        /* If none of the above movements work then BACKTRACK:
            unmark x,y as part of solution path */
        sol[x][y] = 0;
        return false;
    }
 
    return false;
}
 
// driver program to test above function
int main()
{
    int maze[N][N]  =  {
        {1, 1, 1, 0, 0, 0, 0, 0, 0},
        {0, 0, 1, 0, 0, 0, 1, 1, 0},
        {0, 0, 1, 0, 0, 1, 0, 0, 1},
        {0, 1, 0, 0, 1, 0, 0, 0, 1},
        {1, 0, 0, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 1, 0, 0, 1},
        {0, 1, 0, 0, 0, 0, 1, 0, 1},
        {0, 1, 0, 0, 0, 0, 1, 0, 1},
        {0, 0, 1, 1, 1, 1, 0, 0, 1}
    };
 
    solveMaze(maze);
    return 0;
}

I dont know really why it's not working at all, any one can instruct/gimme a hint why this code isn't working? I've done all the recursion steps and other method steps for completely finding the path...but unfortunately when compiles appears some errors..!!

Originally Posted by smokeyangel

You say you got the wrong result -- I have no idea how you managed to wrestle a compiler into compiling this! It's not that there are a lot of mistakes, just a couple that you really can't away with (like not defining the "path" variable anywhere). I think these should be resolved easily.... and there are a couple of minor bits and pieces that you should be able to spot.

Anyway - so far as I can tell your big mistake is starting your path hunt from 0,0, which has value 0, aka "closed/blocked". So your first check of validCell fails, and imaginary maze man goes nowhere.

I noticed that you're using arr[row][col] rather than arr[col][row]. I wouldn't have even noticed except for that the initialisation of "maze" looked nothing like the display. I know it doesn't actually matter -- but it's a bit easier to fiddle with the maze initialisation when you're not trying to mentally flip it over at the same time.

It looks like you only try moving right and downwards. So a maze where you needed to head in one of the other directions would presumably not be solvable. I don't think you can fit that in a 4x4, but since you made it so easy to grow your maze, unfortunately this one wasn't solved despite being solvable:

Code:

Maze:
1 1 1 1 0 0 
1 0 0 1 0 0 
0 0 1 1 0 0 
1 1 1 1 0 0 
1 0 0 0 0 0 
1 1 1 1 1 1 
failed


Path:
1 1 1 1 0 0 
1 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 1 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0

I've no idea how you'd solve that.

I've changed the idea at all...see the last comment below.

The obvious errors would be that you haven't defined sol[][] or solveMaze(). I didn't get anything else.

That aside, this looks good. It solves the maze you've given, and removes markers from dead ends correctly.

What exactly is going wrong on your side? Error messages, bad output?

I guess it still finds one path, even is more than 1 way to get to the end.

Ah, never mind, I see you've got another thread open about compiler errors. You really should post what the error messages are!

Originally Posted by smokeyangel

Ah, never mind, I see you've got another thread open about compiler errors. You really should post what the error messages are!

lol you're missed with me and another one..I just having this thread opened for.

here are the errors of:
error C2061: syntax error : identifier 'solveMazeUtil'
error C2059: syntax error : ';'
error C2059: syntax error : 'type'
error C2061: syntax error : identifier 'isSafe'
error C2059: syntax error : ';'
error C2059: syntax error : 'type'
C2059: syntax error : ';'
error C2059: syntax error : 'type'
warning C4013: 'solveMaze' undefined; assuming extern returning int


what should I write/edit to the code for getting it works? thanks.
I tried but all in vain.

Originally Posted by smokeyangel

The obvious errors would be that you haven't defined sol[][] or solveMaze(). I didn't get anything else.

That aside, this looks good. It solves the maze you've given, and removes markers from dead ends correctly.

What exactly is going wrong on your side? Error messages, bad output?

I guess it still finds one path, even is more than 1 way to get to the end.

the whole problem is error messages, I know the logic of code's finding path is correct..but whatever the error messages prevents me to even what output I would get... if they solved, then all would go well.

Originally Posted by smokeyangel

The obvious errors would be that you haven't defined sol[][] or solveMaze(). I didn't get anything else.

That aside, this looks good. It solves the maze you've given, and removes markers from dead ends correctly.

What exactly is going wrong on your side? Error messages, bad output?

I guess it still finds one path, even is more than 1 way to get to the end.

THANK you buddy very much, I've solved the errrors and the code finds correctly the maze's path..I appreciate your attention/cooperation over here.
well, while I've overcame on finding the path in maze and all go well, I wonder how can I add a function or something to edit to my current code to choose/print the shortest path ever found in maze if there's more than leading paths to the exit, and if there's not then logically the one leading path would be the shortest one.
that's all, and once again appreciate ur patience and bearing myself -new programmer -.