Thread: 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 (:

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 [:

Originally Posted by gavra

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?

Originally Posted by iMalc

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.

Originally Posted by tabstop

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?

Originally Posted by eXeCuTeR

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.

Originally Posted by Adak

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)..

Originally Posted by eXeCuTeR

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.

Originally Posted by Adak

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 (:

Originally Posted by gavra

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.

[=

"else return 0;"