Proposed by Bilal Syed Hussain


Can $n$ queens (of the same colour) be placed on a $n\times n$ chessboard so that none of the queens can attack each other?

In chess a queen attacks other squares on the same row, column, or either diagonal as itself. So the $n$-queens problem is to find a set of $n$ locations on a chessboard, no two of which are on the same row, column or diagonal.

solution to 4-queens
A solution to 4-queens

A simple arithmetical observation may be helpful in understanding models. Suppose a queen is represented by an ordered pair (α,β), the value α represents the queen’s column, and β its row on the chessboard. Then two queens do not attack each other iff they have different values of all of α, β, α-β, and α+β. It may not be intuitively obvious that chessboard diagonals correspond to sums and differences, but consider moving one square along the two orthogonal diagonals: in one direction the sum of the coordinates does not change, while in the other direction the difference does not change. (We do not suggest that pairs (α,β) is a good representation for solving.)

The problem has inherent symmetry. That is, for any solution we obtain another solution by any of the 8 symmetries of the chessboard (including the identity) obtained by combinations of rotations by 90 degrees and reflections.

The problem is extremely well studied in the mathematical literature. An outstanding survey from 2009 is by Bell & Stevens [Bell20091].

See below for discussions of complexity problems with $n$-Queens. For closely related variants without these problems see n-Queens Completion Problem and Excluded Diagonals n-Queens Problem, [prob079], and Blocked n-Queens Problem, [prob080].


Some care has to be taken when using the $n$-queens problem as a benchmark. Here are some points to bear in mind: