In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other?
I tried to draw diagrams onto a $8\times8$ square but I'm only getting $16$ ways. Does that sound right?
Thanks for the help!
Combinatorics – Ways to Place 8 Identical Rooks on a Chess Board Without Attacking Each Other
combinatoricsproblem solving
Related Solutions
The flaw in the reasoning is because you write "the second rook can be placed in $7$ different rows and you can choose $6$ different columns and so on" which is not actually correct - and should stand out as a red flag because no justification is given to a pretty non-obvious and important fact in your argument. Also, your "and so on" hides what happens to the last rook in your argument, which you would say can be put into $1$ row and $0$ columns - which is clearly wrong!
Suppose we put the coordinates on the grid ranging from $(1,1)$ to $(8,8)$ where the diagonal in question is those points of the form $(n,n)$. If you put the first rook at $(1,2)$, your claim is that there are $42$ valid positions for the second rook - but this is not so! More specifically, you claim that we can fix the first coordinate in $7$ ways and then will have $6$ choices for the second coordinate - but this does not hold. In particular, if we choose the first coordinate for the second rook to be $2$, we find that all positions $(2,x)$ are legal except for $(2,2)$ - which is both attacked by the the first rook and on the main diagonal. Oops - so there are actually $43$ valid positions for the second rook!
Patching this argument turns out to be really hard because the number of valid positions for the next rook will, in general, depend on the placement of the previous rooks - so finding another approach is warranted. (For instance, one can count the number of arrangements of rooks that do include the diagonal and also the total number of arrangements of rooks, then subtract. It's also to get a recurrence relation by considering that each square on the diagonal is attacked by two rooks - which then means you have some sort of relation on the rooks which is useful to counting the number of possible placements)
If I understood correctly your approach:
- You take two rooks. You allow first one to stand anywhere ($64$ places)
- You restrict the second one to stand either on the same vertical or row ($14$ places)
- You account that you calculate the configurations of rooks twice ($64\times14/2)$
- You allow for all other 6 rooks to take any of $62$ places left ($\times {62 \choose 6}$).
However, the problem of this method is that since you distinguish between 2 first rooks and 6 rest rooks, you count a lot of positions more than once. For example, position (A1,A2,A3,A4,A5...) is the same as (A3,A4,A1,A2,A5...).
The only viable solution is to calculate positions when no rook attack another rook and to subtract this number from the total possible placements.
Notice, that when no rook is attacking other rook, they occupy all 8 rows. Thus, this position can be uniquely defined as 8 numbers $(a_1,a_2,\ldots)$ where $a_i$ is the position of rook in $i$-th row. All these numbers should be different (otherwise, two rooks are in the same vertical). Thus we need to calculate the number of permutations of 8 elements, which is $8!$. Finally the answer is ${64\choose8} - 8!$
Best Answer
Let's do this piece by piece.
First, let's consider the first rook, we can place it anywhere on the board, thus we have $8^2=64$ choices for that.
Now, for the second one, we can't be in the row or column of that first one, so leaving us with $7^2=49$ choices.
Then so on, we have $6^2=36$ for the third one, $25$ for the fourth one, and so on $\dots$
But, however, we have to remember the rooks are not labeled, thus it doesn't matter specifically about a specific rook's position.
Thus, we have a total of $\frac{(8!)^2}{8!}=40320$ ways.