# 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.

## Comments:

2011-12-19T07:33:08

Nice discussion of backtracking for n-queens. In fact any computable function can be solved this way. So backtracking, or more generally, search algorithms (for it is sometimes possible to completely eliminate the backtracking by being clever about your pruning of the search space, esp child nodes) are far more applicable to a wide range of problems than is generally recognized. And as fsouthern731 rightly points out you can use symmetry to eliminate large portions of the search space as well as the right kind of data structure to automatically incorporate constraints that your would otherwise have to manually check

Permalink

2011-12-08T15:49:57

Then "use" your data structures training to simplifly the logic required, particularly when attempting to identify the 12 truly unique solutions (duplicate defined as any rotation or flipping of the board that results in a duplicate solution is not unique) -- use a 1x8 array where the array index represents either the horizontal or vertical dimension and the content of each element (1..8) represents the other dimension. That way all row and column conflicts are precluded (cannot happen by definition) in the initial solution. All that is left to check for are diagonal conflicts and, of course, rotating and flipping the board on each axis. The comparison and storage requirements are also simplified to a set of single dimension, 8-element arrays.

Permalink

2011-12-04T10:11:23

As a side note, there is also Alpha Beta Pruning (http://www.cs.ucla.edu/~rosen/..., as a way to "reduce" the search tree.

You are right in comparing it with depth-first graph search. This algorithm, however, has a very "focused" search frontier (http://artint.info/html/ArtInt..., which means it is focused on finding a solution (rather than all). If resources are an issue, parallel execution might be a problem (e.g. having 2 threads analysing 2 sub-trees with no solutions, but we don't know that in advance).

Breadth-first search (http://artint.info/html/ArtInt... is typically used to find all the solutions, so parallel execution seems to be more appropriate in this case (imho), but ... looking forward to see your next post indeed ;)

Permalink

2011-11-23T15:36:33

Cool, looking forward to read your next post :)

Permalink