# Backtracking for Fun and Profit

I remember my first class on data structures. There were two sections offered that quarter. One was taught in Fortran and the other was going to be using this new-fangled language named after a French mathematician. Since I knew Fortran, I tried to get into the first section. No such luck; I had to take the Pascal version. We only had class four days a week, so our professor volunteered to take the off day and do some "catch up" lectures on the programming language.

Anyway, we were studying recursion and I was first introduced to backtracking as an algorithmic strategy. It was like I had been given a glimpse of the Grand Unified Theory. Either that or I was still getting a bit of a contact high from learning a new programming language. I had never seen recursion before this and backtracking looked to be such an elegant solution to many problems.

Just so we're all on the same page, let's have a quick review. Backtracking can be used to find all (or some) solutions to problems that are able to incrementally build candidates to solutions. At each incremental build step, one of several "moves" that can advance the current state of a partial solution closer to a final solution is taken. Whenever a partial solution state is found to be "impossible" or can be shown to not lead to a legal final solution, that partial solution is abandoned. Since it was the previously applied move that led to the invalid state, the backtracking algorithm removes the last added move and tries one of the remaining untested next moves. The step removal aspect of the algorithm is done by returning from a recursive call, erasing any changes that were made to the partial solution state, and putting the next legal move into the current partial solution before calling the recursive function with the new partial solution.

Backtracking is an important tool for solving constraint satisfaction problems, such as crosswords, verbal arithmetic, Sudoku, and many other puzzles. It is often the most convenient (if not the most efficient) technique for parsing, for the knapsack problem and other combinatorial optimization problems. When it is applicable, backtracking is often much faster than brute force enumeration of all complete candidates, since it can eliminate a large number of candidates with a single test.

One of the archetypal problems illustrating backtracking is the N-Queens problem (or, if you only have a standard chess board, the 8-Queens problem). Starting with a board divided into squares with `N`

rows and `N`

columns, the object of the problem is to place `N`

chess queens on the board such that no queen attacks any other queen. For `N==16`

, there are potentially 20,922,789,888,000 (16!) solutions. Because no two queens can occupy the same row or the same column or the same diagonal, the actual number of solutions is much lower than this.

Here is a serial code version to solve the N-Queens problem through backtracking.

void NQueens(char **board, int row, int N) { if (row == N) handleSolution(board); for (int i = 0; i < N; ++i) { board[row][i] = 'Q'; if (stillLegal(board, row)) NQueens(board, row+1, N); board[row][i] = ' '; } return; }

The parameters to `NQueens()`

are a 2-dimensional array of characters, the current row for which a new queen will be added to the partial solution, and the total number of rows in the problem. A placed queen will be represented by the `'Q'`

character being placed in the row and column of the array corresponding to the row and column of the board. For this recursive function, there are two ways to know when further calls to `NQueens()`

are not needed. The first is if `row`

is equal to the number of rows on the board. If this is true, then the proper number of queens has been placed and a solution has been found. In this case, the function `handleSolution()`

is called to do something with the found solution.