Блог пользователя yisyis

Автор yisyis, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 : \

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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]

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится