With 4 rooks on a $4\times4$ chessboard such that no rook can attack another, what is the probability there are no rooks on the diagonal?

Question

Four rooks are randomly placed on a $4 \times 4$ chessboard. Suppose no rook can attack another. Under this condition, what is the probability that the leading diagonal of the chessboard has no rooks at all?

Since no rook can attack another, we know that each row and each column contains exactly one rook each. Let $A_i$ be the event that row $i$ has its rook on the diagonal. Then $P\{A_i\} = \frac{1}{4}$ for each $i = 1,\dots,4$.

We want to find the probability that the diagonal of the chessboard has no rooks at all, or equivalently that none of the rows have their rook on the diagonal. Therefore we have

\begin{align} P\{A^c_1 \cap A^c_2 \cap A^c_3 \cap A^c_4\} & = P\{(A_1 \cup A_1 \cup A_3 \cup A_4)^c\} \\ & = 1 - P\{A_1 \cup A_1 \cup A_3 \cup A_4\} \\ & = 1 - (P\{A_1\} + P\{A_2\} + P\{A_3\} + P\{A_4\} - P\{A_1 \cap A_2\} - P\{A_1 \cap A_3\} - P\{A_1 \cap A_4\} - P\{A_2 \cap A_3\} - P\{A_2 \cap A_4\} - P\{A_3 \cap A_4\} + P\{A_1 \cap A_2 \cap A_3\} + P\{A_1 \cap A_2 \cap A_4\} + P\{A_1 \cap A_3 \cap A_4\} + P\{A_2 \cap A_3 \cap A_4\} - P\{A_1 \cap A_2 \cap A_3 \cap A_4\}) \\ & = 1 - (4 \cdot \frac{1}{4} - 6 \cdot \frac{1}{16} + 4 \cdot \frac{1}{64} - \frac{1}{256}) \\ & = 1 - \frac{175}{256} \\ & = \frac{81}{256} \end{align}

using De Morgan's Law and the inclusion-exclusion principle.

However, it seems that this is incorrect since if we consider the number of ways that we can place the rooks such that no rook can attack each other we have $\frac{(4!)^2}{4!} = 4! = 24$ [as per this answer for a similar problem] and so the answer should have denominator of 24. Having said that I don't see where my answer is wrong, so would someone be able to show me the correct solution?

Answer 1

Each non-attacking placement of the rooks defines a permutation $c_1c_2c_3c_4$ of $\{1,2,3,4\}$: $c_k$ is the number of the column containing the rook in row $k$. There are $4!=24$ such permutations, all equally likely. Those that have no rook on the main diagonal are derangements, and there are $9$ of them, so the desired probability is $\frac9{24}$.

If you know the formula for the number of derangements of a set of $n$ objects, you can use it, but $4$ is small enough that it’s almost as easy just to list them:

$$\begin{align*} &2143,2341,2413\\ &3142,3412,3421\\ &4123,4312,4321 \end{align*}$$

Answer 2

Your answer assumes independence between rook placements. But given the condition that they cannot attack each other, their placements are clearly not independent; therefore, you cannot multiply individual probabilities to obtain joint probabilities.

You are correct in observing that the total number of possible non-attacking arrangements is $4! = 24$. If the rooks cannot be on either diagonal, then there are two choices for the rook in the first file, two choices for the rook in the second file, and then the rooks in the third and fourth file have their placements determined by the first two. There are therefore $2 \times 2 = 4$ placements that avoid both diagonals.

If you only need to avoid one diagonal (say, the black diagonal), we merely need the number of derangements of four objects. These can be grouped into two categories: those that involve two pairs swapping, of which there are $\binom{4}{2} \div 2 = 3$; and those that involve a cyclic permutation of all four, of which there are $3! = 6$; for a total of $9$ derangements.

Answer 3

The number of allowable placements should be the number of derangements of $4$ items, which is $9$. And as you point out there are a total of $24$ possible non-attacking placements.

Answer 4

You are misapplying Inclusion-Exclusion. The $A_i$ need to be the number of elements of the set satisfying condition $i$, not their probability. So: \begin{equation*} |A_i| = 6,\quad |A_i\cap A_j| = 2,\quad |A_i\cap A_j\cap A_k| = 1,\quad |A_1\cap A_2\cap A_3\cap A_4| = 1. \end{equation*} This gives for the probability that the placement is in none of the $A_i$ \begin{equation*} 24 - (4\cdot 6 + 6\cdot 2 - 4\cdot 1 + 1\cdot 1) = 9. \end{equation*} So the probability is $\frac{9}{24} = \frac{3}{8}$. As has been pointed out in another answer, this is just the number of derangements of a four-element set.