# Placing Bishops on a Chessboard¶

Find the number of ways to place $K$ bishops on an $N \times N$ chessboard so that no two bishops attack each other.

## Algorithm¶

This problem can be solved using dynamic programming.

Let's enumerate the diagonals of the chessboard as follows: black diagonals have odd indices, white diagonals have even indices, and the diagonals are numbered in non-decreasing order of the number of squares in them. Here is an example for a $5 \times 5$ chessboard.

Let `D[i][j]`

denote the number of ways to place `j`

bishops on diagonals with indices up to `i`

which have the same color as diagonal `i`

.
Then `i = 1...2N-1`

and `j = 0...K`

.

We can calculate `D[i][j]`

using only values of `D[i-2]`

(we subtract 2 because we only consider diagonals of the same color as $i$).
There are two ways to get `D[i][j]`

.
Either we place all `j`

bishops on previous diagonals: then there are `D[i-2][j]`

ways to achieve this.
Or we place one bishop on diagonal `i`

and `j-1`

bishops on previous diagonals.
The number of ways to do this equals the number of squares in diagonal `i`

minus `j-1`

, because each of `j-1`

bishops placed on previous diagonals will block one square on the current diagonal.
The number of squares in diagonal `i`

can be calculated as follows:

```
int squares (int i) {
if (i & 1)
return i / 4 * 2 + 1;
else
return (i - 1) / 4 * 2 + 2;
}
```

The base case is simple: `D[i][0] = 1`

, `D[1][1] = 1`

.

Once we have calculated all values of `D[i][j]`

, the answer can be obtained as follows:
consider all possible numbers of bishops placed on black diagonals `i=0...K`

, with corresponding numbers of bishops on white diagonals `K-i`

.
The bishops placed on black and white diagonals never attack each other, so the placements can be done independently.
The index of the last black diagonal is `2N-1`

, the last white one is `2N-2`

.
For each `i`

we add `D[2N-1][i] * D[2N-2][K-i]`

to the answer.

## Implementation¶

```
int bishop_placements(int N, int K)
{
if (K > 2 * N - 1)
return 0;
vector<vector<int>> D(N * 2, vector<int>(K + 1));
for (int i = 0; i < N * 2; ++i)
D[i][0] = 1;
D[1][1] = 1;
for (int i = 2; i < N * 2; ++i)
for (int j = 1; j <= K; ++j)
D[i][j] = D[i-2][j] + D[i-2][j-1] * (squares(i) - j + 1);
int ans = 0;
for (int i = 0; i <= K; ++i)
ans += D[N*2-1][i] * D[N*2-2][K-i];
return ans;
}
```