Thread: Having a significant trouble

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    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.

  2. #2
    Registered User
    Join Date
    Mar 2010
    Posts
    582
    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.

  3. #3
    Registered User
    Join Date
    Feb 2013
    Location
    Sweden
    Posts
    89
    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.

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,612
    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.

  5. #5
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by whiteflags View Post
    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..!!

  6. #6
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by smokeyangel View Post
    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.

  7. #7
    Registered User
    Join Date
    Mar 2010
    Posts
    582
    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.

  8. #8
    Registered User
    Join Date
    Mar 2010
    Posts
    582
    Ah, never mind, I see you've got another thread open about compiler errors. You really should post what the error messages are!

  9. #9
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by smokeyangel View Post
    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.

  10. #10
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by smokeyangel View Post
    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.

  11. #11
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by smokeyangel View Post
    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 -.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Any significant Big Endian Machines?
    By abachler in forum Tech Board
    Replies: 9
    Last Post: 01-29-2009, 01:53 PM
  2. Significant Digits
    By strokebow in forum C++ Programming
    Replies: 1
    Last Post: 10-23-2008, 04:30 AM
  3. significant numbers
    By Chaplin27 in forum C++ Programming
    Replies: 9
    Last Post: 04-04-2005, 05:01 PM
  4. Significant Figures and Chemistry
    By Korn1699 in forum C++ Programming
    Replies: 3
    Last Post: 11-20-2001, 10:37 AM