环球网旅游

Question

With the white queen on a light-coloured square of your choosing, can you place 7 rooks on the dark squares of the chessboard so that no piece attacks another?

In the above Lichess illustration (with the lovely "horsey" piece set), the rooks are attacking each other, so that one isn't a valid solution.

• If possible, a sample position will suffice.

• If impossible, please include a proof in your answer.

Answer 1

Alternate answer:

This cannot be done.

If I divide up the unattacked dark squares like so:

The squares with black rooks fit into three columns, and the squares with white rooks fit into three rows, so only six rooks can be placed in total.
Every position of the white queen is reachable from this one by exchanging rows and columns; since neither of these operations change which rooks attack which others, every board admits at most six rooks by the same argument.

Answer 2

Answer:

This is impossible.

Explanation:

Since the rooks are on black squares, the diagonal constraints from the queen don’t matter. So it’s as if we have seven rooks on black squares and one rook on a white square. I’ll show below that this is impossible.

In the classic non-attacking rook problem, the positions of the rooks correspond to a permutation of 8 items. It is clear that any white (black) square corresponds to even (odd) value of r+c, where (r,c) is the position of that square. In any permutation σ of 8 items, the sum of r+σ(r) over all rows r is even, so there must be an even number of rows r for which r+σ(r) is odd. But the problem asks us to place seven (an odd number) of rooks on black squares. Therefore, this is impossible.

Answer 3

As mentioned by @Pranay, the diagonals can be ignored. Without loss of generality (because rook attacks are preserved under row and column permutations), the white queen appears in the top left corner cell $(1,1)$. Now let binary decision variable $r_{ij}$ indicate whether a rook appears in cell $(i,j)$, where $i+j$ is odd. The problem is to maximize $\sum_{i,j} r_{ij}$ subject to linear constraints \begin{align} r_{2,3} + r_{2,5} + r_{2,7} &\le 1 \tag1\label1 \\ r_{3,2} + r_{3,4} + r_{3,6} + r_{3,8} &\le 1 \tag2\label2 \\ r_{4,3} + r_{4,5} + r_{4,7} &\le 1 \tag3\label3 \\ r_{5,2} + r_{5,4} + r_{5,6} + r_{5,8} &\le 1 \tag4\label4 \\ r_{6,3} + r_{6,5} + r_{6,7} &\le 1 \tag5\label5 \\ r_{7,2} + r_{7,4} + r_{7,6} + r_{7,8} &\le 1 \tag6\label6 \\ r_{8,3} + r_{8,5} + r_{8,7} &\le 1 \tag7\label7\\ r_{3,2} + r_{5,2} + r_{7,2} &\le 1 \tag8\label8 \\ r_{2,3} + r_{4,3} + r_{6,3} + r_{8,3} &\le 1 \tag9\label9 \\ r_{3,4} + r_{5,4} + r_{7,4} &\le 1 \tag{10}\label{10} \\ r_{2,5} + r_{4,5} + r_{6,5} + r_{8,5} &\le 1 \tag{11}\label{11} \\ r_{3,6} + r_{5,6} + r_{7,6} &\le 1 \tag{12}\label{12} \\ r_{2,7} + r_{4,7} + r_{6,7} + r_{8,7} &\le 1 \tag{13}\label{13} \\ r_{3,8} + r_{5,8} + r_{7,8} &\le 1 \tag{14}\label{14} \end{align} The maximum turns out to be

$6 < 7$,

and the optimal linear programming dual variables provide a short certificate of optimality. Explicitly, adding up constraints \eqref{2}, \eqref{4}, \eqref{6}, \eqref{9}, \eqref{11}, and \eqref{13} yields $\sum_{i,j} r_{ij} \le 6$.

This is a similar approach to the answer by @AxiomaticSystem, but the proof here is generated somewhat automatically as a by-product of the LP solve.