Rooks Attacking Every Square on a Chess Board

Question

8 rooks are randomly placed on different squares of a chessboard. A rook is said to attack all of the squares in its row and its column. Compute the probability that every square is occupied or attacked by at least 1 rook.

The first step I took was to state that there are $64C8$ ways to decide how to place the 8 rooks on the chessboard. Next, I tried to experiment with a physical chessboard to see how this could be done. The only way I found that every square on the board can be attacked is if one rook is in either every horizontal row or every vertical row. Therefore, there are $2 * 8^8 - 2$ ways to place the rooks. To clarify, it is "-2" because the diagonals are counted twice.

Is there a case that I overlooked, or did I solve the problem correctly?

Thanks,

You Know Me......

I think you are misinterpreting the answers in the same way I was. Your approach is to count the positions with a rook in each row, add the positions with a rook in each column, subtract the positions which have been counted twice. That's fine, but there are more positions to be subtracted than the diagonals. You need to subtract any position with both a rook in each row and each column. Look at Ross Millikan's answer again. — saulspatz, Jul 05 '18 at 15:04
@YuiToCheng That duplicate target does not answer this question. But this one does. — Jyrki Lahtonen, Aug 07 '19 at 08:06

Ross Millikan · Answer 1 · 2018-07-06T00:23:35.827

3

You need one rook in each row or one rook in each column. There are $8^8$ ways to put one rook per row and $8^8$ ways to put one rook per column. This double counts the ways that have one rook in each row and column, which is the classic definition of covering every square. For that there are $8$ ways to choose the column for the first row, $7$ ways to choose the column for the second row, and so on making $8!$ in total. Using inclusion-exclusion the final answer is $2\cdot 8^8-8!=33514112$

edited Jul 06 '18 at 00:23

answered Jul 05 '18 at 13:52

Ross Millikan

374,822

2

You can have all eight rooks on the first row, so there are more solutionsthan that – Empy2 Jul 05 '18 at 14:06
@Empy2: I didn't read carefully enough. I'll update. – Ross Millikan Jul 06 '18 at 00:16

score 1 · Answer 2 · answered Jun 11 '15 at 14:54

1

You're not just counting the diagonals twice. There are many more ways to lay out the rooks so that there is exactly $1$ in each row and column.

This is actually a good example for a very simple application of the inclusion-exclusion principle, since you want to find the size of the union of two sets.

answered Jun 11 '15 at 14:54

NovaDenizen

4,216
15
23

Can you explain to me which ways then? – vamaddur Jun 11 '15 at 15:03
How many ways are there to put a rook in every row such that each is in a different column? – NovaDenizen Jun 11 '15 at 15:05
2

Isn't it just 8 factorial? – vamaddur Jun 11 '15 at 15:13
@YouKnowMe: Almost -- but see the comment under Ross's answer. – joriki Jul 05 '18 at 14:44

score 1 · Answer 3 · answered Jul 05 '18 at 15:42

Case $1$: Each row has a rook: There are $8^8$ ways to do this.

Case $2$: There is a row without a rook. In this case every column has a rook, otherwise some squares of that row would be unatacked, hence the number of solutions to case $2$ is $8^8$ minus the number of combinations in which every row has a rook and every column has a rook, which is $8!$.

Hence the final answer is $2\times8^8-8!$.

score 0 · Answer 4 · edited Apr 13 '17 at 12:21

0

Consider e.g. In how many different ways can we place $8$ identical rooks on a chess board so that no two of them attack each other? for the number of ways that 8 rooks can be placed so that all squares are attacked or occupied.

Then, how many ways in total can you place 8 rooks regardless of attacked or occupied squares?

edited Apr 13 '17 at 12:21

Community

1

answered Jun 11 '15 at 14:12

sjb

88

I do not want a follow-up question to this..... I would like someone to verify my solution..... – vamaddur Jun 11 '15 at 14:33
@YouKnowMe The questions might appear different, but they're actually the same question. – Michael Burr Jul 05 '18 at 13:56

Rooks Attacking Every Square on a Chess Board

4 Answers4

Linked