# Задача о n ферзях

!!! question

    Согласно правилам шахмат, ферзь может атаковать фигуры, находящиеся с ним в одной строке, одном столбце или на одной диагонали. Дано $n$ ферзей и доска размером $n \times n$, найдите расстановку, при которой все ферзи не могут атаковать друг друга.

Как показано на рисунке ниже, при $n = 4$ можно найти два решения. С точки зрения алгоритма поиска с возвратом, доска размером $n \times n$ имеет $n^2$ клеток, что дает все возможные выборы `choices`. В процессе последовательной расстановки ферзей состояние доски постоянно меняется, и доска в каждый момент времени является состоянием `state`.

![Решение задачи о 4 ферзях](../assets/solution_4_queens.png)

На рисунке ниже показаны три ограничения этой задачи: **несколько ферзей не могут находиться в одной строке, одном столбце и на одной диагонали**. Стоит отметить, что диагонали делятся на главные диагонали `\` и побочные диагонали `/`.

![Ограничения задачи о n ферзях](../assets/n_queens_constraints.png)

### Стратегия расстановки по строкам

Количество ферзей и количество строк доски равны $n$, поэтому легко получить вывод: **в каждой строке доски разрешено и необходимо разместить только одного ферзя**.

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

На рисунке ниже показан процесс расстановки по строкам для задачи о 4 ферзях. Из-за ограничений по размеру на рисунке развернута только одна ветвь поиска первой строки, и все варианты, не удовлетворяющие ограничениям по столбцам и диагоналям, были обрезаны.

![Стратегия расстановки по строкам](../assets/n_queens_placing.png)

По сути, **стратегия расстановки по строкам играет роль обрезки**, она избегает всех ветвей поиска, где в одной строке появляется несколько ферзей.

### Обрезка по столбцам и диагоналям

Для выполнения ограничения по столбцам мы можем использовать булев массив `cols` длиной $n$ для записи того, есть ли ферзь в каждом столбце. Перед каждым решением о размещении мы обрезаем столбцы, в которых уже есть ферзи, с помощью `cols` и динамически обновляем состояние `cols` при возврате.

!!! tip

    Обратите внимание, что начало матрицы находится в левом верхнем углу, где индекс строки увеличивается сверху вниз, а индекс столбца увеличивается слева направо.

Как же обработать ограничение по диагоналям? Пусть индексы строки и столбца некоторой клетки на доске равны $(row, col)$. Выбрав определенную главную диагональ в матрице, мы обнаружим, что разность индексов строки и столбца всех клеток на этой диагонали одинакова, **то есть $row - col$ для всех клеток на главной диагонали является постоянным значением**.

Другими словами, если две клетки удовлетворяют условию $row_1 - col_1 = row_2 - col_2$, то они обязательно находятся на одной главной диагонали. Используя эту закономерность, мы можем использовать массив `diags1`, показанный на рисунке ниже, для записи того, есть ли ферзь на каждой главной диагонали.

Аналогично, **для всех клеток на побочной диагонали $row + col$ является постоянным значением**. Мы также можем использовать массив `diags2` для обработки ограничения по побочным диагоналям.

![Обработка ограничений по столбцам и диагоналям](../assets/n_queens_cols_diagonals.png)

### Реализация кода

Обратите внимание, что в квадратной матрице размерности $n$ диапазон $row - col$ составляет $[-n + 1, n - 1]$, а диапазон $row + col$ составляет $[0, 2n - 2]$, поэтому количество главных и побочных диагоналей равно $2n - 1$, то есть длина массивов `diags1` и `diags2` равна $2n - 1$.

```src
[file]{n_queens}-[class]{}-[func]{n_queens}
```

Расстановка по строкам выполняется $n$ раз, с учетом ограничения по столбцам от первой строки до последней строки имеется $n$, $n-1$, $\dots$, $2$, $1$ вариантов выбора, что требует $O(n!)$ времени. При записи решения необходимо скопировать матрицу `state` и добавить ее в `res`, операция копирования занимает $O(n^2)$ времени. Таким образом, **общая временная сложность составляет $O(n! \cdot n^2)$**. На самом деле, обрезка по диагональным ограничениям также может значительно сократить пространство поиска, поэтому эффективность поиска часто лучше указанной временной сложности.

Массив `state` использует $O(n^2)$ пространства, массивы `cols`, `diags1` и `diags2` используют по $O(n)$ пространства. Максимальная глубина рекурсии равна $n$, используя $O(n)$ пространства стека. Таким образом, **пространственная сложность составляет $O(n^2)$**.