maze solver algorithm...

[yashitkumarsingh]

plz people help me out .... i just wanna know a basic algorithm for maze solving with program.... plz give ideas on both shortest path and quickest path...

 

[jpanhalt]

There are different types and configurations of mazes. For example, in some it is to reach a certain position, such as the center, in others it is to find an exit. The latter type raises questions like, how many exits are there, and how many entrances.

If you Google on "maze algorithm" you will find those matters discussed i the first few hits, at least I did.

An old and simple algorithm for one entrance, one exit is to always keep one hand on the right (or left) wall. It's not efficient, but it will work. At least the author in Scientific American said it would, but that was many years ago. John

Edit: modified algorithm to be clearer.

 

[richardv2]

Right-Hand Rule has flaws

The right hand rule is excellent for any maze where all walls are connected.
It won't work if there is an island or two in the maze.

An "island" means that one section of the maze has walls that are completely disconnected from the rest of the maze. If the goal is "inside" the island, then right or left hand rules will never get you there, and if you start out inside an island, you can never escape.

All maze contests I've seen are very clear in the description and rules about islands, so it won't be a problem. If you have islands, can't use left-right-hand rules.

And yes, all of the different possibilities and algorithms are covered once you start Googling.

 

[slurp]

It might be worth your while going over to **broken link removed**

These guys are into maze solving and have all sorts both in the forum and linked from the rest of the site.

Best regards,
Colin

--
www.minisumo.org.uk

 

[jpanhalt]

The right hand rule is excellent for any maze where all walls are connected.
It won't work if there is an island or two in the maze.

An "island" means that one section of the maze has walls that are completely disconnected from the rest of the maze. If the goal is "inside" the island, then right or left hand rules will never get you there, and if you start out inside an island, you can never escape.

The potential for islands with the goal contained therein is a valid point. My comment applied to mazes with one entrance and one exit. Whether the rule works in all such cases may boil down to how one defines entrance and exit (e.g., as opposed to goal). Here is a citation from the NY Times (September 6, 1989):

"If however, one starts with the entryway right-hand wall and never breaks contact with it, one will never become attached to an island wall. Thus, those who are consistent in applying Mr. O'Brien's right-hand-wall method, will find it to work without fail. ALEX JOYCE New York, Aug. 15, 1989."

https://query.nytimes.com/gst/fullpage.html?res=950DE4DA1139F935A3575AC0A96F948260

Nevertheless, the main point I was making to the OP was that s/he had to provide more information about the maze before general solutions could be found. Your point about islands, in that context, is obviously an important consideration. John