Colocar alfiles en un tablero de ajedrez

Hallar el número de formas de colocar $K$ alfiles en un tablero de ajedrez $N \times N$ de modo que ningún par de alfiles se ataquen entre sí.

Algoritmo

Este problema se puede resolver usando programación dinámica.

Enumeremos las diagonales del tablero de ajedrez como sigue: las diagonales negras tienen índices impares, las diagonales blancas tienen índices pares, y las diagonales se numeran en orden no decreciente del número de casillas que hay en ellas. Aquí hay un ejemplo para un tablero $5 \times 5$.

$$\begin{array}{ccccc}\mathbf{1}& 2& \mathbf{5}& 6& \mathbf{9}\\ 2& \mathbf{5}& 6& \mathbf{9}& 8\\ \mathbf{5}& 6& \mathbf{9}& 8& \mathbf{7}\\ 6& \mathbf{9}& 8& \mathbf{7}& 4\\ \mathbf{9}& 8& \mathbf{7}& 4& \mathbf{3}\\ \end{array}$$$$\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}

Sea D[i][j] el número de formas de colocar j alfiles en diagonales con índices hasta i que tienen el mismo color que la diagonal i. Entonces i = 1...2N-1 y j = 0...K.

Podemos calcular D[i][j] usando solo valores de D[i-2] (restamos 2 porque solo consideramos diagonales del mismo color que $i$). Hay dos formas de obtener D[i][j]. O bien colocamos todos los j alfiles en diagonales anteriores: entonces hay D[i-2][j] formas de lograrlo. O bien colocamos un alfil en la diagonal i y j-1 alfiles en diagonales anteriores. El número de formas de hacer esto es igual al número de casillas en la diagonal i menos j-1, porque cada uno de los j-1 alfiles colocados en diagonales anteriores bloqueará una casilla de la diagonal actual. El número de casillas en la diagonal i se puede calcular como sigue:

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

El caso base es sencillo: D[i][0] = 1, D[1][1] = 1.

Una vez que hemos calculado todos los valores de D[i][j], la respuesta se puede obtener como sigue: considerar todos los números posibles de alfiles colocados en diagonales negras i=0...K, con los números correspondientes de alfiles en diagonales blancas K-i. Los alfiles colocados en diagonales negras y blancas nunca se atacan entre sí, así que las colocaciones se pueden hacer de forma independiente. El índice de la última diagonal negra es 2N-1, el de la última blanca es 2N-2. Para cada i sumamos D[2N-1][i] * D[2N-2][K-i] a la respuesta.

Implementación

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