# Recursive Solution to Any Maze And Stack Overflow Problems

• 12-12-2002
PunkyBunny300
Recursive Solution to Any Maze And Stack Overflow Problems
So I'm trying write a program that will solve any maze using a recursive function. I keep coming close to solving it using a random number generator that tells the program where to move next if there is more than one possible move surrounding the space it is currently at.
My problem is that the program only runs a certain number of times and then gives me an error. So it never reaches the end of the maze. I have a base case for when it reaches the mark that denotes the end of the maze and I also have a function which will back track over spaces already visited if it gets into a space where it no longer has any possible moves. I have been working on this FOREVER and am incredibly frustrated. I've heard that this is because I have too many variables which will overload the stack but I don't know how to reduce the number of variables I feel like I need them all!!!!!!!!!!! Ahh!!!!!!
• 12-12-2002
Nick
One way of solving a maze type problem is to use
a grid[M][N] label it so that grid[M][N] = 1 if it is a wall
grid[M][N] = 0 if empty and grid[M][N] = -1 if it is empty
and visted. Then you basically do a depth first search
by calling the algorithm on adjacent unvisted empty nodes recursivily.
• 12-12-2002
quzah
Re: Recursive Solution to Any Maze And Stack Overflow Problems
Quote:

Originally posted by PunkyBunny300
So I'm trying write a program that will solve any maze using a recursive function. I keep coming close to solving it using a random number generator that tells the program where to move next if there is more than one possible move surrounding the space it is currently at.
For creating use random. Don't use random for solving. To solve, use the "follow the left hand wall" approach.
Code:

```if( north != been_there_done_that )     recursive( here->north ); if( east != been_there_done_that )     recursive( here->east ); if( south != been_there_done_that )     recursive( here->south ); if( west != been_there_done_that )     recursive( here->west ); return at_a_dead_end;```
Basicly, as suggested, make a grid, pick your starting X and Y coords, and apply the above logic. When you get someplace, mark it as "visited". Or as in my example, "been_there_done_that".

Eventually you will map the entire maze, or you will hit the exit before that.

Quzah.
• 12-13-2002
PunkyBunny300
Would either of these solutions solve a maze that was 9 by 9 and had the end point in the center of the maze and no walls except the outer ones in the maze?

This is not the maze that I have to solve but... I was instructed to make my algorithm such that it could solve any maze.
• 12-13-2002
Magos
Either follow a wall, as was suggested, though this will only work if the start and goal are at the perimiter.

Or follow every path, and make a recusive split if the path splits into 2 or more ways. Mark the visited paths so you don't end up in an endless recursion. See picture:
• 12-13-2002
quzah
Quote:

Originally posted by Magos
Either follow a wall, as was suggested, though this will only work if the start and goal are at the perimiter.

Not true. My example will always solve any maze.
Code:

```################### #                # # ####### # ####### #  #    # #    ## # ##### ### # ##### #    #S#  #    # # ### # # ### # ### #  # # #E#  ##  # ###################```
n,n,w,w,e,e,e,e,n,n,
w,w,w,w,w,w,s,s,e,e,w,
w,s,s,e,e,e,e,s,s,n,n,
w,w,w,s,s,e,e,n,n,n,n,
n,n,n,e,e,e,e,e,e,e,e,
e,e,s,s,s,s,w,w,s,s,

Vola. Solved. The code example I gave will *always* solve any maze. If you use more directions of travel, just add them in. Basicly you always follow the same order as you go around any given intersection. You will always eventually reach the end.

That's what I mean by "follow the wall". You actually follow around a set order at every intersection. (IE: "Always turn left".)

