The N-Queens Problem & Backtracking

Suppose you are trying to accomplish a task where you must make several choices. Some collections of these choices will result in a failed task, while other collections result in an accomplished task.

If one simply searches through all possible collections of choices looking for which ones are successful (i.e., the "brute force" method), the number of possibilities one needs to examine often grows exponentially with the size of the problem!

As an example of this, consider the N-queens problem:

Place N queens on an N x N chessboard so that no two queens attack each other --
that is to say, no two queens share the same row, column, or diagonal.

In a $4 \times 4$ board, we have to choose positions for 4 identical queens from $16$ different possible squares. This can be done in $${}_{16}C_{4} = \frac{16 \cdot 15 \cdot 14 \cdot 12}{4 \cdot 3 \cdot 2 \cdot 1} = 1820 \textrm{ ways}$$

However, for an $8 \times 8$ board, we have to choose positions for $8$ identical queens from $64$ different squares, which can be done in ${}_{64}C_{8} = 178462987637760 \textrm{ ways}$!

We can tighten this up quite dramatically by enforcing one queen in each row through the use of $8$ nested loops as shown below:

for (int i=0; i < 8; i++) {
for (int j=0; j < 8; j++) {
for (int k=0; k < 8; k++) {
for (int l=0; l < 8; l++) {
.
.
for (int p=0; p < 8; p++) {
//check validity of (i,j,k,l,…,p);
}
.
.
}
}
}
}


Using such nested loops, we would only have to look at $4^4=256$ configurations for a $4 \times 4$ board and $8^8$ configurations for a $8 \times 8=16777216$ board -- but this is still far, far too many!

We need a better way...

One such better way is through the use of a backtracking algorithm. In a backtracking algorithm, one incrementally builds candidates to the solution(s) and abandons partial candidates (backtracks) as soon as it is determined they cannot possibly be valid solutions.

For the N-Queens problem, one way we can do this is given by the following:

1. For each row, place a queen in the first valid position (column), and then move to the next row
2. If there is no valid position, then one backtracks to the previous row and try the next position
3. If one can successfully place a queen in the last row, then a solution is found. Now backtrack to find the next solution

Using a Stack for Backtracking in the N-Queens Problem

Recall that each queen must be on a different row in the N-Queens problem. Given this, we shall attempt to put queens on the board one row at a time starting with row 0.

We can use a stack to indicate the positions of the queens. Importantly, notice that we only have to put the column positions of the queens on the stack. We can determine each queen's coordinates given only the stack. We simply combine the position of an element in the stack (the row) with the value of that element (the column) for each queen. Two examples of this are shown below:

* * * *                           |    * * Q *     2           (3,2)
* Q * *      1        (2,1)       |    Q * * *     0           (2,0)
* * * Q      3        (1,3)       |    * * * Q     3           (1,3)
Q * * *      0        (0,0)       |    * Q * *     1           (0,1)
stack      queen       |              stack         queen
coordinates    |                         coordinates


Starting with a queen in the first row, first column (represented by a stack containing just "$0$"), we search left to right for a valid position to place another queen in the next available row.

• If we find a valid position in this row, we push this position (i.e., the column number) to the stack and start again on the next row

• If we don't find a valid position in this row, we backtrack to the previous row -- that is to say, we pop the col position for the previous row from the stack and search for a valid position further down the row

Note, when the stack size gets to $n$, we will have placed $n$ queens on the board, and therefore have a solution.

Of course, there is nothing that requires there be only one solution. To find the rest, every time a solution is found, we can pretend it is not a solution, backtrack to the previous row, and proceed to find the next solution.

Ultimately, every position in the first row will be considered. When there are not more valid positions in the first row and we need to backtrack, that's our cue that there are no more solutions to be found. Thus, we may stop searching when we try to pop from the stack, but can't as it is empty.

Putting all this into pseudo-code form, we have the following algorithm...

Create empty stack and set current position to 0

Repeat {

loop from current position to the last position until valid position found //current row

if there is a valid position {
push the position to stack, set current position to 0 // move to next row
}

if there is no valid position {
if stack is empty, break // stop search
else pop stack, set current position to next position // backtrack to previous row
}

if stack has size N { // a solution is found
pop stack, set current position to next position // backtrack to find next solution
}

}