Problem with Maze Algorithm

Question

I am having a problem with a algorithm that is designed to solve mazes.

I used an algorithm from here.http://www.cs.bu.edu/teaching/alg/maze/

FIND-PATH(x, y)

1. if (x,y outside maze) return false
2. if (x,y is goal) return true
3. if (x,y not open) return false
4. mark x,y as part of solution path
5. if (FIND-PATH(North of x,y) == true) return true
6. if (FIND-PATH(East of x,y) == true) return true
7. if (FIND-PATH(South of x,y) == true) return true
8. if (FIND-PATH(West of x,y) == true) return true
9. unmark x,y as part of solution path
   1. return false

It is a recursive solution , i modified it such that it will continue even after finding exit so that it can find other solutions as well. It seems to work , just that it seems to find half the total number of solutions that i know are possible.

1. if (x,y is goal) return true is changed to return false.

Anyone know what might be the problem with such an algorithm resulting in half the number of total possible solutions? I also have a problem into finding the total number of dead end paths, any suggestions on that?

Answer 1

what seems to be missing is the check if X&Y has already been marked as part of the solution, and if so we abort. (this should be somewhere on point 3.5)

If not a maze with a possible loop somewhere would run indefinately and blow up the stack

by the way, from what I read the algorithm is based on a maze with only 1 solution

R

Answer 2

For the number of dead ends, you need something like that:

3.5 if (North of x,y not open) and (South of x,y not open) and (West of x,y not open) and (East of x,y not open) deadends++

Answer 3

Rather than trying to find one way through the maze, you need to find (and therefore map) multiple ways through the maze.

In order to do this, you need to mark where you've been (on a particular path). If you reach a point you've already been to, you need to flag that route as a dead end.

A recursive function is still the way to go, but make sure that you pass the (placesIhaveBeen) structure through the recursive function.

The recursive loop needs to break when you get to a point where N,S,E,W are all blocked. (You've been there before, you can't go in that direction, it's outside the maze) The recursive loop also needs to break when you reach your target.

If you get to your target - increase a Global Variable by one. If you've nowhere to go - increase your dead-ends by one.

I can't write the pcode for this (it'll take too long), but I believe that the secret is in a function that returns true if N, S, E and W are all blocked.

Addition to my initial answer

With regard to why I treat areas I've been to as "blocked", and why I treat them as dead ends....

      ########
      #      #  
      # #### #
####### #  # #
        #  # #
####### #  # #
      # #### #
      #      #  
      ########

I would classify the above maze part as a dead end, and I can't see how I can identify it as such without treating places I've been to as blocked areas.

I realise that this would cause the following to also show dead ends, but I can't see a way around it.

      #######
      #     #  
      # ### #
####### #G# #
        # # #
####### #   #
      # ### #
      #     #  
      #######

Answer 4

This is a sample maze

####################
#S #  #       #    #
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #   #  #   ###
# ### ### ## # #####
#  #      #       E#
####################