Thread: Q: Recursion to find all paths of a maze

Hi all.

I've been working on a program that will find all possible paths through a maze. I can find the way through the maze no problem, but what I want to try to do is to get it to find all the paths so after I can determine which one is the shortest/quickest path. My problem was that with my recursion algorithm I would take the same path over and over (of course).

So, I came up with this type of algorithm:

1.) Go through the maze, storing each 'turn' that is made
2.) Block the 'turn' closest to the end of the maze so you do not repeat that path.
3.) If a dead end is reached, fill the dead end with a wall-type character so you do not continue down that path.

Eventually with this you end up 'closing' each path to be made through the maze. The first time through the maze it works, then the second, but then it just gets all buggy and doesn't work.

I'm not trying to get anyone to write this code for me, because I am doing it mostly out of curiousity. But my question is, am I making it more complicated than it has to be? Or is there a simpler algorithm to solve the problem?

Code:

Example Maze:

O = start
X = end

 ##########
 #        #
 # ## # #O#
 # ## # ###
 # ## # #X#
 # ## ### #
 #      # #
 # # ## # #
 #        #
 ##########

Thanks in advance.