Thread: Recursive Solution to Any Maze And Stack Overflow Problems

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.

[edit]
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.