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

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"?

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

Quote:

---

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?

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.

Quote:

---

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.

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

Quote:

---

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

---

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)

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.

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.

Quote:

---

Originally Posted by tabstop

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.

Quote:

---

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.

Quote:

---

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?

Quote:

---

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.

Quote:

---

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

Quote:

---

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.

Quote:

---

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

Quote:

---

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?

Quote:

---

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.

Quote:

---

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.

[=

"else return 0;"