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.