Задача N ферзей: бэктрекинг по строкам, диагонали r−c и r+c и битовые маски

Коротко

N ферзей — эталонная задача на перебор с возвратом. Общий шаблон бэктрекинга уже разобран в отдельной статье, там ферзи упоминаются мимоходом. Здесь займёмся только ими: откуда берутся формулы диагоналей, почему перебор идёт по строкам, как ускорить проверку до одной операции и как выглядит битовая версия, которую любят просить в продолжение.

Условие

Нужно расставить $n$ ферзей на доске $n \times n$ так, чтобы никакие два не били друг друга. Ферзь бьёт всю свою строку, весь столбец и обе диагонали.

На LeetCode есть два варианта:

• 51. N-Queens — вернуть все расстановки, каждая доска как список строк из . и Q;
• 52. N-Queens II — вернуть только их количество.

Для $n = 4$ решений два:

.Q..      ..Q.
...Q      Q...
Q...      ...Q
..Q.      .Q..

Почему перебор по строкам

Самый прямолинейный подход — выбрать $n$ клеток из $n^2$ и проверить каждую комбинацию. Для $n = 8$ это $\binom{64}{8} \approx 4{,}4$ миллиарда вариантов. Так задачу никто не решает, но с этой оценки удобно начать рассуждение на собеседовании.

Первое наблюдение: два ферзя в одной строке бьют друг друга. Значит, в каждой строке стоит ровно один ферзь, и расстановку можно записать массивом queens, где queens[r] — столбец ферзя в строке r. Вариантов становится $n^n$, для восьми это около 16,7 миллиона.

Второе наблюдение: в каждом столбце тоже ровно один ферзь. Тогда queens — перестановка чисел $0..n-1$, и вариантов $n! = 40\,320$. Остаётся проверить диагонали.

Бэктрекинг идёт дальше: мы не генерируем перестановку целиком, а строим её строка за строкой и бросаем ветку, как только новый ферзь оказывается под боем. Для $n = 8$ такой перебор делает 2057 рекурсивных вызовов вместо 40 320 полных перестановок.

Как узнать диагональ клетки

Это центральная идея задачи. Возьмём клетку $(r, c)$, где $r$ — строка, $c$ — столбец.

• Если идти по диагонали вниз-вправо, строка и столбец растут одновременно: $(r+1, c+1)$, $(r+2, c+2)$… Разность $r - c$ не меняется.
• Если идти вниз-влево, строка растёт, а столбец убывает: $(r+1, c-1)$, $(r+2, c-2)$… Не меняется сумма $r + c$.

Получается, что у всех клеток одной диагонали одинаковое $r - c$, а у всех клеток одной антидиагонали одинаковое $r + c$. На доске 4×4 это выглядит так:

r - c:          r + c:
 0 -1 -2 -3      0  1  2  3
 1  0 -1 -2      1  2  3  4
 2  1  0 -1      2  3  4  5
 3  2  1  0      3  4  5  6

Каждое число — это номер диагонали. Всего диагоналей каждого типа $2n - 1$: значения $r - c$ лежат от $-(n-1)$ до $n-1$, значения $r + c$ — от $0$ до $2n-2$.

Значит, ферзь в клетке $(r, c)$ занимает четыре «ресурса»: строку $r$, столбец $c$, диагональ $r - c$ и антидиагональ $r + c$. Строки мы занимаем по порядку и о них не думаем, остальные три храним в множествах.

Наивная проверка

Прежде чем вводить множества, посмотрим на вариант, который многие пишут первым: для новой клетки пройти по всем уже поставленным ферзям.

def is_safe(queens, r, c):
    for pr, pc in enumerate(queens):
        if pc == c or abs(pr - r) == abs(pc - c):
            return False
    return True


def count_naive(n):
    queens = []

    def bt(r):
        if r == n:
            return 1
        total = 0
        for c in range(n):
            if is_safe(queens, r, c):
                queens.append(c)
                total += bt(r + 1)
                queens.pop()
        return total

    return bt(0)


print([count_naive(n) for n in range(1, 9)])  # [1, 0, 0, 2, 10, 4, 40, 92]

