《“十三五”现代综合交通运输体系发展规划》解读

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.

Notice that the black rooks are an even number of columns away from the queen, and the white rooks are an even number of rows away. Every unattacked dark square falls into exactly one of these groups, so it either shares a column with a light square in the queen's row, or a row with a light square in the queen's column. There are six such squares in total, giving a maximum of six rooks regardless of the queen's location.

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

Answer:

It is not possible.

A somewhat more visual explanation than other answers:

Let's consider the number of black squares in each column that don't share a row with the queen:



Some columns have four black squares that don't share a row with the queen, some columns have only three.

Since the queen is on a white square, she is necessarily on a column that has four black squares not on her row. No rook can be in that column.

This leaves us with 3 columns that have 4 potential rows for rooks, and 4 columns that have 3 potential rows for rooks. Let's consider the latter.

Since each of the seven rooks and the queen (eight pieces in total) take up a whole column and a whole row for themselves due to their attack pattern, and there are exactly eight rows and columns on the board, then each column (and row) must contain exactly one piece.

Notice that

On the last picture, there are four columns which must be filled. However, they all share only three rows. By the Pigeonhole principle, if each column is to contain a piece, then necessarily at least one pair must share a row. Therefore, there cannot be any valid solution!

I used the case given in the question as a visual demonstration for my answer, but my answer is independent of where the queen is placed, so long as it in on a white square.

Answer 4

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.