Colocando Bispos em um Tabuleiro de Xadrez

Encontre o número de maneiras de colocar $K$ bispos em um tabuleiro de xadrez $N \times N$ para que dois bispos não se ataquem.

Algoritmo

Esse problema pode ser resolvido usando a programação dinâmica.

Vamos enumerar as diagonais do tabuleiro de xadrez da seguinte forma: diagonais pretas têm índices ímpares, diagonais brancas têm índices pares e as diagonais são numeradas em ordem não decrescente do número de quadrados nelas. Aqui está um exemplo para um tabuleiro de xadrez $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}$$

Deixe que D[i][j] denote número de maneiras de colocar j bispos em diagonais com índices até i que têm a mesma cor que a diagonal i. Assim, i = 1...2N-1 e j = 0...K.

Podemos calcular D[i][j] usando apenas valores de D[i-2] (subtraímos 2 porque consideramos apenas diagonais da mesma cor que $i$). Existem duas maneiras de obter D[i][j]. Ou colocamos todos os j bispos nas diagonais anteriores: então existem D[i-2][j] maneiras de conseguir isso. Ou colocamos um bispo na diagonal i e j-1 bispos nas diagonais anteriores. O número de maneiras de fazer isso é igual ao número de quadrados na diagonal i menos j-1, porque cada um dos j-1 bispos colocados nas diagonais anteriores bloqueará um quadrado na diagonal atual. O número de quadrados na diagonal i pode ser calculado da seguinte forma:

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

O caso base é simples: D[i][0] = 1, D[1][1] = 1.

Uma vez calculados todos os valores de D[i][j], a resposta pode ser obtida da seguinte forma: considere todos os números possíveis de bispos colocados nas diagonais pretas i=0...K, com números correspondentes de bispos nas diagonais brancas K-i. Os bispos colocados nas diagonais pretas e brancas nunca se atacam, de modo que as colocações podem ser feitas independentemente. O índice da última diagonal preta é 2N-1, o último branco é 2N-2. Para cada i adicionamos D[2N-1][i] * D[2N-2][K-i] à resposta.

Implementação

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