Условие abs(pr - r) == abs(pc - c) — та же идея диагоналей в другой записи: две клетки лежат на одной диагонали, если смещения по строке и столбцу равны по модулю. Решение правильное, но каждая проверка стоит $O(n)$. На собеседовании его можно назвать первым, а потом сказать, что проверку можно сделать за $O(1)$.

Решение с множествами

def solve_n_queens(n):
    cols, diag1, diag2 = set(), set(), set()
    queens = []  # queens[r] = столбец ферзя в строке r
    result = []

    def backtrack(r):
        if r == n:
            result.append(["." * c + "Q" + "." * (n - c - 1) for c in queens])
            return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            queens.append(c)
            backtrack(r + 1)
            queens.pop()
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)

    backtrack(0)
    return result


for row in solve_n_queens(4)[0]:
    print(row)
# .Q..
# ...Q
# Q...
# ..Q.
print(len(solve_n_queens(4)), len(solve_n_queens(8)))  # 2 92

Структура ровно та же, что в любом бэктрекинге:

1. База: дошли до строки n — значит, все ферзи стоят, записываем доску.
2. Выбор: перебираем столбец для текущей строки.
3. Отсечение: если столбец или одна из диагоналей заняты, клетку пропускаем.
4. Шаг вперёд: помечаем ресурсы и уходим в следующую строку.
5. Откат: снимаем пометки, чтобы следующий выбор видел доску такой, какой она была до нас.

Доску в виде строк собираем только в момент, когда решение найдено. Держать двумерный массив символов и менять в нём клетки можно, но это лишняя работа на каждом шаге.

Массивы вместо множеств

Множества в Python удобны, но у диагоналей известный диапазон, поэтому подойдут обычные булевы массивы. Отрицательное r - c сдвигаем на n - 1:

def solve_arrays(n):
    cols = [False] * n
    diag1 = [False] * (2 * n - 1)  # индекс r - c + n - 1
    diag2 = [False] * (2 * n - 1)  # индекс r + c
    queens, result = [], []

    def backtrack(r):
        if r == n:
            result.append(queens[:])
            return
        for c in range(n):
            a, b = r - c + n - 1, r + c
            if cols[c] or diag1[a] or diag2[b]:
                continue
            cols[c] = diag1[a] = diag2[b] = True
            queens.append(c)
            backtrack(r + 1)
            queens.pop()
            cols[c] = diag1[a] = diag2[b] = False

    backtrack(0)
    return result


print(solve_arrays(4))  # [[1, 3, 0, 2], [2, 0, 3, 1]]

Здесь решения записаны компактно, как массивы столбцов: [1, 3, 0, 2] означает, что в строке 0 ферзь стоит в столбце 1, в строке 1 — в столбце 3 и так далее. Обратите внимание на queens[:]: без копии в result попадёт ссылка на один и тот же список, который к концу перебора опустеет.

В языках вроде Java или C++ вариант с массивами естественнее: там нет отрицательных индексов, и смещение n - 1 придётся делать в любом случае.

Разбор на примере n = 4

Пройдём начало перебора руками. Запись $(r, c)$ — ферзь в строке $r$, столбце $c$.

1. Ставим $(0, 0)$. Заняты столбец 0, диагональ $0$, антидиагональ $0$.
2. Строка 1: столбец 0 занят, у столбца 1 $r - c = 0$ — та же диагональ. Столбец 2 свободен, ставим $(1, 2)$.
3. Строка 2: столбцы 0 и 2 заняты, у столбца 1 $r + c = 3$ — антидиагональ ферзя $(1, 2)$, у столбца 3 $r - c = -1$ — его же диагональ. Тупик, откатываемся.
4. Снимаем $(1, 2)$, пробуем $(1, 3)$. В строке 2 подходит только $(2, 1)$.
5. Строка 3: свободен лишь столбец 2, но у клетки $(3, 2)$ $r - c = 1$, как у $(2, 1)$. Снова тупик, и в строке 2 других вариантов нет.
6. В строке 1 столбцы кончились, откатываемся до строки 0 и ставим $(0, 1)$.
7. Дальше всё сходится: $(1, 3)$, $(2, 0)$, $(3, 2)$. Это первое решение [1, 3, 0, 2].

