Hello… I tried to solve KNICOV problem in June Cook off and I could not figure out for cases like N = 3 and M = 10. Did somebody managed to find a pattern in the position of the Knights?

At least for me I wasn’t able to find any good pattern. The answers are weird for skipping periods of 6 and 7. The safe way to solve this problem is to do bitmask DP that relates a row to a mask of its two previous rows.

There is a good pattern there, but edge cases are too risky.

```
N=1, ans=M
N=2,
ans=(M/6)*4+4;
if(m%6==1) ans-=2;
if(m%6==0) ans-=4;
```

for N=3, this pattern continues till M=13.

From then whenever M%6==2, ans would be +3 instead of +4.

Here’s a link to my answer. Comment if you have any doubts

Im not familiar to bitmask DP… Do you have any good link where it is explained?

Update, I found a pattern for 2 \leq N \leq 3. Haven’t proven yet if it works for big N, but for now it looks like this:

Can anyone comment if this Q could be done via brute force?? Since board is small, Make a boolean array of 0 and 1. If arr[i][j]==0, then place a knight at a cell and mark the cells 1 where it can attack and where its positioned.

Any comments??

I went down the pattern path, but was unable to identify the pattern when n == 3 and m > 13 and m % 6 == 2, as described in the accepted answer. However, even after reading that, I still can’t find a way to place 11 knights to cover a 3 x 14 board… Can somebody show me?

i.e. I can’t figure out how to deal with these question marks with only three knights:

```
..KK.. ..KK.. ??
..KK.. ..KK.. ??
...... ...... ??
```

Can you share a potential solution that uses 11 knights to solve 3 x 14?

I feel finding the pattern for m - 14 was too much for me.

So, I ended up getting a wrong answer (cause I found till m = 6 -_-). Is there anyone who used backtracking or other method to solve the problem ? It might be slower but it will take care of all the corner and edgy cases.

is it possible to solve this question using maxflow aur min cut??

can a knight only attack one other box other than the one it is placed on?

because if that’s not the case then we can easily solve this problem using only 4 knights for n=2, isn’t it? Please help me out here.

Can you show that sample of N=3 and M=14? I used a similar pattern for N=2 and N=3; can´t figure out a different pattern (perhaps because i was looking for cases until M=14).

This is the pattern i used for N = 3:

EEKKEE EEKKEE EEKKEE …

EEKKEE EEKKEE EEKKEE …

EEEEEE EEEEEE EEEEEE …

Each new block use 4 Knights for covering the whole block; except when M%6 = 1, where two Knights are enough (placing one on previous block):

EEKKEE EEKKEE E

EEKKEE EEKKKE K

EEEEEE EEEEEE E

I guess that should be a way for covering a block of 3 * 8 using only 7 Knights, seems to be logic now

Here’s some configurations for N=14 with 11 knights:

```
..KK.K....KKK.
..KK.......K..
.......KK.....
..KK.K....KK.K
..KK..........
.......KK....K
..KK.K....KKKK
..KK..........
.......KK.....
```

Thanks @hikarico

Sample for solving N=3 and M=14 case.

EEKKEK EEEEKKKK

EEKKEE EEEEEEEE

EEEEEE EKKEEEEE

Perfect, thank you.

Fix a column. If I place knight, it will affect upto two columns to the left. If n=3 there are six slots to the left, you can do DP with 2^6 states for the knights, and another 2^6 for the missing positions. Total is 2^{12} m states which is enough to solve the problem.

You can also reduce it to 3^6m states by making it ternary, but thats not needed