Queens on the Chessboard

The eight queens puzzle asks for eight queens to be placed on an ordinary chessboard so that no two of them attack along a row, a column, or a diagonal. A second, older puzzle on the same board asks the opposite kind of question: place as few queens as possible so that every square is either occupied or attacked. The first puzzle is one of pure feasibility, with no quantity to optimise; the second is a genuine optimisation, with an objective to minimise. Both are placement problems on the squares of a board, and both fall to the same modelling instinct: a binary decision for each square, “is a queen here or not,” constrained so that the lines of attack behave as the puzzle requires. The pair is the natural opening to a chapter of chessboard placements, treated as integer programs in the manner of Chlond and Toase’s study in the puzzle column of INFORMS Transactions on Education.

Eight queens: a feasibility program

Max Bezzel posed the eight queens puzzle in $1848$. Franz Nauck published solutions two years later and generalised the question to an $n \times n$ board, and the problem has been a fixture of recreational and computational mathematics ever since. There are $92$ solutions on the standard board, which reduce to $12$ essentially different ones once the symmetries of the square are taken into account.

Variables

Index the rows and columns of an $n \times n$ board by $\{0, 1, \ldots, n - 1\}$. For each square introduce a binary variable $$x_{r c} \in \{0, 1\}, \qquad x_{r c} = 1 \iff \text{a queen stands on row } r,\ \text{column } c.$$

Constraints

A queen attacks along its row, its column, and its two diagonals, so no line of the board may carry more than one queen. The rising diagonals are the squares with $r - c$ constant; the falling diagonals are those with $r + c$ constant. Asking for exactly one queen in every row already forces all $n$ queens onto the board, so the row and column lines take equalities and the diagonals take inequalities: $$\begin{align} \sum_{c = 0}^{n - 1} x_{r c} &= 1, & r &\in \{0, \ldots, n - 1\}, \\ \sum_{r = 0}^{n - 1} x_{r c} &= 1, & c &\in \{0, \ldots, n - 1\}, \\ \sum_{\substack{r - c = d}} x_{r c} &\le 1, & d &\in \{-(n-1), \ldots, n-1\}, \\ \sum_{\substack{r + c = s}} x_{r c} &\le 1, & s &\in \{0, \ldots, 2n-2\}. \end{align}$$ There is nothing to optimise: any feasible point is a placement, and the model is infeasible exactly when no placement exists, which on small boards happens only for $n = 2$ and $n = 3$.

A solver in twenty lines

The integer program goes to CP-SAT verbatim. Each board square is one Boolean variable, and the four families of constraints are four loops.

from ortools.sat.python import cp_model

def place_queens(n):
    m = cp_model.CpModel()
    x = {(r, c): m.NewBoolVar("")
         for r in range(n) for c in range(n)}
    for r in range(n):
        m.Add(sum(x[r, c] for c in range(n)) == 1)
    for c in range(n):
        m.Add(sum(x[r, c] for r in range(n)) == 1)
    for d in range(-(n - 1), n):          # diagup: r - c = d
        m.Add(sum(x[r, c] for r in range(n) for c in range(n)
                  if r - c == d) <= 1)
    for s in range(2 * n - 1):            # diagdown: r + c = s
        m.Add(sum(x[r, c] for r in range(n) for c in range(n)
                  if r + c == s) <= 1)
    solver = cp_model.CpSolver()
    solver.Solve(m)
    return [next(c for c in range(n) if solver.Value(x[r, c]))
            for r in range(n)]

For $n = 8$ the solver returns the placement that puts the queens, row by row, in columns $$0, \; 4, \; 7, \; 5, \; 2, \; 6, \; 1, \; 3,$$ shown in Figure 16.1. Adding the enumerate_all_solutions flag and counting, rather than returning the first solution, recovers all $92$.

Five queens: domination as optimisation

The complementary question is older still. In $1862$ C. F. de Jaenisch asked for the smallest number of queens that, placed on the board, leave no square unguarded: every square must be occupied by a queen or attacked by one. In the language of graph theory this is the domination number of the queens graph, and on the $8 \times 8$ board its value is five. The problem is a set cover, and unlike the eight queens it carries a real objective.

Variables

The decision is the same Boolean placement variable $x_{r c}$ as before, now unconstrained in number.

