
Re: finite maze solving algorithm
Posted:
Nov 30, 2004 1:22 PM


Michael Michalchik wrote: > I was wondering if anyone knows if all possible topologies of finite > 2d mazes can be solved by a finite algorithm. For example, we know > that all fully connected mazes can be solved by picking a wall and > exhaustively following it. Can a general solution work for all mazes > including the ones that are piecewise disconnected? If this is > possible, is the general solution a solved problem?
Interesting. How are you defining a maze, here? Usually, I think of a maze as just a graph, which you can solve using something simple like depthfirst search, regardless of whether it is planar. It is probably better to think in terms of connectedness of rooms than connectedness of walls.
(I hope I am not being ignorant here, but you seem to be using "topology" and "piecewise disconnected" in strange ways. Obviously if the topological space is disconnected, there will be no path possible between points in different components  in the discrete topology, if you're not there, you can't get there.)
HTH  Kevin

