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

Answer:  N! (factorial of N)

Proof: There should be exactly one rook in each column and in each row. If this is not held than there will be at least one pair of rooks attacking each other. We populate each column one by one with rooks. In first column we have N possible position for the rook, as there are no previous rooks and it can be put in any row. After that in second column we have only N-1 valid position, as the one row is already occupied with previous rook. In third column we have N-2 places left as two rows are already occupied by first and second rooks. and so on. In the last Nth column we have only 1 possible position as previous N-1 rooks occupied different N-1 rows and only one is left. So we have N*(N-1)*(N-2)*(N-3)*...*2*1 = N!

Example: If N is equal to 3. In first column we can put rook in any place (3 variants). In second column one row is occupied by previous rook so we have only 2 options and in last column we have 1 option. In total 3*2*1=6 variants.
Rows for each rook:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

____________________________
Comment down for any queries

Please give a thumb up