Важно увидеть, что ферзь $(0, 0)$ оказался бесперспективным, и мы выяснили это, не дойдя ни до одной полной расстановки. Именно ради таких ранних отказов бэктрекинг и нужен.

Битовая версия для подсчёта

Если нужно только количество решений (LeetCode 52), доску можно не хранить вовсе. Занятые столбцы и диагонали текущей строки укладываются в три целых числа, где бит $i$ отвечает за столбец $i$.

def total_n_queens(n):
    full = (1 << n) - 1

    def dfs(cols, d1, d2):
        if cols == full:
            return 1
        count = 0
        free = full & ~(cols | d1 | d2)
        while free:
            bit = free & -free
            free ^= bit
            count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
        return count

    return dfs(0, 0, 0)


print([total_n_queens(n) for n in range(1, 13)])
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200]

Разберём строку за строкой:

• cols — занятые столбцы. Когда в ней все $n$ бит единичные, ферзи стоят во всех строках.
• d1 и d2 — столбцы текущей строки, которые бьются по диагоналям от уже поставленных ферзей. Это главное отличие от версии с множествами: мы храним не номера диагоналей, а их проекцию на текущую строку.
• free = full & ~(cols | d1 | d2) — свободные клетки строки одной операцией. & full отрезает биты старше $n$-го, которые появились после инверсии.
• free & -free выделяет младший единичный бит. Это тот же трюк, что в дереве Фенвика, подробнее о нём в статье про битовые операции.
• free ^= bit убирает этот бит из кандидатов.
• При переходе на следующую строку диагональ, идущая в сторону старших битов, смещается на одну позицию: << 1. Диагональ в другую сторону — >> 1. Маска & full нужна, чтобы биты, ушедшие за край доски, не накапливались.

Направление сдвигов значения не имеет: доска симметрична, поэтому можно поменять << 1 и >> 1 местами, ответ не изменится. Важно лишь, чтобы d1 всегда сдвигалась в одну сторону, а d2 — в другую.

Та же функция на JavaScript:

