1
$\begingroup$

I have a m×n chessboard and I have to put p rooks in the board so that no two of them are in attacking position.
(Two rooks attack each other if they are in the same row or same column)
How many ways I can do that?
I saw somewhere that the problem can be described with a recurrence relation which would be R(m,n,p) = m . R(m-1,n-1,p-1) + R(m,n-1,p) .
I tried to figure it out but I couldn't.
How did this relation come?(I know the base cases, I just want to know how this formula works?)

EDIT : I have considered it already but that's where my confusion is.
Let's say I have a 3×3 chessboard. enter image description here
Then when I want to put rooks in the first column I have 3 options (choosing cell 1,1 ; choosing cell 2,1 ; choosing cell 3,1) .
Now,from my poor drawing it's obvious when I'm putting the rook in the cell (1,1) or (3,1) I just have to find out how many ways I can put other (one less) rooks in the (2×2) chessboard.
But when I'm putting the rook in the cell (2,1) I see I have to find out how many ways I can put x rooks in a 1×2 chessboard and y rooks in a 1×2 chessboard.

Where,x+y = p - 1.
Now for any m and n this new recurrence relation has to be true R(m,n,k) = R(t,n,x) + R(m-t,n,k-x) .

Because if that's true then for placing every rook in the first column I can surely assume I can place other rooks in R(m-1,n-1,p-1) ways.

(I am not sure how this works and how x and y would vary.)

That's where I got stuck.

$\endgroup$
  • $\begingroup$ The two disconnected parts behave just like a 2 times 2 square as far as the rules of this task are concerned. So, while it isn't a rectangle you can treat it like it were one. $\endgroup$ – Phira Jul 25 '15 at 16:35
  • $\begingroup$ Yeah I got this now.Thanks a lot. $\endgroup$ – anon Jul 25 '15 at 17:03
2
$\begingroup$

I will assume that you have $m$ rows and $n$ columns.

Case 1: There is a rook in the first column

This gives $m$ possibilities for placing this rook and $R(m-1,n-1,p-1)$ for placing the other rooks. (One rook less, remove first column, remove row with the first rook.)

Case 2: There is no rook in the first column

This is clearly the same problem with $n$ replaced by $n-1$.

$\endgroup$
  • $\begingroup$ Thanks for your answer.But I have considered it already.I just didn't get the Case 1. $\endgroup$ – anon Jul 25 '15 at 14:28

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.