N-Queens

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

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

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

Пример: n = 5. Смотрите на [0, 4, 1]: в строке 3 все столбцы под боем, ветка там обрывается, а строке 2 больше нечего пробовать.

0123401234результаты—
свободная клеткаферзь выше, в спискетолько что поставленный ферзьклетка этой строки под боемполная доска, сохранена

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

01/82
сначала · назад · пуск · шаг
Скорость
1function solveNQueens(n):
2 results = []
3 place([])
4 return boards drawn from results
5
6function place(queens): // queens[r]: column in row r
7 if len(queens) == n:
8 add copy of queens to results
9 return
10 for c in free columns of row len(queens):
11 place(queens + [c]) // a new list: no undo
состояние
queens
–
c
–
results
–
нажмите шаг, чтобы вернуться

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

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

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

Сложность

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

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

Решить на LeetCode ↗

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