Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Backtracking for Fun and Profit

November 22, 2011

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video