N Queens

Introduction to backtracking

The prototypical backtracking problem is the classical n queens problem, first proposed by German chess enthusiast Max Bezzel in 1848 (under his pseudonym “Schachfreund”) for the standard $8 × 8$ board and by François-Joseph Eustache Lionnet in 1869 for the more general $n × n$ board. The problem is to place $n$ queens on an $n × 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.

Algorithm for the n queens problem

In a letter written to his friend Heinrich Schumacher in 1850, the eminent mathematician Carl Friedrich Gauss wrote that one could easily confirm Franz Nauck’s claim that the “eight queens” problem has 92 solutions by trial and error in a few hours. (“Schwer ist es übrigens nicht, durch ein methodisches Tatonniren sich diese Gewissheit zu verschaffen, wenn man 1 oder ein paar Stunden daran wenden will.”) His description “Tatonniren” comes from the French tâtonner, meaning to feel, grope, or fumble around blindly, as if in the dark.

Gauss’s letter described the following recursive strategy for solving the n-queens problem; the same strategy was described in 1882 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 figure above shows the resulting 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 ...