Quzah.
• 12-13-2002
Magos
You can't solve my example maze by following the wall. If you follow the left wall, you will end up at the start again (and obviously the same if you follow the right wall). That's because the goal lies in a separate section (notice that the walls in the middle aren't connected to the outer walls, which they are in your maze).

Your solution path isn't 100% correct (you miss some moves) but I noticed that you most of the time walks with the wall at your left side, but at the end suddenly do a right turn...
• 12-13-2002
quzah
Quote:

Originally posted by Magos
Your solution path isn't 100% correct (you miss some moves) but I noticed that you most of the time walks with the wall at your left side, but at the end suddenly do a right turn...
That's what I meant by "following the wall", I should have said, "Always turn left." instead. And yeah, It may be slightly off at the end. I didn't write a program to solve that maze and dump the text. I just typed it in by hand. Basicly you get the idea of how it works. That algorythm, which is the code I provide above, will always solve any maze.

And the only reason that a "follow the wall" will fail is if there is more than one way to solve a maze. Any "perfect", I believe that's the term", maze will be solved by "follow the wall". A non-perfect (ie: more than one patch connects a given cell to another) maze may foil a "follow the wall" algo, like you said:
Code:

```########### #    E    # # ### ### # # #    # # # # #S# # # # # ### # # # #    # # # ####### # #        # ###########```
The "follow the wall" just follows around and around and around the center block. My example would solve it.

Actually, I should have rephrased that, my code actually is "always turn right", so the solution for my example would have been basicly on the first shot. Right turn, right turn, solved.
[/edit]

Quzah.
• 12-13-2002
master5001
ONe major downfall to using recursion to solving a maze (especially if you do as Magos suggested and test every path) is that if you use are solving a decent sized map you will have a stack overflow pretty quick. Unless the maps are always very linear--which defeats the purpose of a maze--the recursion should be used conservitively for this application.
• 12-13-2002
quzah
Quote:

Originally posted by master5001
ONe major downfall to using recursion to solving a maze (especially if you do as Magos suggested and test every path) is that if you use are solving a decent sized map you will have a stack overflow pretty quick. Unless the maps are always very linear--which defeats the purpose of a maze--the recursion should be used conservitively for this application.
Yes and no. With huge mazes, at best you should end up with a number of recursions the same size as the maze. The same basicly holds true with non recursive maze solving. You end up having to have an array or (insert data structure here) the same size as the maze itself.

With most recursive functions, unless you're introducing new variables, you shouldn't have too much stack overhead per recursion:
Code:

```int recurse( Node *room ) {     room->state = USED;     if( room->north != USED )     {         recurse( room->north );     }     if( room->east != USED )     {         recurse( room->east );     }     if( room->south != USED )     {         recurse( room->south );     }     if( room->west != USED )     {         recurse( room->west );     } }```
Incomplete, but close enough to illustrate. The only thing here is the need to backtrack at dead ends. So you'd probably want a parameter to pass as the direction you came from.

But yes, you're right also in that you can run out of stack space on very large mazes.

The benifit of non-recursive solutions, is while it does require basicly a duplicate of the maze (space wise), it isn't allocated on the stack so it avoids overflow.

Quzah.
• 12-13-2002
PunkyBunny300
Code:

```+---+----+---+ |            | |            | |            | +    X      | |            | +            + |            + +--+--+--+--++```
Will your code solve this? with x as the end point? Because I would consider this a maze (and I believe game theory does also)....
And I'm not trying to be nitpicky... well I am... but I really need to be sure that this way will solve any maze... and I don't see how the following the wall or making left hand turns will solve this... I haven't tried coding it for myself yet...
• 12-13-2002
quzah
Of course it will. Apply the logic. The "maze" doesn't need any walls. It doesn't even have to be an array. It could be a list of lists. Whatever, it doesn't matter, so long as you provide the code to "move" in a given direction, and a way to mark that "cell" as having been looked at.

"If ThisDirection is not used, move this way and then mark where we move as used."

That's the basic algo.

Quzah.
• 12-14-2002
Magos
Quote:

Originally posted by quzah
That algorythm, which is the code I provide above, will always solve any maze.
Quote:

And the only reason that a "follow the wall" will fail is if there is more than one way to solve a maze. Any "perfect", I believe that's the term", maze will be solved by "follow the wall". A non-perfect (ie: more than one patch connects a given cell to another) maze may foil a "follow the wall" algo, like you said:
Perhaps you should rephrase the "solve any maze" into "solve any maze that has exactly one solution" then :). In that case I agree with you.

Sorry, but i can be a little pedantic over details sometimes...

Oh, and can you explain how PunkyBunny's maze works, I didn't get it. Is it just a lot of space so 'following a wall' won't do much?
• 12-14-2002
PunkyBunny300
It works! Yay!!! Thanks so much guys!!
• 12-14-2002
quzah
Quote:

Originally posted by Magos
Perhaps you should rephrase the "solve any maze" into "solve any maze that has exactly one solution" then :). In that case I agree with you.

No. My example will solve any maze. The code I provided will solve any maze. Apply the logic.

What I was referring to "Put your left hand on the wall and walk" will only solve mazes where there is no chance of a small circle (example box #2).

The code example I provided is not "walk with your hand on the wall", it is "if there is an open neighboring cell, move there", and it will solve any maze. Period.

There were two concepts discussed:
1) Walk with your hand on the wall.
2) Walk in any given non-used direction, in methodical order. (IE: Always turn left.

The code example is the latter. There is a big difference between walking with your hand on the wall, and always turning a direction, provided it (that cell) hasn't been traveled before.

Quzah.