Backtracking Example - The N Queens Problem

The prototypical backtracking problem is the classical n Queens Problem, first proposed by German chess enthusiast Max Bezzel in (under his pseudonym “Schachfreund”) for the standard 8 x 8 board and by François-Joseph Eustache Lionnet in for the more general n x n board. The problem is to place n queens on an n x n chessboard, so that no two queens are attacking each other.

For readers not familiar with the rules of chess, this means that no two queens are in the same row, the same column, or the same diagonal.

Figure 1: Gauss’s first solution to the 8 queens problem, represented by the array [5, 7, 1, 4, 2, 8, 6, 3]

Figure 1: Gauss’s first solution to the 8 queens problem, represented by the array [5, 7, 1, 4, 2, 8, 6, 3]

Gauss’s letter described the following recursive strategy for solving the n-queens problem; the same strategy was described in by the French recreational mathematician Édouard Lucas, who attributed the method to Emmanuel Laquière. We place queens on the board one row at a time, starting with the top row. To place the rth queen, we methodically try all n squares in row r from left to right in a simple for loop. If a particular square is attacked by an earlier queen, we ignore that square; otherwise, we tentatively place a queen on that square and recursively grope for consistent placements of the queens in later rows. The pseudo code below shows an algorithm, which recursively enumerates all complete n-queens solutions that are consistent with a given partial solution. Following Gauss, we represent the positions of the queens using an array Q[1 .. n], where Q[i] indicates which square in row i contains a queen. When PlaceQueens() is called, the input parameter r is the index of the first empty row, and the prefix Q[1 ..r-1] contains the positions of the first r-1 queens. In particular, to compute all n-queens solutions with no restrictions, we would call PlaceQueens(Q[1 .. n], 1). The outer for-loop considers all possible placements of a queen on row r; the inner for-loop checks whether a candidate placement of row r is consistent with the queens that are already on the first r-1 rows.

PlaceQueens(Q[1 .. n], r):
    if r = n + 1
        print Q[1 .. n]
    else
        for j = 1 to N
            legal = TRUE
            for i = 1 to r-1 
                if (Q[i] = j) or (Q[i] = j + r-i) or (Q[i] = j-r + i)
                    legal = FALSE

            if legal
                Q[r] = j
                PlaceQueens(Q[1...n], r+1) // Recurse

Figure 2: The complete recursion tree of Gauss and Laquière’s algorithm for the 4 queens problem.

Figure 2: The complete recursion tree of Gauss and Laquière’s algorithm for the 4 queens problem.

Let’s explain it in a different way:

Since there must be exactly one queen in each column of the board, and exactly one queen in each row, every queen must be in its own unique row and column. We arbitrarily use the columns of the board to organize the search. Assume the columns are numbered 1 to 8 . Try to think recursively now. Imagine that you have placed queens on the board already and that the queens that have been placed so far cannot attack each other. In other words, so far the queens on the board are a potential solution. Initially this is true because no queens are on the board. You have been placing the queens on the board by putting them in successive columns. Now suppose further that you have a means of checking, for any given potential position in which you want to place the current queen, whether doing so would put it under attack by one of the queens already on the board. The task at the moment is to place the queen in the current column, so you try each row position in that column to see if it leads to a solution. If there is a row that is safe in this column, then you place the queen and recursively advance to the next column, trying to place the next queen there, unless of course you just placed the 8 th queen, in which case you found a solution. However, if there is no row in the current column that is safe for the queen, then you have to backtrack - you have to go back to the queen you placed in the preceding column and try a different row for it, repeatedly if necessary, until it is safe, applying this same recursive strategy there. If you backtrack to the very first queen and cannot find a row for it, then there is no solution to this problem.

The following pseudocode function implements this strategy and is a good example of a backtracking algorithm.

bool placeQueens(int current column, int current row) {
  // Base case. Try to place Queen in a column after end of board
  // if we reach here it means we placed all queens on board
  if (Current Column >= 8) {
    successfully placed all queens so exit with success
  }
  bool isQueenPlaced = false;
  while (Queen is not placed in current Column &&
    Current Row < 8) {
    // If the queen can be attacked in this position, then
    // try moving it to the next row in the current column.
    if (isUnderAttack(current row, current column))
      current row = current row + 1;
    else {
      // Queen is not under attack so this position is good.
      // Advance to next column and try starting in row = 0
      isQueenPlaced = placeQueens(current column + 1, 0);
      // If it wasn't possible to put the new Queen in the next
      // column, backtrack by deleting the new Queen and
      // removing the last Queen placed and moving it down one row.
      if (!isQueenPlaced)
        current row++;
    } // end if
  } // end while
  return isQueenPlaced;
} // end placeQueens

Summary

Backtracking algorithms are commonly used to make a sequence of decisions, with the goal of building a recursively defined structure satisfying certain constraints.

Often (but not always) this goal structure is itself a sequence. Here, for the n-queens problem, the goal is a sequence of queen positions, one in each row, such that no two queens attack each other. For each row, the algorithm decides where to place the queen.

In each recursive call to the backtracking algorithm, we need to make exactly one decision, and our choice must be consistent with all previous decisions. Thus, each recursive call requires not only the portion of the input data we have not yet processed, but also a suitable summary of the decisions we have already made. For the sake of efficiency, the summary of past decisions should be as small as possible. For the n-queens problem, we must pass in not only the number of empty rows, but the positions of all previously placed queens. Here, unfortunately, we must remember our past decisions in complete detail.


Licenses and Attributions


Speak Your Mind