Розставлення слонів на шахівниці

Знайдіть кількість способів розставити $K$ слонів на шахівниці розміру $N \times N$ так, щоб жодні два слони не били один одного.

Коли підходить цей алгоритм?

• Чи задача про підрахунок розставлень фігур, що б'ють по діагоналях (слони), на квадратній шахівниці?
• Чи можна звести взаємні удари до незалежності по двох наборах діагоналей (чорні/білі), щоб порахувати кожен набір окремо?
• Чи це підрахунок розставлень, а не пошук однієї конфігурації? (для загального підрахунку розподілів → Біноміальні коефіцієнти)

Алгоритм

Цю задачу можна розв'язати за допомогою динамічного програмування.

Занумеруємо діагоналі шахівниці так: чорні діагоналі мають непарні індекси, білі — парні, а самі діагоналі нумеруються в незменшуваному порядку за кількістю клітинок у них. Ось приклад для шахівниці $5 \times 5$.

$$\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}$$

Нехай D[i][j] позначає кількість способів розставити j слонів на діагоналях з індексами до i, які мають той самий колір, що й діагональ i. Тоді i = 1...2N-1 і j = 0...K.

Ми можемо обчислити D[i][j], використовуючи лише значення D[i-2] (ми віднімаємо 2, бо розглядаємо тільки діагоналі того самого кольору, що й $i$). Є два способи отримати D[i][j]. Або ми розставляємо всі j слонів на попередніх діагоналях: тоді є D[i-2][j] способів це зробити. Або ми ставимо одного слона на діагональ i, а j-1 слонів — на попередні діагоналі. Кількість способів зробити це дорівнює кількості клітинок у діагоналі i мінус j-1, бо кожен з j-1 слонів, розставлених на попередніх діагоналях, заблокує одну клітинку на поточній діагоналі. Кількість клітинок у діагоналі i можна обчислити так:

C++

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

Python

def squares(i: int) -> int:
    if i & 1:
        return i // 4 * 2 + 1
    else:
        return (i - 1) // 4 * 2 + 2

TypeScript

function squares(i: number): number {
  if (i & 1) return Math.floor(i / 4) * 2 + 1;
  else return Math.floor((i - 1) / 4) * 2 + 2;
}

Go

func squares(i int) int {
	if i&1 != 0 {
		return i/4*2 + 1
	}
	return (i-1)/4*2 + 2
}

Базовий випадок простий: D[i][0] = 1, D[1][1] = 1.

Коли ми обчислили всі значення D[i][j], відповідь можна отримати так: розглянемо всі можливі кількості слонів, розставлених на чорних діагоналях i=0...K, з відповідними кількостями слонів на білих діагоналях K-i. Слони, розставлені на чорних і білих діагоналях, ніколи не б'ють один одного, тому розставлення можна робити незалежно. Індекс останньої чорної діагоналі — 2N-1, останньої білої — 2N-2. Для кожного i додаємо D[2N-1][i] * D[2N-2][K-i] до відповіді.

Реалізація

C++

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

Python

def bishop_placements(N: int, K: int) -> int:
    if K > 2 * N - 1:
        return 0

    # D[i][j] — кількість способів розставити j слонів на діагоналях
    # до i включно того самого кольору, що й i.
    D = [[0] * (K + 1) for _ in range(N * 2)]
    for i in range(N * 2):
        D[i][0] = 1
    if K >= 1:
        D[1][1] = 1
    for i in range(2, N * 2):
        for j in range(1, K + 1):
            D[i][j] = D[i - 2][j] + D[i - 2][j - 1] * (squares(i) - j + 1)

    ans = 0
    for i in range(K + 1):
        ans += D[N * 2 - 1][i] * D[N * 2 - 2][K - i]
    return ans

TypeScript

// Кількість розставлень зростає експоненційно, тож рахуємо в BigInt,
// аби уникнути переповнення number.
function bishopPlacements(N: number, K: number): bigint {
  if (K > 2 * N - 1) return 0n;

  // D[i][j] — кількість способів розставити j слонів на діагоналях
  // до i включно того самого кольору, що й i.
  const D: bigint[][] = Array.from({ length: N * 2 }, () =>
    new Array<bigint>(K + 1).fill(0n)
  );
  for (let i = 0; i < N * 2; i++) D[i][0] = 1n;
  if (K >= 1) D[1][1] = 1n;
  for (let i = 2; i < N * 2; i++)
    for (let j = 1; j <= K; j++)
      D[i][j] = D[i - 2][j] + D[i - 2][j - 1] * BigInt(squares(i) - j + 1);

  let ans = 0n;
  for (let i = 0; i <= K; i++)
    ans += D[N * 2 - 1][i] * D[N * 2 - 2][K - i];
  return ans;
}

Go

func bishopPlacements(N, K int) int64 {
	if K > 2*N-1 {
		return 0
	}

	// D[i][j] — кількість способів розставити j слонів на діагоналях
	// до i включно того самого кольору, що й i.
	D := make([][]int64, N*2)
	for i := range D {
		D[i] = make([]int64, K+1)
		D[i][0] = 1
	}
	if K >= 1 {
		D[1][1] = 1
	}
	for i := 2; i < N*2; i++ {
		for j := 1; j <= K; j++ {
			D[i][j] = D[i-2][j] + D[i-2][j-1]*int64(squares(i)-j+1)
		}
	}

	var ans int64 = 0
	for i := 0; i <= K; i++ {
		ans += D[N*2-1][i] * D[N*2-2][K-i]
	}
	return ans
}