codeworrior's blog

chess board
By codeworrior, 14 years ago, In English
in how many ways is it possible to place z identical rooks on a chessboard of dimension x*y such that every cell in the chessboard is threatened by at least one rook ??
plzz explain how to solve this problem??
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
> i can solve it when all the rooks are considered of different color
Then just divide this number by z!, since now you can rearrange the rooks and still get the same configuration.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It depends on the complexity do you need)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
If z>xy or z <max(x,y) ret 0
Otherwise => inclusion-exclusion
Ai - set of ways of placing z identical rooks on a x*y chessboard knowing that i is missing where i is a column or row
We have |Ai1 * Ai2 * ... * Ain|
= \binom{xy-ky-(n-k)x+k(n-k)}{z}, where k is the number of elements from {i1,...,in} that are rows with k in
{0, ..., n} and n in {1,...,x+y} and "*" stand for intersection and \binom{x}{y}(binomial number) is x!/(y!(x-y)!) and if x is 0 or negative then \binom{x}{y} is 0;
The answer is A=\binom{xy}{z}-S
and
S=sumi=1 x+y sumk=0 i(H(i,k))
H(i,k)=\binom{x}{k} \binom{y}{i-k}\binom{xy-ky-(i-k)x+k(i-k)}{z}

Hope the writing is understandable - I didn't find good tools of writing such formulas here
H(i,k) can be taken from a precomputed table.
Precomputation can be done using O(n2) aditional memory and O(n2) using Pascal identity.
Then follow O(n2) summations. Hope I'm not wrong. Even if I'm wrong the idea can be used - I believe so.
If you get BigInts I think it can be done in O(n3) if this is O(n2) as claimed
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
If anyone can check if my dinamic formula is correct, please do:
d[x][y][z]-your answer
d[x][y][z]=sum{i=1}{x}{d[x][y-1][z-i]*binom{x}{y}}+sum{i=0}{x-1}{x*d[x-1][y-1][z-1-i]*binom{x-1}{i}}
d[1][1][1]=1
d[x][y][z]=0, x<1 or y < 1 or z < 1
As it looks this algo is O(n4) but I'm thinking if some tricks might be used to reduce the complexity.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is a solution with O(1) complexity.

We have k rooks and n*m board.

Consider, we have not n*m but n*k board.

Than the answer is n·(n - 1)·...·(n - k + 1).

Now all we need is to select k rows from given m rows in all ways: m! / k!·(m - k)!

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Why is this correct? I mean, I don't understand why in all configurations all cells will be covered at least once.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      When we have only k rows, not m, this means we must occupy each row. First row we can occupy in any of n columns. Second - in any of n colums, except the column, selected on the previous step - (n - 1) and so on.

      Now we have m rows. So let's just select k that we will use and keep other rows empty. It can be done in CMK ways.

      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I repeat. If the answer is not 0 then k>=n and k>=m. So you cannot do it like you say. There will be at least one column with more than one rooks.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      It is not correct. If k>n*m or k < max(n,m) the answer is 0. But the idea can be adjusted. Suppose the answer is not 0. Then k >=n and k >=m. By considering an n*k board we will not get the answer n*(n-1)*...*(n-k+1)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Cut out "But the idea can be adjusted. I don't know how.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          If k > n OR k > m answer is 0.

          And if k <= min(m, n) my formulas should work.

          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Have you read the problem statement? Do you know what a rook is? We need our rooks to attack all positions on the chess table and we need at least max(n,m) rooks to do that.
            → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            "If k>n or k>m answer is 0."
            A simple example to prove you wrong. The board is n*m and the number z of rooks is n*m. Then by simply filling the chessboard with rooks we get the single solution.
            → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well... Not O(1) because we cannot calculate this factorials fast.

But we can used Pascal's triangle to calc CMK

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ok. I think I got it.

First of all if k <= x answer is 0.

Second of all ; ) to cover all spots we must place one rook either on each row or on each column. Why? Consider that we have column i and row j without rook - than place (i, j) is unattacked. Proved.

So let's assume we are going to cover all x rows.

Let's use dynamic programming. This is pseudocode.

http://pastie.org/1150933

After we should switch x and y and repeat.
Solution for O(n3).

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The answer is:

 

where

 

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Sorry, in the first formula above, n should be x, m is y and r is z.
    → Reply