Place $8$ rooks on a $10\times 10$ board.

The Problem:-

"In chess, a rook attacks any piece in the same row or column as the rook, provided no other piece is between them. In how many ways can $8$ rooks be placed on a $[8\times8]$ chessboard so that no two attack each other? What about $8$ rooks on a $10\times10$ board?"

I believe I have an answer for the first part of the question. When placing the first rook, there are 8 places on any particular column (or row) to place the rook, leaving just 7 places on a different column (or row) for the next rook, and so on, providing 8! possible ways to place the rooks in such a way that they cannot attack each other ($P(8,8) = 8!/(8-8)! = 8!$).
However, I am not sure I fully understand how this would work for a board where there are more rows and columns than pieces (such as on a 10x10 board). Does it become $P(10,8) = 10!/(10-8)! = 10!/2$ ? If so, why? If not, how should I approach this problem?

This problem was found in "Introduction to Combinatorics and Graph Theory" by David Guichard.

Solution 1:

So for the first question you need to place a rook in each column. The rook in the first column can go in $8$ places, the rook in the second column then has $7$ possible rows etc.

In the second part, you need first to choose the $8$ columns out of the $10$ available, and then place a rook in each of the columns. If once again you move from left to right, counting the number of possibilities, you should be fine.

Rather than talking about "any particular" column or row, you should make a habit of defining the scheme more closely (the first, second rather than "any" etc). This will help to avoid a great deal of confusion and can also highlight any double-counting.

Solution 2:

For the second part, if we first focus on the columns the rooks are in: since there cannot be two rooks in the same column, the rooks must appear in $8$ different columns. And you can choose $8$ columns out of $10$ in

$$10 \choose 8$$

ways. Once, we've chosen the $8$ columns, let's place the rooks in those columns. Well, you can place the first rook in $10$ different rows, the next in $9$, etc. until the last one, which can be place in $3$ different rows, so we can place those $8$ rooks in:

$$\frac{10!}{2!} = \frac{10!}{2}$$

ways. This leads to a grand total of:

$${10 \choose 8} \cdot \frac{10!}{2}$$

ways of placing $8$ rooks on a $10 \times 10$ board.

Solution 3:

This is a different approach than what's been offered so far, but that might help some people understand the problem differently.

I would solve this by first assuming order mattered when placing the rooks (so placing on $A1$ then $B2$ is different than $B2$ then $A1$), then adjusting my answer to compensate.

The number of squares you can place the first rook on is $10^2$. Wherever you place it, you effectively turn your board into a $9 \times 9$ board with no rooks on it.

Now that we've lost a row and a column from our first rook, the number of squares you can place the second rook on is $9^2$.

Carrying on for each rook, we get:

$$10^2 \cdot 9^2 \cdot ... \cdot 3^2$$

Ways to place our rooks (don't forget we only have $8$ rooks, so we don't go all the way to $1^2$). Remember though, we assumed order matters. In reality, it does not. However, there's only $8!$ different ways to order our rooks, so we can divide our initial answer by $8!$, leaving:

$$ (10^2 \cdot 9^2 \cdot ... \cdot 3^2) / 8!$$

Ways to place our rooks.

Solution 4:

For the first case of placing 8 rooks on an 8x8 board your result of 8! is correct.

For the second case of placing 8 rooks on a 10x10 board I find the following approach to be the simplest way to do the calculations:

There are 10*9/2 = 45 ways to choose which two rows you will not be using. Likewise there are 45 ways to choose which two columns you will not be using.

Once you have chosen which rows and columns not to use there are 8! ways to place the rooks in the remaining squares.

That gives a total of 8!*45² = 81648000 possibilities.