Skip to content

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.

$$\begin{matrix} \bf{1} & 2 & \bf{5} & 6 & \bf{9} \\\ 2 & \bf{5} & 6 & \bf{9} & 8 \\\ \bf{5} & 6 & \bf{9} & 8 & \bf{7} \\\ 6 & \bf{9} & 8 & \bf{7} & 4 \\\ \bf{9} & 8 & \bf{7} & 4 & \bf{3} \\\ \end{matrix}$$

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;
}