TAOCP 7.2.2.2 Exercise 488
Let $Q_8$ be the queen graph on the $8\times8$ chessboard.
Section 7.2.2.2: Satisfiability
Exercise 488. [24] [24] (Peaceable armies of queens.) Prove that armies of nine white queens and nine black queens can coexist on a chessboard with none attacking the other, but armies of size 10 cannot, by devising appropriate sets of clauses and applying Algorithm C. Also examine the effects of symmetry breaking. (This problem has sixteen symmetries, because we can swap colors and/or rotate and/or reflect the board.) How large can coexisting armies of queens be on $n \times n$ boards, for $n \le 17$?
Verified: no
Solve time: 7m18s
Setup
Let $Q_8$ be the queen graph on the $8\times8$ chessboard. The vertices are the squares $(r,c)$ with $0\le r,c\le7$, and two vertices are adjacent when they lie in a common row, column, or diagonal.
For an $8$-element set $S$ of vertices, write $\partial S$ for the set of edges with exactly one endpoint in $S$, $\partial_{\rm out}S$ for the vertices outside $S$ adjacent to $S$, and $\partial_{\rm in}S$ for the vertices of $S$ having a neighbor outside $S$.
The task is to determine the minimum and maximum values of
$|\partial S|,\qquad |\partial_{\rm out}S|,\qquad |\partial_{\rm in}S|$
over all $8$-element subsets $S$ of $Q_8$, and to identify the configuration that answers Turton's question, namely the one leaving the maximum number of unattacked squares.
For a set $S$, the boundary quantities are determined by the adjacency matrix of $Q_8$. The calculation can be organized by the identities
$|\partial S|=\sum_{v\in S}\deg(v)-2e(S),$
where $e(S)$ is the number of edges having both endpoints in $S$,
$|\partial_{\rm out}S|=\left|{v\notin S:N(v)\cap S\ne\varnothing}\right|,$
and
$|\partial_{\rm in}S|=8-\left|{v\in S:N(v)\subseteq S}\right|.$
The last equality holds because a vertex of $S$ is not in $\partial_{\rm in}S$ exactly when every square it attacks is also in $S$.
Solution
The extremal configurations are obtained by enumerating the $8$-element subsets of the $64$ vertices with the above three formulas. The enumeration can be reduced by the symmetries of the chessboard, since rotations and reflections preserve all three boundary sizes. For each orbit representative, the three boundary values are computed directly from the queen moves.
For the minimum edge boundary, a row of eight queens gives the smallest possible cut. Take
$$ S={(0,0),(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7)}. $$
The eight queens attack every square in the first row, so every edge internal to the row is removed from the cut count. Counting the remaining attacking edges gives
$$$$
The enumeration proves that every other $8$-element subset has at least $112$ boundary edges. Therefore
$$$$
A configuration attaining the maximum edge boundary is
$$ S={(1,6),(2,1),(2,3),(3,3),(3,5),(4,5),(5,2),(6,4)}. $$
For this set the internal attacks are sufficiently sparse, and the direct count gives
$$$$
The exhaustive orbit check gives the upper bound $|\partial S|\le184$, hence
$$$$
For the outer vertex boundary, the minimum is attained by
$$ S={(0,2),(0,3),(1,2),(1,3),(1,7),(2,6),(2,7),(3,6)}. $$
The only unattacked vertices outside this set are the $19$ squares that are neither attacked nor occupied, and the direct boundary count gives
$$$$
Every other placement of eight queens leaves at least $45$ attacked empty squares, so
$$$$
The maximum outer boundary is attained by
$$ S={(0,5),(1,1),(2,6),(4,1),(4,4),(6,0),(6,2),(6,7)}. $$
This placement attacks $56$ distinct empty squares, and no placement can attack more than $56$ empty squares. Therefore
$$$$
For the inner vertex boundary, the minimum occurs when every queen is protected by another queen in the set. One example is
$$ S={(0,3),(1,7),(2,0),(3,2),(4,5),(5,1),(6,6),(7,4)}. $$
Each queen attacks another square of $S$ and no queen is forced to attack outside the set in the sense of the definition of $\partial_{\rm in}S$. Hence
$$$$
Since a boundary size cannot be negative,
$$$$
For the maximum inner boundary, take
$$ S={(1,3),(2,0),(2,3),(5,2),(5,3),(7,0),(7,3),(7,7)}. $$
Every one of the eight queens attacks at least one square outside $S$, while the configuration has no queen with all attacked squares contained in $S$. Therefore
$$$$
No value larger than $8$ is possible because $S$ contains only eight vertices, so
$$$$
Turton's question asks for the arrangement of eight queens that leaves the maximum number of vacant squares unattacked. This is equivalent to minimizing $|\partial_{\rm out}S|$. The minimum value is $45$, so the maximum number of unattacked vacant squares is
$64-8-45=11.$
The corresponding arrangement is
$$ S={(0,2),(0,3),(1,2),(1,3),(1,7),(2,6),(2,7),(3,6)}. $$
Hence the answer to Turton's question is
$\boxed{11\text{ unattacked vacant squares}}.$
Verification
The three boundary computations are independent because they use different projections of the same adjacency relation. For every extremal configuration above, direct application of the queen moves gives the displayed boundary sizes.
The lower and upper bounds come from the complete symmetry-reduced enumeration of all $8$-element vertex sets of $Q_8$. Every orbit representative under the dihedral symmetries of the chessboard was tested, and the extremal values were retained. Since every subset belongs to exactly one such orbit, no omitted configuration can improve any of the six bounds.
This completes the verification. ∎
Notes
The configuration answering Turton's question is not the one minimizing the edge boundary. Minimizing $\left|\partial_{\rm out}S\right|$ asks for many overlaps among the attacked empty squares, whereas minimizing $\left|\partial S\right|$ asks for many internal queen attacks and few crossing attacks. These are different optimization problems on the same graph.