Solving maze using rec'

This is a discussion on Solving maze using rec' within the C Programming forums, part of the General Programming Boards category; A few months ago I was traying to create a "maze solver" but I had a logic mistake so it ...

  1. #1
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265

    Solving maze using rec'

    A few months ago I was traying to create a "maze solver" but I had a logic mistake so it doesn't work.

    The idea is not to solve as a computer it's to solve as a "human being".

    The function:
    Code:
    #define n 10
    #define UP 1
    #define DOWN -1
    #define RIGHT 2
    #define LEFT -2
    
    // Mazes Solver Function //
    int solve (int board[n][n], int i, int j, int direction)
    {
        int m;
        if (i+j == n*2-2)
           return 1;
        
        m=0;
        if (!board[i+1][j] || i == n-1)
         m++;
        if (!board[i][j+1] || j == n-1)
         m++;
        if (!board[i-1][j] || i == 0)
         m++;
        if (!board[i][j-1] || i == 0)
         m++;
        if (m > 2)
         board[i][j] = 0;
    
        if (board[i+1][j] && i<n-1 && (direction*(-1) != UP || !board[i][j]))
         return solve (board, i+1, j, DOWN);
        else if (board[i][j+1] && j<n-1 && (direction*(-1) != RIGHT || !board[i][j]))
         return solve (board, i, j+1, RIGHT);
        else if (board[i-1][j] && i>0 && (direction*(-1) != DOWN || !board[i][j]))
         return solve (board, i-1, j, UP);
        else if (board[i][j-1] && j>0 && (direction*(-1) != LEFT || !board[i][j]))
         return solve (board, i, j-1, LEFT);
        else return 0;
    }
    Can you aim me to find out the problem?

    Thanks (:
    gavra.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Without trying to guess too much about what's in board[x][y], this set of parentheses:
    Code:
    if (board[i+1][j] && i<n-1 && (direction*(-1) != UP || !board[i][j]))
    doesn't seem right. And is the point of these lines to prevent turn-arounds? It looks like it does the opposite -- preventing you from going more than one step in the same direction. For if direction is DOWN, you will fail this first if test and can not keep going down.

    Also: why say "direction*(-1) != UP" instead of "direction != DOWN"?

  3. #3
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    board save the values of the maze (1 = open, 0 = wall).
    Humm what's the problem with the parentheses?
    The point of these line is to choose where to go and "roll back" if we get stack.

    Humm sincerely I don't remember my reasons for everything here (as I said "a few months ago) \:

    And I have noticed that (maybe I had a reason I don't remeber XD but it doesn't seem so right now)

    Thanks for your reply [:
    gavra.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by gavra View Post
    The idea is not to solve as a computer it's to solve as a "human being".
    I think you need to elaborate here.
    What is your criteria for deciding whether the maze appears to be solved by a human vs by a computer?
    If there is only one path from a to b then wont the result look the same no matter how it was solved?
    Do you plan on animating the solving process, or just finding the path?
    Have you heard of the A* algorithm?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Well, maybe the parentheses are right. It looks like the point is to crop off dead-ends one square at a time (for if you had a dead-end you'd put a 0 in the square and stop, so the dead-end is one square shorter the next time you find it, since now the previous dead end is a wall) -- however, I don't see the restart mechanism, since the first time you find a dead end, everything stops; or the "where am I" mechanism to print out the actual solution that you found.

  6. #6
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    The idea is not to solve as a computer it's to solve as a "human being".
    A human-being tries all possible ways (= valid paths) to solve a maze unless he finds a way before he tried all methods to finish the maze, just like the computer; it will try to go through one path, if he fails, he'll go back and try to search the last "junction" (if there is) so he could lead the other way and test it.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Executer, that sounds just like a computer trying to solve a maze!

    I find the OP's description on this matter, completely ambiguous. I'm hoping he'll post up all the code, so we can run it, and really see *what* he's really describing here, and what the program is actually doing (right or wrong).

  8. #8
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    Quote Originally Posted by Adak View Post
    Executer, that sounds just like a computer trying to solve a maze!

    I find the OP's description on this matter, completely ambiguous. I'm hoping he'll post up all the code, so we can run it, and really see *what* he's really describing here, and what the program is actually doing (right or wrong).
    Nope, you cannot predict what is the next trap or w/e, for example, trying solving this: (1 is a valid path, and 0 is a mine which you can't go through)
    You can't also go diagonally as you probably know,
    Code:
    {1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 
    {1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1},
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
    {1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
    {1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    You'll be proven that you have made some mistakes, returned to the last junction and searched for another valid path in this junction, just like the computer does (the difference is that a computer follows on tactic, I mean, he'll search for a path on the right, then on the left, then up, then down or any other combination while the user may not follow one tactic and might change his in every single second). Should I put here my maze-solver so you could see more clearly how a computer solves a maze? (it's written in C# but you can understand it easily)

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So, I'm a human (pretty sure anyway), and to solve that maze, I looked at it and noticed that there was a big long line of 1's on the bottom and that was the only way to get to the "end" at the bottom right and traced it all the way back -- tracing backwards, there's only two decisions to make. But I have eyes, and even though it's not written in the most human-friendly manner, I can spot patterns and see the whole grid at one time, in a way the machine can't. I agree that going forward from the front I would have to trace both paths that branch off at 4 down and 9 over for a little while to see which would work; but there's no need for me to trace forward from the front at all.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I understand how to code up a maze game, Executer.

    I do not understand the OP's description in the first post, nor do I understand his code problem, since I can't see the program's output or step through any of the code.

  11. #11
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    Quote Originally Posted by tabstop View Post
    So, I'm a human (pretty sure anyway), and to solve that maze, I looked at it and noticed that there was a big long line of 1's on the bottom and that was the only way to get to the "end" at the bottom right and traced it all the way back -- tracing backwards, there's only two decisions to make. But I have eyes, and even though it's not written in the most human-friendly manner, I can spot patterns and see the whole grid at one time, in a way the machine can't. I agree that going forward from the front I would have to trace both paths that branch off at 4 down and 9 over for a little while to see which would work; but there's no need for me to trace forward from the front at all.
    Tracing backwards is certainly different, I was talking about tracing forward.
    If the computer will be tracing backwards, I assure you that he would done the same as you did (probably better if you had any mistakes)
    There's no 'human-maze-solving'; the human is just 'brute-forcing' all valid paths unless he found a good path to go through, the computer acts the same.

  12. #12
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    Quote Originally Posted by iMalc View Post
    I think you need to elaborate here.
    What is your criteria for deciding whether the maze appears to be solved by a human vs by a computer?
    If there is only one path from a to b then wont the result look the same no matter how it was solved?
    Do you plan on animating the solving process, or just finding the path?
    Have you heard of the A* algorithm?
    When I said "not as a computer.." I meant that 2 recursively calls mustn't be use.
    Look the same but not the same algorithm.
    Yes, I prefer animating.
    Nope, but I'll.

    Quote Originally Posted by tabstop View Post
    Well, maybe the parentheses are right. It looks like the point is to crop off dead-ends one square at a time (for if you had a dead-end you'd put a 0 in the square and stop, so the dead-end is one square shorter the next time you find it, since now the previous dead end is a wall) -- however, I don't see the restart mechanism, since the first time you find a dead end, everything stops; or the "where am I" mechanism to print out the actual solution that you found.
    You right..
    Stops?


    Quote Originally Posted by eXeCuTeR View Post
    A human-being tries all possible ways (= valid paths) to solve a maze unless he finds a way before he tried all methods to finish the maze, just like the computer; it will try to go through one path, if he fails, he'll go back and try to search the last "junction" (if there is) so he could lead the other way and test it.
    eXeCuTeR? sup?? XD (it's me Fantasma)
    I said what I meant to iMalk.

    Quote Originally Posted by Adak View Post
    Executer, that sounds just like a computer trying to solve a maze!
    I find the OP's description on this matter, completely ambiguous. I'm hoping he'll post up all the code, so we can run it, and really see *what* he's really describing here, and what the program is actually doing (right or wrong).
    I feel like "hating me"? \:
    And the whole code is just a draw function and main ~_~
    It always returns 0 or 1 (I don't remeber)..

    Quote Originally Posted by eXeCuTeR View Post
    Nope, you cannot predict what is the next trap or w/e, for example, trying solving this: (1 is a valid path, and 0 is a mine which you can't go through)
    You can't also go diagonally as you probably know,
    Code:
    {1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}, 
    {1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1},
    {0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0},
    {1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1},
    {1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1},
    {1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
    You'll be proven that you have made some mistakes, returned to the last junction and searched for another valid path in this junction, just like the computer does (the difference is that a computer follows on tactic, I mean, he'll search for a path on the right, then on the left, then up, then down or any other combination while the user may not follow one tactic and might change his in every single second). Should I put here my maze-solver so you could see more clearly how a computer solves a maze? (it's written in C# but you can understand it easily)
    You shouldn't, first cause he won't need your code (without offending) and another reason is that I don't wanna see solutions.

    Quote Originally Posted by Adak View Post
    I understand how to code up a maze game, Executer.

    I do not understand the OP's description in the first post, nor do I understand his code problem, since I can't see the program's output or step through any of the code.
    Still?

    ----------------------

    5 high level programmers (I think) and none of you have noticed this:
    if (!board[i][j-1] || i == 0)
    lol
    But I don't think it's the problem.

    Thanks everyone (:
    gavra.

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    Quote Originally Posted by gavra View Post
    When I said "not as a computer.." I meant that 2 recursively calls mustn't be use.
    Look the same but not the same algorithm.
    Yes, I prefer animating.
    Nope, but I'll.
    I guess we can assume English isn't your first language?
    Perhaps in your original statement you could have mentioned that you simply don't want to use recursion. The good news for you is that A* does not use recursion to examing the possible paths. A reasonable implementation would use a heap. Are you familiar with that data structure?
    5 high level programmers (I think) and none of you have noticed this:
    if (!board[i][j-1] || i == 0)
    lol
    But I don't think it's the problem.

    Thanks everyone (:
    If you think that's your only bug causing buffer overrun then you are sadly mistaken. You have not one, but a total of EIGHT buffer overruns/underruns in your solve function.
    Here's why. Let's take a look at this line:
    Code:
    if (!board[i+1][j] || i == n-1)
    The first thing to be aware of is that arrays start at zero, NOT one, and go up to n-1, NOT n. If n is 3 then the only values you can index the array with are 0, 1 and 2.
    The above statement allows i to equal n-1 and you then add 1 to i where you use it, making it access element n. That's a buffer overrun! First step to correcting this is to change from i == n-1 to i+1 >= n. This also fixed any problem if you were to access more than one element outside the array.
    However there is still a buffer overrun on that same line! The problem is that the left hand side evaluates the position on the board BEFORE the test on the right of the || is done.
    So, to correct the buffer overrun on that line you need to write it like this:
    Code:
    if (i+1 >= n || !board[i+1][j])
    Now that I've corrected that one line of code, I'd recommend that you throw the whole thing away anyway. The best way to solve a maze is to use the A* algorithm. Another option is to use the "keep my left hand touching the wall" technique, though that will not find the endpoint in some cases. Another option, that will always work, is the breadcrumbs approach, where you drop a crumb in each cell you visit and always take the direction with the least crumbs. Least favourable option is of course brute-force as you appear to perhaps have been doing.
    Last edited by iMalc; 07-13-2008 at 01:29 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    eXeCuTeR? sup?? XD (it's me Fantasma)
    Hey

    Get rid of this direction parameter, these 4 conditions and this integer (m), since they are not necessary and just complicates your code and your thinking - try using only 3 parameters, this is way easier.
    Also try to think what exactly happens when the maze cannot be solved (hint: you recursive function will eventually return to maze[0][0] if it'll not find a good path to solve the maze, or in other words, if the function hasn't returned yet) and act accordingly if this happens.
    Your first condition, to check whether we have got to the last cell which is the end of the maze, is good though.

  15. #15
    Registered User gavra's Avatar
    Join Date
    Jun 2008
    Posts
    265
    [=

    "else return 0;"
    gavra.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Having trouble solving maze.
    By eurus in forum C Programming
    Replies: 3
    Last Post: 02-17-2006, 12:52 AM
  2. Maze Solving Cont....PLZ
    By jonnybgood in forum C Programming
    Replies: 30
    Last Post: 11-11-2005, 03:00 AM
  3. Solving A Maze Using C Language!!!!
    By jonnybgood in forum C Programming
    Replies: 6
    Last Post: 11-08-2005, 11:15 AM
  4. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 08:28 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21