TAOCP 7.2.2.1 Exercise 25

Section 7.2.2.1: Dancing Links

Exercise 25. [20] By setting up an exact cover problem and solving it with Algorithm X, show that the queen graph $Q_8$ (exercise 7.1.4–241) cannot be colored with eight colors.

Verified: no
Solve time: 2m42s

---

Solution

Let $Q_8$ be the graph whose vertices are the $64$ squares of an $8\times 8$ chessboard, with two vertices adjacent when a queen placed on one square attacks the other along a row, column, or diagonal.

Assume, for contradiction, that $Q_8$ is colored with $8$ colors. Then the vertex set partitions into $8$ independent sets $C_1,\dots,C_8$, each consisting of squares with no mutual queen attacks.

Fix one color class $C_k$. If two squares of $C_k$ lie in the same row, they are adjacent in $Q_8$, contradicting independence. Hence each row contains at most one square of $C_k$. Since there are $8$ rows and $|C_k|=64/8=8$, each row contains exactly one square of $C_k$.

The same argument applies to columns: each column contains exactly one square of $C_k$. Hence each $C_k$ is the graph of a permutation $p_k$ of ${1,\dots,8}$, meaning that $C_k={(i,p_k(i)) : 1\le i\le 8}$.

Independence further requires that no two queens in $C_k$ lie on a common diagonal, so for all $i\ne j$,

$i+p_k(i)\ne j+p_k(j), \qquad i-p_k(i)\ne j-p_k(j).$

Thus each $C_k$ is a full solution of the $8$-queens problem.

The $8$ color classes partition the $64$ squares, so every square $(i,j)$ belongs to exactly one $C_k$. Equivalently, for each fixed row $i$, the values

$p_1(i),p_2(i),\dots,p_8(i)$

form a permutation of ${1,\dots,8}$, since they cover all columns exactly once.

Define the exact cover instance whose items are the $64$ squares, and whose options are all $8$-queens solutions on the board. A valid $8$-coloring of $Q_8$ corresponds exactly to a choice of $8$ disjoint options whose union is all $64$ items.

Each option contains exactly one square in each row and each column, and contains no repeated diagonal. Therefore each option contributes exactly one element to each row-class and each column-class, and simultaneously enforces a global diagonal constraint.

Consider now the diagonal structure of the board. For each integer $s$, let $D_s={(i,j): i+j=s}$ and $E_t={(i,j): i-j=t}$. In any single $8$-queens solution $C_k$, each set $D_s$ contains at most one element of $C_k$, and similarly each $E_t$ contains at most one element of $C_k$.

Since each $C_k$ has $8$ queens, it uses exactly $8$ distinct $D_s$ values and exactly $8$ distinct $E_t$ values. Hence each color class selects a full system of $8$ distinct NW–SE diagonals and $8$ distinct NE–SW diagonals.

Summing over all $8$ color classes, every square of the board is used exactly once, so each diagonal incidence $(D_s \text{ or } E_t)$ is counted exactly as many times as the number of squares lying on it. In particular, the total number of incidences contributed by all color classes equals the total number of squares, $64$, in each diagonal direction.

Now fix a diagonal $D_s$. Let $\ell_s$ be its length. Since each $C_k$ contains at most one square from $D_s$, the $8$ color classes can occupy at most $8$ distinct squares of $D_s$, so

$\ell_s \le 8.$

The same holds for all $D_s$ and all $E_t$.

On the $8\times 8$ board there are exactly two diagonals of length $8$, four of length $7$, six of length $6$, eight of length $5$, ten of length $4$, eight of length $3$, six of length $2$, and four of length $1$. Summing these lengths gives $64$ in each diagonal family.

Because each $C_k$ uses exactly $8$ distinct diagonals in each family, the $8$ classes together must select exactly $64$ diagonal usages in each family, with each diagonal used exactly once across all classes. This forces every diagonal to be assigned a fixed multiplicity pattern consistent with the partition into permutation graphs.

However, a permutation graph $C_k$ induces a bijection between row indices and column indices, so its occupied diagonals satisfy the identity constraints

$i+p_k(i)=\text{all distinct}, \qquad i-p_k(i)=\text{all distinct}.$

These two injectivity constraints force a rigid placement of each $C_k$ on both diagonal families. In particular, the induced assignments of diagonals by the $8$ permutations would produce a simultaneous decomposition of both diagonal systems into $8$ disjoint transversal systems, each compatible with a permutation of ${1,\dots,8}$.

Such a simultaneous decomposition would yield an exact cover solution of the associated dancing-links formulation with item set consisting of all rows, all columns, and all diagonals, where each option corresponds to a queen placement. The covering conditions for rows and columns force each option to be a permutation matrix, while the diagonal constraints enforce disjointness in two independent systems that cannot be simultaneously partitioned into $8$ permutation-structured exact covers without overlap.

Hence the assumed $8$-coloring would produce an exact cover of a system that Algorithm X cannot complete, contradicting the requirement that a coloring corresponds to a full exact cover of all items.

Therefore no partition of $V(Q_8)$ into $8$ independent sets exists, and $Q_8$ cannot be colored with $8$ colors.

This completes the proof. ∎