Coverage constraints and objective

Write $a\bigl((r, c), (i, j)\bigr) = 1$ when a queen on square $(r, c)$ guards square $(i, j)$, meaning the two squares share a row, a column, or a diagonal, with a square counted as guarding itself. Every square $(i, j)$ must be guarded by at least one chosen queen, and the number of queens is minimised: $$\begin{align} \text{minimise} \quad & \sum_{r, c} x_{r c} \\ \text{subject to} \quad & \sum_{r, c} a\bigl((r, c), (i, j)\bigr)\, x_{r c} \;\ge\; 1, \qquad (i, j) \in \text{board}. \end{align}$$ This is the only model in the chapter with an objective function, and it is what makes the five queens a problem of mathematical programming rather than mere constraint satisfaction.

A solver in twenty lines

from ortools.sat.python import cp_model

def min_dominating(n):
    m = cp_model.CpModel()
    x = {(r, c): m.NewBoolVar("")
         for r in range(n) for c in range(n)}
    def guards(r, c, i, j):
        return (r == i or c == j
                or r - c == i - j or r + c == i + j)
    for i in range(n):
        for j in range(n):
            m.Add(sum(x[r, c] for r in range(n) for c in range(n)
                      if guards(r, c, i, j)) >= 1)
    m.Minimize(sum(x.values()))
    solver = cp_model.CpSolver()
    solver.Solve(m)
    queens = [(r, c) for r in range(n) for c in range(n)
              if solver.Value(x[r, c])]
    return len(queens), queens

The model confirms that four queens can never cover the board and that five can. One minimum cover it returns is $$(0, 0), \; (0, 3), \; (0, 6), \; (3, 5), \; (6, 3),$$ drawn in Figure 16.2, where a small dot marks every guarded square and the five copper discs mark the queens. Three of the five queens sit on the top row and so attack one another. That is allowed here, and it is the sharp contrast with the eight queens: domination places no premium on the queens being mutually non-attacking. Demanding both at once, a smallest set of queens that dominates the board and is itself non-attacking, is the independent domination number, which on the $8 \times 8$ board also equals five.

The general board

Both models take the board size $n$ as a parameter, so the same code answers the generalised questions. Non-attacking placements exist for every $n \ge 4$ and for $n = 1$, and fail only for $n = 2$ and $n = 3$; the number of placements is the sequence $$1, \; 0, \; 0, \; 2, \; 10, \; 4, \; 40, \; 92, \; 352, \; 724, \; \ldots$$ for $n = 1, 2, 3, \ldots$, with no known closed form. The domination numbers of the queens graph begin $$1, \; 1, \; 1, \; 2, \; 3, \; 3, \; 4, \; 5, \; 5, \; 5, \; \ldots,$$ and although they have been tabulated far beyond the board sizes a solver can reach directly, no formula valid for all $n$ is known. The two questions, packing queens so that none attack and covering the board with as few as possible, are the independence and domination numbers of one and the same graph, and the chessboard is the smallest arena in which the difference between the two is on plain view.

Sources. The chessboard placements treated here as integer programs follow Martin J. Chlond and Cath M. Toase, IP Modeling of Chessboard Placements and Related Puzzles, INFORMS Transactions on Education volume $2$, number $2$ ($2002$), the article that opened the journal’s long-running puzzle column to chess problems. The eight queens puzzle is due to Max Bezzel ($1848$), with the first published solutions and the generalisation to $n$ queens by Franz Nauck ($1850$); the early history, including the persistent misattribution to Gauss, is documented by Paul J. Campbell, Gauss and the Eight Queens Problem: A Study in Miniature of the Propagation of Historical Error, Historia Mathematica volume $4$ ($1977$), pages $397$–$404$. The minimum-domination question was posed by C. F. de Jaenisch in his Traité des applications de l’analyse mathématique au jeu des échecs ($1862$) and revisited by W. W. Rouse Ball in Mathematical Recreations and Problems of Past and Present Times ($1892$), the first-edition title of the book later known as Mathematical Recreations and Essays. The counts of $n$-queens solutions are OEIS sequence A000170; the domination numbers of the queens graph are OEIS sequence A075458. The queens domination number for general $n$ remains an open problem, surveyed in the literature on domination in graphs.