Understanding backtracking (maze algorithm)

Question

I am trying to understand recursive backtracking by creating an algorithm that finds a way out from a maze. So this is my "backtracking" logic:

1) Identify all open locations from current location that you haven't been to before ex: up, down. (left and right may be blocked by a wall or might have been visited before)

2) If amtOfOpenLocations >= 1 choose a random openLocation and move there.

3) (Recursive call) If nothing went wrong repeat #1 until a path out, or base case, is reached.

4) If amtOfMoveLocations < 1 step back through each move made until one of those moves has an available move location that is other than any of the moves already made. Repeat steps 1-3.

So my first question is: Is this a correct implementation of a backtracking algorithm?

If my logic is correct here is my next question:

So basically what I do is I keep checking locations other than the ones already made until I find a way out. When I find a way out I ignore all other possible moves and return the solution. If, for example, I am in location (4,4) and I have locations (4,3), (4,5), (5,4), (3,4) all available as openLocations do I make 4 recursive calls to each one of those locations or do I simply make one recursive call to anyone of them and test each location one by one?

My book says "If you are not at an exit point, make 4 recursive calls to check all 4 directions, feeding the new coordinates of the 4 neighboring cells."

An answer on stackoverflow about a similar problem says: "multiple moves per iteration...is wrong" So because of this I am confused. Is my book wrong or what?

Lastly what would be the optimal way to prevent locations that I already checked before? My idea is to keep a temporary array that has all visited locations marked by "!" and my getMoveLocations() method would avoid any cell with an "!". Is there a better way to do this or is my way acceptable?

Answer 1

I'll try to walk through all points:

1. The outline of your algorithm looks correct. The first step assures that you won't run into an infinite regression as you try only unvisited locations. As long as you have locations to try, you move on. On step no. 3 the recursive descent happens. Step no. 4 is your base case on the recursive function. This should be tested at first, as if it is true, you have to exit the function immediately. Therefore it "abandons each partial candidate ("backtracks") as soon as it determines that it cannot possibly be completed to a valid solution." (from Wikipedia).
   By randomly picking a new openLocation you also make it non-deterministic, but still determined. It's a kind of a randomized one.

2. Do you make 4 recursive calls to each one of those locations or do you make one recursive call to anyone of them and test each location one by one? Well...you do the latter, test each location after another in your "tree" of combinations. Backtracking basically walks a tree of possible combinations and goes down to the solution, if it is stuck, it goes upward. Let's call a horizontal section of that tree a layer.
   Your book implements it slightly different that you do. While you have a list of locations you can visit, the authors of your book don't seem to. They will try all four direct neighbours of a position, if it's a wall, "something went wrong" (step 3) and they track back. In that case they won't need a list, just four recursive calls, one after the other. Meanwhile you pick a random item from a list of possible locations, which are computed beforehand for the current cell. Please make sure, that you don't recompute that list each time you get back from a recursive descent. In order to make those lists permanent and just updating them, they shall not be in the recursive function, but precomputed before you start the backtracking, then updating them on each step.

3. Either try it without that list, like the authors of the book, or use the array, which is the right approach. I'd recommend a stack data structure, so you can simply pop out a new location, until it's empty.

Answer 2

Is this a correct implementation of a backtracking algorithm?

Yes, it looks fine.

Moving in a random direction might add complexity to your code though. Not much, if done right, but still a bit more complex than deterministically moving up, down, left, then right, for example.

Also - step 1 as a separate step is probably overkill if you only have 4 directions - just looping over all 4 directions (either deterministically, or by adding them all to a list and randomly picking one and removing it until the list is empty) and then doing a visited / blocked check before the recursive call should be much simpler.

Do I make 4 recursive calls to each one of those locations or do I simply make one recursive call to anyone of them and test each location one by one?

I'm not sure what you mean by the second part. (In Java) recursive calls appearing consecutively in code gets executed in series. You'd have a recursive call for each of them (how will you visit 4 locations with 1 call?).

An answer on stackoverflow about a similar problem says: "multiple moves per iteration...is wrong"

That just sounds like the ramblings of a misguided user.

There's some sense to the basic idea though - with the iterative version, you enqueue many moves in an iteration, but you only perform one per iteration (where you pop). With the recursive version, it's a bit less obvious.

Take a look at the depth-first search pseudo-code on Wikipedia, which clearly makes multiple recursive calls / enqueues multiple moves per iteration:

Recursive:
1  procedure DFS(G,v):
2      label v as discovered
3      for all edges from v to w in G.adjacentEdges(v) do
4          if vertex w is not labeled as discovered then
5              recursively call DFS(G,w)

Iterative:
1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v ← S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

What would be the optimal way to prevent locations that I already checked before?

Your approach isn't bad, but a more natural approach is to use an array of boolean, although, last time I checked, that isn't particularly memory efficient. The most memory efficient would be a BitSet, although the code for that would be slightly more complex.