function totalNQueens(n) {
  const full = (1 << n) - 1

  function dfs(cols, d1, d2) {
    if (cols === full) return 1
    let count = 0
    let free = full & ~(cols | d1 | d2)
    while (free) {
      const bit = free & -free
      free ^= bit
      count += dfs(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
    }
    return count
  }

  return dfs(0, 0, 0)
}

console.log([4, 8, 10, 12].map(totalNQueens)) // [ 2, 92, 724, 14200 ]

Битовые операции в JavaScript работают с 32-битными целыми, так что для доски больше 30×30 этот код уже не годится. На практике до таких размеров перебор всё равно не доживает.

Насколько это быстрее? На одной и той же машине в CPython для $n = 12$ версия с множествами, которая ещё и собирает доски, работала около 0,7 с, битовая — около 0,2 с. Асимптотика не меняется, выигрыш даёт константа: вместо трёх поисков в хеш-таблице одна побитовая операция, а перебираются только свободные столбцы, а не все $n$.

Сколько решений бывает

Числа для малых $n$ полезно помнить хотя бы частично: они помогают проверить свою реализацию.

Вторая строка — число решений с точностью до поворотов и отражений доски. Знаменитые «12 решений» задачи о восьми ферзях — это именно они, а всего расстановок 92. Все значения в таблице посчитаны кодом из этой статьи и сверены с простым перебором перестановок для $n \le 8$.

Что стоит отметить:

• Для $n = 2$ и $n = 3$ решений нет: любые два ферзя на такой маленькой доске бьют друг друга, если стоят в соседних строках.
• Последовательность не монотонна: для $n = 6$ решений меньше, чем для $n = 5$.
• Для любого $n \ge 4$ решение существует, и одну расстановку можно построить явной формулой за $O(n)$ без перебора. Но формула неочевидна, и на собеседовании её не ждут.
• Количество растёт быстро, и простой формулы для него не известно. Это последовательность A000170 в OEIS.

Сложность

Время. Грубая верхняя оценка — $O(n!)$: в строке 0 не больше $n$ вариантов, в строке 1 не больше $n - 1$ и так далее. Реальное число узлов дерева гораздо меньше, потому что диагонали отсекают ветки, но точной формулы для него нет. Для LeetCode 51 к перебору добавляется сборка ответа: каждое решение превращается в $n$ строк длины $n$.

Память. $O(n)$ на глубину рекурсии и множества (или массивы длины $2n - 1$). Плюс сам ответ: в LeetCode 51 это $S \cdot n^2$ символов, где $S$ — число решений. В битовой версии только стек глубины $n$.

На собеседовании честный ответ звучит так: «в худшем случае $O(n!)$, на практике значительно меньше из-за отсечений; память $O(n)$ без учёта ответа». Пытаться вывести точную оценку не нужно.

Типичные ошибки

Забыть откат. Если после рекурсивного вызова не убрать столбец и диагонали из множеств, они останутся занятыми для всех последующих веток. Для $n = 8$ такой код находит 0 решений вместо 92: первая ветка помечает ресурсы, а следующие уже не могут ничего поставить.

Перепутать формулы диагоналей. Используют r - c для одной и r - c для другой или пишут abs(r - c). Модуль склеивает разные диагонали: клетки $(0, 1)$ и $(1, 0)$ получат одинаковое значение 1, хотя лежат на разных диагоналях. Ответ становится меньше правильного.

Отрицательный индекс в массиве. В Python diag1[r - c] с отрицательным индексом не упадёт, а молча обратится к элементу с конца массива. Ошибки не будет, ответ будет неверным. Сдвигайте на n - 1 или используйте множество.

Сохранить ссылку вместо копии. result.append(queens) вместо result.append(queens[:]). Все элементы результата — один и тот же список, к концу перебора пустой.

Проверять строки. Множество занятых строк не нужно: строки заполняются строго по порядку, по одной. Лишняя проверка не ломает решение, но показывает интервьюеру, что вы не до конца поняли, зачем перебор идёт по строкам.

Забыть маску в битовой версии. Без & full в d1 копятся биты старше $n$-го. На ответ это не влияет, пока free маскируется, но числа растут, а в языках с фиксированной разрядностью биты уходят за край слова. Привычка маскировать сразу избавляет от таких сюрпризов.

На собеседовании

N ферзей обычно дают в двух ситуациях. Первая — как задачу на кодинг уровня hard, где ждут рабочий бэктрекинг с проверкой за $O(1)$. Вторая — как устный вопрос «как бы вы решили», чтобы проверить, понимаете ли вы отсечения.

Хороший порядок ответа:

1. Сказать, что в каждой строке ровно один ферзь, поэтому перебираем столбец для каждой строки.
2. Объяснить, почему $r - c$ и $r + c$ однозначно задают диагонали.
3. Написать решение с тремя множествами и явно проговорить откат.
4. Оценить сложность: $O(n!)$ сверху, $O(n)$ памяти.
5. Если спросят про ускорение — рассказать про битовые маски.

Частые продолжения:

• Только количество — битовая версия, доску хранить не нужно.
• Найти любое одно решение — тот же бэктрекинг, но с выходом при первом найденном ответе (функция возвращает True, и вызывающий код прекращает цикл).
• Учесть симметрию — можно перебирать в первой строке только левую половину столбцов и удваивать ответ, отдельно обработав средний столбец при нечётном $n$. Это ускоряет подсчёт примерно вдвое.
• Другие фигуры — ладьи (только столбцы, ответ $n!$) или ограничения на запрещённые клетки. Шаблон не меняется, меняется проверка.

Похожие задачи

Та же схема «выбор → проверка → шаг → откат» встречается во многих задачах:

• Поиск слова в сетке — бэктрекинг по клеткам, где «ресурс» — посещённая клетка, и её тоже нужно освобождать при возврате. Задачу можно решить в тренажёре.
• Сумма комбинаций — перебор с отсечением по сумме.
• Судоку — те же множества по строкам, столбцам и квадратам 3×3 вместо диагоналей.
• Раскраска графа — перебор цветов вершин с проверкой соседей.

Если битовые маски в переборе понравились, следующий шаг — ДП по подмножествам, где те же приёмы используются уже для хранения состояний. А чтобы увереннее чувствовать себя с рекурсией в целом, пригодится статья про рекурсию.