TAOCP 7.2.2.2 Exercise 487
Working
Section 7.2.2.2: Satisfiability
Exercise 487. ▶ [27] [27] There are $\binom{92}{2} = 4216,368$ ways to place eight queens on a chessboard. Long ago, W. H. Rouse asked which of these leaves the maximum number of vacant squares to remain unattacked. [See W. W. Rouse Ball, Mathematical Recreations and Problems, third edition (London: Macmillan, 1896), 109–110.]
Every subset $S$ of the vertices of a graph has three boundary sets defined thus:
$$\partial S = \text{the set of all edges with exactly one endpoint} \in S;$$ $$\partial_{\text{out}} S = \text{the set of all vertices} \notin S \text{ with at least one neighbor} \in S;$$ $$\partial_{\text{in}} S = \text{the set of all vertices} \in S \text{ with at least one neighbor} \notin S.$$
Find the minimum and maximum sizes of $\partial S$, $\partial_{\text{out}} S$, and $\partial_{\text{in}} S$, over all 8-element sets $S$ in the queen graph $Q_8$ (exercise 7.1.4–241). Which set answers Turton's question?
Verified: no
Solve time: 6m15s
Working