yisyis's blog

Dynamic Problem (need help)
By yisyis, 11 years ago, In English

I have problem and i think it's about Dynamic programming but i'm not sure. By the way, i can't find out how can i solve this. Dynamic programming just an instintic.

Problem:

We've got a standard chessboard (8x8) and we got infinite knights. We gonna put these knights onto chessboard. There is only one condition: Number of knights in all rows and columns must be odd. How many possible solutions there?

I've tried to find answers for 2x2, 3x3, 4x4 chessboard using brute force and tried to understand pattern or find a formula but i cant find it. Please help me how can i find the solution.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What if you place only one knight in the diagonal?:D

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry i forgot the most important part. I need how many possible placement are there?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not sure but this algorithm (or at least the idea) may be correct:

      for all bitmasks (from 0 to 1^(2*8-1)) calculate DP[bitmask], where bitmask represents the rightmost column and bottommost row. for example if in the 7th position of bitmask is 0 it means 7th row in the last column sums even. calculation would like something like this:

      for every old_bitmask for every bitmask DP[N][old_bitmask ^ bitmask] = DP[N-1][old_bitmask]

      kind of this :D This is very rough explanation : \

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

use dynamic programming with bitmask dp[i][bitmask] means number of ways to put knights of table i*8 (i.e first i rows) and if i'th bit on bitmask is 1 that means i'th column is odd , then output dp[8][2^8-1]

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

code

→ Reply