9. N Queens

«Шахматы — это геометрия ограничений, где каждый шаг сужает свободу всех остальных фигур».
— Эдсгер Дейкстра

Задача о $N$ ферзях (N-Queens, LeetCode 51) — историческая классика компьютерных наук, сформулированная в 1848 году шахматистом Максом Беззелем и математически исследованная Карлом Гауссом.

Условие: На шахматной доске $N \times N$ требуется расставить $N$ ферзей таким образом, чтобы ни один ферзь не атаковал другого. Ферзь бьет по горизонтали, вертикали и обеим диагоналям. Необходимо вернуть все возможные уникальные конфигурации доски.

В отличие от простых перестановок, здесь ограничения носят глобальный геометрический характер. Для senior-разработчика на Go эта задача — визитная карточка владения алгоритмической оптимизацией: как свести проверку пересечений с $O(N)$ к регистровым операциям за $O(1)$ и как использовать битовую арифметику для мгновенного нахождения свободных позиций.

Архитектура: Инвариант построчной расстановки

Поскольку никакой ферзь не может делить строку с другим, мы сразу отсекаем перебор клеток: в каждой строке стоит ровно один ферзь.
Задача сводится к выбору номера столбца col для каждой строки row = 0, 1, ..., n-1.

Для мгновенной ($O(1)$) проверки допустимости клетки (row, col) используются математические свойства координатной сетки:

1. Вертикаль (Столбец): ферзи не могут иметь одинаковый col.
2. Главная диагональ (): разность координат row - col постоянна вдоль диагонали. Диапазон значений: от $-(N-1)$ до $+(N-1)$. Сдвигая на $N-1$, получаем индекс в массиве:
   $$\text{idx}_{\text{diag1}} = \text{row} - \text{col} + N - 1 \quad \in [0, \; 2N-2]$$
3. Побочная диагональ (/): сумма координат row + col постоянна вдоль диагонали. Диапазон:
   $$\text{idx}_{\text{diag2}} = \text{row} + \text{col} \quad \in [0, \; 2N-2]$$

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc

    subgraph Board["Доска 4x4: Решение [ . Q . . ], [ . . . Q ], [ Q . . . ], [ . . Q . ]"]
        R0["Строка 0: [ . Q . . ] (col = 1)"]:::process
        R1["Строка 1: [ . . . Q ] (col = 3)"]:::process
        R2["Строка 2: [ Q . . . ] (col = 0)"]:::process
        R3["Строка 3: [ . . Q . ] (col = 2)"]:::success
    end

    Start["Старт: row = 0"]:::entry --> Try0["row 0: ставим col = 1"]:::process
    Try0 --> Try1["row 1: ставим col = 3"]:::process
    Try1 --> Try2["row 2: ставим col = 0"]:::process
    Try2 --> Try3["row 3: ставим col = 2"]:::process
    Try3 --> Valid["row == 4: Все 4 ферзя в безопасности!"]:::success

    Try0 -.->|"Попытка col = 0"| Conflict["Конфликт диагонали или вертикали!"]:::error
  

Идиоматичная реализация на Go

package main

// solveNQueens возвращает все допустимые конфигурации доски N x N.
// Временная сложность: O(N!), существенно меньше благодаря диагональному отсечению
// Пространственная сложность: O(N) дополнительной памяти под стек и маски
func solveNQueens(n int) [][]string {
    if n <= 0 {
        return nil
    }

    var result [][]string

    // Массивы флагов для мгновенной O(1) проверки атак
    cols := make([]bool, n)
    diag1 := make([]bool, 2*n-1) // Главные диагонали: row - col + n - 1
    diag2 := make([]bool, 2*n-1) // Побочные диагонали: row + col

    // queens[row] хранит индекс столбца, в котором стоит ферзь
    queens := make([]int, n)

    // Предвыделенный буфер строки для исключения аллокаций при формировании ответа
    rowTemplate := make([]byte, n)
    for i := range rowTemplate {
        rowTemplate[i] = '.'
    }

    var backtrack func(row int)
    backtrack = func(row int) {
        // Все ферзи успешно расставлены
        if row == n {
            board := make([]string, n)
            for r := 0; r < n; r++ {
                // Копируем шаблон точек и ставим ферзя в позицию queens[r]
                rowBytes := append([]byte(nil), rowTemplate...)
                rowBytes[queens[r]] = 'Q'
                board[r] = string(rowBytes)
            }
            result = append(result, board)
            return
        }

        for col := 0; col < n; col++ {
            d1 := row - col + n - 1
            d2 := row + col

            // Если вертикаль или хотя бы одна диагональ под боем — пропуск
            if cols[col] || diag1[d1] || diag2[d2] {
                continue
            }

            // Choose
            queens[row] = col
            cols[col], diag1[d1], diag2[d2] = true, true, true

            // Explore
            backtrack(row + 1)

            // Unchoose (откат всех полей)
            cols[col], diag1[d1], diag2[d2] = false, false, false
        }
    }

    backtrack(0)
    return result
}

Взгляд под капот: Mechanical Sympathy и битовая магия

Для максимальной производительности (например, в задаче N-Queens II на подсчет числа решений) булевы массивы заменяются тремя регистрами CPU: cols, d1, d2.

// available содержит 1 в тех битах, где клетка безопасна
available := ^(cols | d1 | d2) & ((1 << n) - 1)
for available != 0 {
    // Выделение младшего единичного бита (Kernighan bit trick):
    bit := available & -available
    available -= bit
    // При переходе на row + 1 главная диагональ сдвигается влево, побочная — вправо!
    backtrack(row+1, cols|bit, (d1|bit)<<1, (d2|bit)>>1)
}

• Операция (d1 | bit) << 1 автоматически смещает диагональные лучи атаки для следующей строки!
• Нет ни одного обращения к памяти — алгоритм исполняется целиком в регистрах процессора.
• Время решения для $N = 14$ падает с секунд до миллисекунд.

Подводные камни и вопросы с собеседований

Резюме

N-Queens — классический образец поиска с геометрическими ограничениями:

• Построчная декомпозиция гарантирует отсутствие горизонтальных коллизий.
• Математические проекции row - col + n - 1 и row + col сводят проверки к $O(1)$.
• Инвариант отката удерживает расход памяти в строгих границах $O(N)$.

В заключительной задаче кластера Backtracking мы разберем генерацию синтаксически корректных скобочных последовательностей: 10. Generate Parentheses.