I also assume the rule of "do not include a node in the solution tree if it was already in the tree"? Because that sure helps.
Typically the tree is implicit, and you only construct the parts of the tree you actually visit, often tearing things down as you roll it back.
Your solver keeps track of the current steps along the tree. You probably also want to keep track of what cells you have explored in the maze. If the maze has only #
and characters, use
*
to indicate you have visited the cell in this solver.
You start at some location. If that location is valid, you mark it with a *
so you don't come back to it, and add that location (say, (1,1)
)to your "stack" of your path.
Now, you follow the rules you wrote above. Check the cell under your current location. Is it empty? (not a #
or a *
) If so, recurse, asking if that finds the way out.
If it finds the way out, take the path it found, prepend your current node, and return that path as the way out.
If it does not, search in the next adjacent cell (by the order above).
Finally, wrap the above recursive routine with a function that calls it, then removes the *
marks from the map.
The tree you walk is implicitly coded. Building the tree forces you to visit every node, and you only want to build the parts that you have to.
This can be optimized in a number of ways. You can avoid writing to the map by working on a "ghost" copy of it. You can avoid prepending by passing the stack to the recursive versions, which carefully remove any extra nodes if they fail, and leave them on if they succeed. Or you can use a real stack, and encode the path backwards, with a wrapping function that (after all the work is done) reverses the path so it is in a more conventional order.