Question

Rooks can move any number of squares horizontally or vertically on a chess board. The n rooks problem is to arrange rooks on an n×n board in such a way that none of the rooks could bump into another by making any of its possible horizontal or vertical moves.

For this problem, the variables are each column (labeled 0, 1, ... , n−1), the the domain consists of each possible row (also labeled 0, 1, ... ,n−1). In each column we place a rook on row 0, row 1, ... , row n−1.

For example, if n=2 we have only two solutions to this problem:

R @
@ R 

or

@ R
R @ 

How many possible solutions are there to this, in terms of n?
Also, give a simple proof that your answer is correct.

Answer 1

Note that each row must contain a rook. So the problem is reduced to finding a column for each rook.

The first rook can be placed in any of the columns. The second rook can be placed in any column except the column of the first rook. So there are options for this and so on

Total number of ways is

Hope this was helpful. Please do leave a positive rating if you liked this answer. Thanks and have a good day!