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.
What if you place only one knight in the diagonal?:D
Sorry i forgot the most important part. I need how many possible placement are there?
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 : \
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]
code
ASS ? (function) (its too rude)
but ASSERT is not so rude?
DP Dummy Penis