Backtracking searth, pt3

I think I went off on a tangent in my last posts but the basic idea through backtracking search is that the computer is able to know where it's been and where it needs to go. This is where recursion and the stack comes in, mainly.

Whenever a function is called, the variables passed get loaded onto either the stack or into registers, depending on the architecture of the computer. The actual implementation details aren't too terribly important, except that the first function also saves a copy of its registers in the stack space. This DETAIL does become vitally important for recursion to work properly. When you go into recursion, you have to go out eventually. It's like running into a forest. You can only run so far before you start running out.

Most programmers know that, if you declare a variable called foo, set it to contain the value "5" as a number, and call another function, foo still contains 5 when you come back. However, things tend to get a little trickier when you're dealing with recursion, because then a function is calling itself. Which means you now have to think of foo as a local variable but also as a local variable that may have a completely different value. They're named the same, they come from the same function, so recursion is a little tricky to think about sometimes, especially when going out of it.

Going out of recursion means the calls you have made are returning, and control is returning to functions that made these calls. These functions and their variables sit lower on the stack, and as control is returned, the functions will keep doing what they need to do with the variables they had started with, despite any changes other function calls might have made.

This is assuming the variables were passed by value, of course. This isn't something you want to do with large objects, and sometimes, you want recursive algorithms to manipulate the data they are passing to copies of themselves, since the whole idea is to break down a problem into parts. Merge sort is a good example. Break an unsorted list into multiple unsorted lists until they are of a certain size, and then sort those lists, and then merge the smaller sorted lists into one big list.

Now what do you do if you want to manipulate the data passed, but you want to also don't want to make the changes permanent? We could do pass-by-value, but what if it's a big object, or a big array? It is also possible to do pass-by-reference and just undo what we did after the function call, and this is generally how a backtracking search gets implemented.

First, you find a partial solution. In the case of the n-queens problem, this can be an empty board. An empty board can be considered a partial solution in much the same way that, if you have an idea of something, then you have a partial solution to that problem (no idea -- nowhere near to getting a solution). From there, you place your queen, make a call, try to place another queen, and if that doesn't work, you return the control to the function that called you and let him clean up the placement of his queen and try again. This would just look like the opposite of what you just did before you make another call. I should probably point out that backtracking search requires a loop to make this possible.

Backtracking search doesn't require a computer though, of course. If you got stuck in a minotaur's labyrinth you would be able to find your way out if you were able to keep track of where you need to look, and where you've already looked.

Backtracking search, pt2

The way we would tell a computer to solve this problem is through an algorithm called backtracking search.

Understanding the algorithm requires some knowledge of recursion, and a little bit of intuition about what is going on.

Recursion breaks down a problem into smaller pieces of itself, as is the case for Binary Search, or when previous computations of the problem must be known for further computations of the problem, as is the case with Fibonacci. To do this, recursion calls itself. This saves a copy of the old function on the stack, and, when the new function exits, the old function continues. This functionality is what allows a backtracking search algorithm to undo what it did and to continue on to finding another possible solution. It is what allows the computer, in the n queens problem described in part 1, to take off the queens it needs to when it has not arrived at a solution (or when it has, and it wishes to search for another solution).

Recursion makes algorithms short and sweet. I had to implement backtracking search, recently, to find the number of solutions to a problem where a spider (or crab, or other kind of actor) can move around a board in 8 directions, and I was tasked to find out how many different ways it could move across a board so that it reaches a finish square and touches all squares once.

The entire code base turned out to be fifty-four lines, but it's fifty-four lines of code that seemed to be doing quite a lot. Some of the boards given by the testing program had around 3,000 solutions. I mean, fifty-four lines just to do all of that!

It's pretty amazing.

Backtracking search, pt1

I give you a puzzle and I tell you that this puzzle has a million solutions to it. Furthermore, I want you to find all one million solutions. How would you accomplish this? It would likely be a very time-consuming task, and there would be well, quite a bit of things to keep track of.

Let's get a little more specific. I have a chessboard, and I want to know how many configurations of queens I can have, so that one queen occupies a row, and no queen is able to attack one another. Let's go a little simpler. I have a chessboard that is 1x1. How many solutions are there? One, and this is a pretty trivial case. There are no solutions for a 2x2 board and there are no solutions for a 3x3 board, but there are two solutions for a 4x4 board.

How would we find them?

Let's start with an empty board.
....
....
....
....

Let's place a queen in the first row, first column.
Q...
....
....
....

Now, let's go to the second row. Since we cannot place a queen in the first or second column, let's place a queen in the third column.
Q...
..Q.
....
....

Now, for the third row. Where can we place a queen?
The first, second, third, and fourth columns are right now. So we must backtrack. We will take off our queens, and start by placing one at the second column.
.Q..
....
....
....

Our next possible place is the fourth column, second row.
.Q..
...Q
....
....

Now, our next possible place is the first column, third row.
.Q..
...Q
Q...
....

Our last place to check is the 3rd column, last row.
.Q..
...Q
Q...
..Q.

And now we have a solution. This took about seven steps. Quite awhile. There is one more solution to a 4x4 board, but it's just a mirror image. I won't get solving this as you should see the pattern.

So, how would we find all solutions for an 8x8 or even an NxN problem set?

With a computer that can do what we did. Of course.