Snow White and the Seven Rooks on Dark Squares

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.

Alternate answer elaborating some ideas already present in the discussion.

First, observe that we can swap two rows of any solution and preserve the fact that it is a solution, provided that the two rows have the same parity (i.e. there is an odd number of rows between them); and similarly for columns. We can also perform a diagonal flip of the entire board.

Suppose we have a solution. Using the above operations we can move the queen to h1, regardless of where it started.



Now we know there is a rook on a dark square in the g-file. Using a row swap we can move it to g3. The rook can't have been on the first rank or else it would have been attacking the queen, so this doesn't move the queen we already placed. Similarly we move the rook on the 2nd rank to f2 with a column swap.



Continuing in this way, we perform swaps to place black rooks on e5 and d4, then on c7 and b6, without disturbing the queens and rooks we previously placed.



But now there is nowhere to place the last rook, a contradiction. So no solution exists.

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.

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.

Answer:

Not possible.

As mentioned by others,

the queen's diagonal attack is irrelevant: it affects only white squares and the 7 rooks are on black. She might as well be just an eighth rook. Without loss of generality you can also assume she is at h1.

This means that an equivalent problem is to

place 7 non-attacking rooks on the 7x7 sub-board a2-g8, such that all 7 are on black squares.

Notice that

a rook on a black square of this 7x7 sub-board attacks 5 black squares (excluding her own) and 7 white squares. So any placement of 7 rooks on black squares will result in a total of 35 attacks against the 17 unoccupied black squares.

Hence some black square is attacked more than twice, which means it must have either two attackers in the same rank or two in the same file - and these rooks also attack each other.

I had a highly visual answer prepared, only to realize it was basically the same as @Invizio's. So here's another:

Is it possible?

No.

Why?

Let's place our $7$ rooks. Each of them can attack $7 \times 2=14$ squares. There are also $7 \times 6 = 42$ squares in total that are attacked twice by any dual combination of these rooks. So, together they all attack $14\times7-42=56$ distinct squares, making $63$ when the squares they're on themselves are added.

Each of them can attack $8$ white and $6$ black squares. If we have $n$ white squares that are attacked twice, then we have $56-n$ attacked white squares, and $n+7$ attacked or occupied black squares. Since there's only one free square left:

$33>n+7>30$
$26>n>23$

However, both squares attacked by the same combination of rooks have the same color, so $56-n$ and by extension $n$ must be even, as in $24$.

$n+7=31$, so the remaining square must be black, and therefore can't be occupied by the queen.

Another solution:

Since Queen’s diagonal moves aren’t valid, we can state that the white queen is another eighth rook.

Then the problem becomes:

Can you locate 8 rooks in 7 black / 1 white squares, not attacking each other?

We know that

Swapping 2 rooks like following (White to black) in any valid not-attacking 8 rook solution makes another valid solution.

This manipulation should be possible until we get the following position:

Note that

Swapping two rooks doesn’t change the parity of numbers of whites/blacks which rooks are located.

Simple proof:

Any rectangles on the chessboard (considering each squares to vertices) should have even number of white / blacks.

Therefore

Seven blacks and one white is impossible.

Edit - Here is the proof that

there are no solutions that cannot be diagonalized by swaps.

Using the standard chess notation and the picture above, there is a rook on file a, and so on the rank 8.

If the rook is on a8, no need any moves. If the rook is not on a8, swap a? rook and ?8 rook.

After the moves, we just need to solve the problem in smaller chessboard (7x7).

Repeating these moves will let the range of to-solve chessboards as 7x7, 6x6, 5x5, 4x4, 3x3, 2x2 and finally all rooks are solved.