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 $r$-th queen, we methodically try all $n$ ...