N-Queens II

Сложная№52строка за строкой

Нужно поставить n шахматных ферзей на доску n × n так, чтобы никакие два не стояли в одной строке, столбце или на одной диагонали, и вернуть, сколько всего способов. Нужно только число, доски не нужны. Наш пример: при n = 5 способов 10.

52 N-Queens IIРазбор · 1×

Пример: n = 5. Смотрите на строку 1 сразу после ферзя в (0, 0): у (1, 1) r - c = 0, а 0 уже есть в d1, значит, это та же диагональ.

0123401234
свободная клеткаферзь вышетолько что поставленный ферзьзанято: столбец или диагональ в множествеполная доска: ещё один способ

Считаем, сколькими способами можно поставить 5 ферзей на доску 5 × 5 так, чтобы никто никого не бил

01/82
сначала · назад · пуск · шаг
Скорость
1function totalNQueens(n):
2 count = 0
3 place(0, {}, {}, {})
4 return count
5
6function place(r, cols, d1, d2): // d1: r-c, d2: r+c
7 if r == n:
8 count = count + 1
9 return
10 for c with c ∉ cols, r-c ∉ d1, r+c ∉ d2:
11 place(r + 1, cols + c, d1 + (r-c), d2 + (r+c))
состояние
r
–
c
–
cols
–
d1
–
d2
–
count
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Вдоль диагонали ↘ r и c растут вместе, поэтому r - c не меняется; вдоль диагонали ↙ не меняется r + c. Ферзь занимает свой столбец, своё r - c и своё r + c, поэтому, бьют ли клетку, видно по трём множествам за один взгляд.
  2. Каждый вызов заполняет одну строку столбцом, который не бьёт никто сверху, поэтому вызов с r = n держит полную верную доску и добавляет ровно один способ, а строка без свободного столбца сразу обрывает ветку.
  3. Каждый вызов получает новые множества со своим ферзём, а множества вызывающего остаются прежними: подъём убирает ферзя без всякой отмены.

Сложность

Время не больше O(n!): в строке 0 можно попробовать n столбцов, в строке 1 не больше n − 1 и так далее; каждая проверка по множествам — O(1), хотя их копия стоит O(n) на вызов. Память O(n²): глубина до n вызовов, у каждого множества до n чисел.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.