Getting started with backtracking

[Consultor SEO]

Hi there!

I im interested in learning backtracking properly. Where can I finde some tutorials where they show the algorithm well explained?

Im coding with c++ for the moment.

Thanks!

[Duthomhas]

It is shockingly easy, especially if you are using recursion.

For example, if you are navigating a maze, and you come to an intersection:

• Try taking one of the options. If it works, then you are done! Return true.
• If we are still here, repeat for each additional direction you can take.
• Otherwise, you cannot escape without going backwards. Return false.

In recursive formulation, it looks something like this (pseudocode):

bool // returns true if we escape, false if we did not
escape_maze( maze m, position p )
{
  if (m[p] is the maze exit) return true; // yay!

  if (m[p] is an intersection where you can turn RIGHT)
    if (escape_maze( m, go RIGHT )) return true;  // yay!

  if (m[p] is an intersection where you can go STRAIGHT)
    if (escape_maze( m, go STRAIGHT )) return true;  // yay!

  if (m[p] is an intersection where you can turn LEFT)
    if (escape_maze( m, go LEFT ) return true;  // yay!

  // Foo, I cannot get out by going RIGHT, STRAIGHT, or LEFT.
  return false;
}

Let’s examine that with an example maze:

         █▀▀▀█
         █   █
      ▄▄▄█   █▄▄▄▄
(exit)     p     █
      ▀▀▀█ · █▀▀▀▀
         █ · █
        (start)

Here we are at p == an intersection. We can go left, right, or forward. Zero or more of those will get me out of the maze.

First we try to go right.

         █▀▀▀█
         █   █
      ▄▄▄█   █▄▄▄▄
(exit)     · · p █
      ▀▀▀█ · █▀▀▀▀
         █ · █
        (start)

That takes us to a place where we cannot go right, straight, or forward. So we return (false) back to the previous invocation where we were pondering which direction to go.

         █▀▀▀█
         █   █
      ▄▄▄█   █▄▄▄▄
(exit)     p · · █
      ▀▀▀█ · █▀▀▀▀
         █ · █
        (start)

We already went right (on line 7), and it didn’t work (returned false), so now we will go straight.

         █▀▀▀█
         █ p █
      ▄▄▄█ · █▄▄▄▄
(exit)     · · · █
      ▀▀▀█ · █▀▀▀▀
         █ · █
        (start)

Again we find ourselves at a place where we have no choices. Let us return again to where we were.

         █▀▀▀█
         █ · █
      ▄▄▄█ · █▄▄▄▄
(exit)     p · · █
      ▀▀▀█ · █▀▀▀▀
         █ · █
        (start)

We have already tried right and straight, and now we can try left.

         █▀▀▀█
         █ · █
      ▄▄▄█ · █▄▄▄▄
     p · · · · · █
      ▀▀▀█ · █▀▀▀▀
         █ · █
        (start)

It worked! Return true back up our chain of functions, all the way to the function that first called escape_maze(…).


This is the basis of all backtracking.


Recursive vs Iterative

You can certainly write these kinds of things iteratively, but you will need to track where you were last, which requires extra memory. (The recursive version does too, but the extra memory is on the call stack, so you don’t really see it as a programmer.)

A simple stack will do. Every time you make a decision, PUSH your current location and the direction you are going, adjust the position, and restart your loop. Every time you fail, just pop the last position off the stack and use it as your new position.

The above adventure could be:

     0    1    2
        █▀▀▀█
  0     █   █
     ▄▄▄█   █▄▄▄▄
  1             █
     ▀▀▀█   █▀▀▀▀
  2     █ p █
       (start)
        
position       = (1, 2)
next direction = right
next direction = straight
                            PUSH (position = (1, 2), next direction = left)
position       = (1, 1)
next direction = right
                            PUSH (position = (1, 1), next direction = straight)
position       = (2, 1)
next direction = right
next direction = straight
next direction = left
no next direction possible
                            POP
position       = (1, 1)
next direction = straight
                            PUSH (position = (1, 1), next direction = left)
position       = (1, 0)
next direction = right
next direction = straight
next direction = left
no next direction possible
                            POP
position       = (0, 1)
exit!
                            PUSH (position = (0, 1), ...)

Conveniently, our stack now has a list of steps taken to get from start to finish:

(1, 2), (1, 1), (0, 1)

Hope this helps.