7
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ Place the rooks on the main diagonal. Now permute the columns (or rows, but not both) to obtain all possible $8!$ configurations. This is the same as asking about all possible column permutations of the identity $8\times 8$ matrix. $\endgroup$ – Pedro Tamaroff May 3 '13 at 2:43
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And how are you accommodating for the overcounting? For example, putting the first rook in row 1 column 1, the second rook in row 2 column 2, everything else in the same place, we have an identical configuration.) $\endgroup$ – Cameron Buie May 3 '13 at 2:40
  • 2
    $\begingroup$ BTW, $8! = 40320$, not $5040$ (which is $7!$). :-) $\endgroup$ – ShreevatsaR May 3 '13 at 2:43
  • 1
    $\begingroup$ Worth mentioning, then, yes? $\endgroup$ – Cameron Buie May 3 '13 at 2:43
  • 1
    $\begingroup$ Oops...NOW the page updates to show me your edit. My bad. $\endgroup$ – Cameron Buie May 3 '13 at 2:45
  • 1
    $\begingroup$ Thanks for all the help and comments! After this long day ... $\endgroup$ – Alice May 3 '13 at 2:47
7
$\begingroup$

As you have $8$ rows and $8$ rooks and no two rooks can be on the same row, each row should have exactly one rook.

As you have $8$ columns and $8$ rooks and no two rooks can be on the same column, each column should have exactly one rook.

So you can come up with a rook configuration by placing the first rook on some column of the first row, then the second rook on some other column of the second row, and so on. The number of configurations is therefore the number of ways you can list the $8$ different columns such that each of them is covered and none of them repeats. This is the number of permutations of the $8$ columns, which is $$8! = 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 40320.$$

$\endgroup$
2
$\begingroup$

For two rooks to be attacking each other, they must either share a row or a column. For two rooks to not attack each other they must not share a row and they must not share a column.

8 rows and 8 columns need to be chosen once each. A set of eight rows can be chosen in $\binom{8}{8} = 1$ ways and a set of columns can be chosen in $\binom{8}{8} = 1$ ways.

Ordered pairs can be generated from the two sets in $8!$ ways.

Given the first coordinate of the first ordered pair (can be anything wlog), there are $\binom{8}{1}$ ways to choose the second coordinate for the first ordered pair.

Given the first coordinate of the next ordered pair, there are $\binom{7}{1}$ ways to choose the second coordinate.

Because $\binom{n}{1} = n$ the total number of ways to create the coordinates is $n(n−1)(n−2)...(1) = n!$.

In our case, $n = 8$ so there are $8!$ ways to generate valid coordinates or ways place the rooks.

In total, there are $\binom{8}{8} 8! = 8!$ ways to place the rooks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.