N-Queens II

В каждой строке должна быть ровно одна ферзь, поэтому расстановка — это список cols, в котором cols[r] — столбец с ферзём в строке r. Каждая запись может указывать на любой из n столбцов, поэтому существует n^n списков. Перебирайте их, как считает одометр: увеличивайте последнюю запись на единицу, а когда она становится больше n-1, сбрасывайте её до 0 и переносите единицу на предыдущую запись.

Для каждого списка сравните каждую пару строк i < j. Два ферзя атакуют друг друга, если они стоят в одном столбце — cols[i] == cols[j] — или на одной диагонали. На диагонали при перемещении вниз на одну строку вы перемещаетесь на один столбец влево или вправо, поэтому два ферзя стоят на одной диагонали тогда и только тогда, когда разница между столбцами равна разнице между строками: |cols[i] - cols[j]| == j - i. Список, который проходит все проверки пар, задаёт допустимую доску. Поскольку проверяется каждый список, ни один вариант не пропускается и ни один не учитывается дважды.

Этот способ работает медленно, потому что он никогда не останавливается раньше времени. Если два ферзя стоят на одной диагонали в первых двух строках, доска уже заведомо не подходит, однако одометр всё равно перебирает все n^(n-2) вариантов заполнения остальных строк. Для n = 8 это 16,777,216 списков, чтобы найти 92 доски. Для n = 12 это около 8.9 × 10^12 списков. Даже если проверять один список за одну наносекунду, на это уйдёт около 2.5 часа.

Размещайте ферзей построчно, сверху вниз, и проверяйте каждого нового ферзя сразу после размещения. Если он под боем, никакое заполнение строк ниже не исправит это, поэтому сразу пропустите эту клетку. Если клетка безопасна, рекурсивно переходите к следующей строке, а когда этот вызов завершится, уберите ферзя и попробуйте следующий столбец. Вызов, достигший строки n, разместил n безопасных ферзей и засчитывается как одна доска. Это алгоритм с возвратом, и он активно отсекает варианты: при n = 12 он посещает 856,189 частичных досок вместо 8.9 × 10^12 полных.

Вторая часть — быстро проверить клетку. Строки ниже пусты, а в строке нового ферзя нет других ферзей, поэтому атаковать клетку (row, c) могут только три линии: её столбец, диагональ / и диагональ \. У всех клеток одной диагонали / одинаковая величина row + c, от 0 до 2n-2. У всех клеток одной диагонали \ одинаковая величина row - c, от -(n-1) до n-1, поэтому прибавьте n-1, чтобы получить индекс от 0 до 2n-2. Используйте три массива флагов: cols размером n, а также diag и anti размером 2n-1. Клетка безопасна, только если все три флага выключены: три обращения, O(1), тогда как сравнение со всеми уже размещёнными ферзями потребовало бы O(n).

На одной линии может находиться не более одного ферзя, поэтому при размещении ферзя включите три его флага, а при удалении снова выключите их — массивы вернутся в исходное состояние. На доске 4 на 4 ферзь в клетке (0, 0) устанавливает cols[0], diag[0] и anti[3]. Во второй строке клетка в столбце 1 лежит на диагонали anti[3], поэтому её пропускают, не проверяя самого ферзя.

В первой строке есть n столбцов, во второй — не более n-1, и так далее, поэтому поиск ограничен величиной O(n!), а диагонали значительно сокращают количество вариантов. При n = 12 циклы проверяют в общей сложности 10,103,868 клеток. Рекурсия достигает глубины в n вызовов, а массивы содержат около 5n флагов, поэтому пространственная сложность равна O(n).

Поиск с множествами работает быстро, но в каждой строке всё равно проверяет все n столбцов, и большинство из них атакованы. Битовая маска позволяет сразу перейти к свободным клеткам. Пусть бит c целого числа обозначает столбец c строки, которую вы собираетесь заполнить, и будем хранить три маски: cols — уже занятые столбцы, left — клетки этой строки, атакованные по диагонали в одном направлении, а right — атакованные по диагонали в другом направлении.

Тогда свободные клетки задаются одним выражением: free = ~(cols | left | right) & full, где в full установлены младшие n битов. Выражение free & -free выделяет самую младшую свободную клетку, а вычитание её маски позволяет перейти к следующей. Когда вы ставите ферзя на bit и переходите на строку ниже, его столбец остаётся занятым, а каждая диагональная атака смещается на один столбец. Поэтому следующая строка получает cols | bit, ((left | bit) << 1) & full и (right | bit) >> 1. Отменять изменения не нужно: каждый вызов получает собственные три целых числа. Когда cols == full, все n ферзей расставлены.

Возьмём n = 4 и поставим первого ферзя в столбец 1: bit = 0010, считая столбец 0 крайним справа битом. Для строки 1 получаем cols = 0010, left = 0100 и right = 0001, поэтому free = 1000: столбец 3 — единственный возможный вариант, найденный без проверки столбцов 0, 1 или 2.

Поиск посещает те же частичные доски, что и версия с множествами, но теперь на каждом шаге цикла ставится ферзь. Для n = 12 это 856,188 шагов вместо 10,103,868 проверок клеток, причём на каждом шаге выполняется лишь несколько целочисленных операций. Время работы по-прежнему ограничено сверху величиной O(n!), а глубина рекурсии составляет n вызовов. Код на R выполняет те же операции с масками без рекурсии: он хранит в векторе все частичные доски для одной строки и расширяет их все на одну строку за раз, поэтому в памяти хранится целый уровень досок вместо n вызовов.