Задача о восьми ферзях: решение и алгоритм

Задача о восьми ферзях просит расставить восемь одинаковых ферзей на обычной шахматной доске так, чтобы никакие два не били друг друга. Ферзь ходит по строке, столбцу и любой диагонали; препятствий между фигурами в этой задаче нет. Найти одну подходящую расстановку можно вручную, а подсчёт всех вариантов удобно поручить алгоритму. В калькуляторе выберите размер доски: он переберёт допустимые положения и покажет первое решение и общее число расстановок.
Как устроено условие
Пронумеруем строки сверху вниз от 1 до 8, а столбцы слева направо тоже от 1 до 8. В каждой строке обязательно будет ровно один ферзь: двух в одну строку ставить нельзя, а строк и фигур поровну. По той же причине каждый столбец тоже займёт ровно один ферзь. Эти два наблюдения не решают задачу целиком: остаётся запрет на совпадение диагоналей.
Для клеток с координатами и ферзи атакуют друг друга по диагонали ровно тогда, когда . Например, клетки и отстоят на две строки и два столбца: между ними диагональ. Напротив, для клеток и разности равны двум и трём, поэтому диагонального конфликта нет.

На схеме показан один ферзь в клетке . Он контролирует семь других клеток своей строки, семь клеток столбца и тринадцать клеток на диагоналях: всего 27. Эти направления вне занятой клетки не пересекаются, поэтому их количества можно сложить по правилу суммы. На краю доски число диагональных клеток будет другим.
Готовая расстановка и её проверка
Одно решение удобно записать списком столбцов, по одному для каждой строки:
Это означает: ферзь первой строки стоит в первом столбце, второй строки - в пятом, и так далее. Столбцы в списке не повторяются, строки различны по способу записи. Например, ферзи первой и третьей строк стоят в столбцах 1 и 8: разница строк равна двум, а столбцов семи. Они не атакуют друг друга.
Проверять все пары по отдельности необязательно. Две клетки лежат на одной диагонали одного направления, если у них одинаковая разность ; для другого направления признак - одинаковая сумма . Для приведённой расстановки разности по строкам равны , а суммы - . В каждом списке все значения различны, значит, ни одна пара не делит диагональ. Вместе с проверкой столбцов этого достаточно для доказательства, что расстановка годится.
Почему полный перебор можно сократить
Если выбирать произвольные восемь занятых клеток из 64, придётся рассматривать множество положений, заведомо нарушающих условие по строкам и столбцам. После требования «по одному ферзю в каждой строке и столбце» положение задаётся перестановкой восьми столбцов. Таких кандидатов . Связь факториала с выбором порядка разобрана в статье про сочетания и перестановки.
Однако даже среди перестановок много диагональных конфликтов. Идея перебора с возвратом состоит в том, чтобы замечать их раньше: если первые несколько ферзей уже бьют друг друга, расставлять остальных бессмысленно. Мы не проверяем целиком каждое заведомо испорченное продолжение, а отсекаем всю соответствующую ветвь поиска.
Важно различать два числа. - число кандидатов при соблюдении строк и столбцов; это ещё не число ответов. Число допустимых полных расстановок существенно меньше. Сокращение пространства поиска не меняет условие задачи и не теряет правильные варианты: ветвь отбрасывается только после обнаружения реального конфликта.
Перебор с возвратом на маленькой доске
Начнём с первой строки и будем пробовать столбцы слева направо. Допустив очередного ферзя, переходим к следующей строке. Если в ней нет подходящей клетки, снимаем последнего поставленного ферзя и продолжаем поиск в его строке со следующего столбца. Такой возврат повторяется столько раз, сколько потребуется.
Например, на доске сначала поставим ферзей в столбцы 1 и 3 первых двух строк. В третьей строке столбец 1 занят по вертикали, столбец 3 тоже; столбцы 2 и 4 бьёт ферзь второй строки. Подходящей клетки нет. Снимаем второго ферзя и пробуем столбец 4: теперь в третьей строке доступен столбец 2. Но для четвёртой строки опять нет места, поэтому нужно вернуться и продолжить перебор. В конце концов находится решение .
Порядок проб влияет на то, какое решение будет показано первым, но при полном переборе не влияет на итоговое количество. Структура поиска напоминает обход в глубину: мы углубляемся по одной ветви, а затем возвращаемся к предыдущему выбору. Здесь вершины дерева - частичные расстановки, а не клетки исходной доски.
Алгоритм и проверка ограничений
На шаге храним уже выбранные столбцы предыдущих строк. Для каждого столбца новой строки проверяем, что он не использован и что ни для одной прежней строки не выполняется . Если обе проверки пройдены, добавляем и рекурсивно обрабатываем следующую строку. После возврата удаляем этот выбор и рассматриваем следующий столбец.
Когда расставлены все фигур, найдено одно решение. Если нужен только пример, на этом можно остановиться; если нужно количество, счётчик увеличивается на единицу, а поиск продолжается. Так работает калькулятор выше: при каждом изменении размера он заново просматривает дерево и показывает первую найденную расстановку. Для размеров от четырёх до восьми число решений соответственно равно 2, 10, 4, 40 и 92.
Для ускорения проверок удобно хранить три множества занятых значений: столбцов , разностей и сумм . Проверка кандидата тогда состоит из трёх обращений к множествам; при постановке значения добавляют, при возврате удаляют. Важно удалять именно значения снимаемой фигуры, иначе они ошибочно заблокируют соседнюю ветвь. Рекурсивный стек и эти множества занимают памяти, если не сохранять список всех решений.
Сколько решений и при чём здесь симметрия
Для обычной доски существует 92 расстановки, если повороты и отражения считать разными положениями на фиксированной доске. Если же отождествить расстановки, получающиеся друг из друга поворотами и зеркальными отражениями квадрата, остаётся 12 фундаментальных решений. Полный список расстановок и их разбиение на классы приведены в каталоге решений.
Наивно разделить 92 на восемь нельзя. У квадрата действительно есть восемь преобразований симметрии, включая тождественное, но разные преобразования иногда дают одну и ту же расстановку. Один из двенадцати классов содержит четыре различных положения, поскольку его рисунок совпадает с собой после поворота на 180 градусов. Остальные одиннадцать классов содержат по восемь: .
Обобщение и сложность
В задаче о ферзях требуется разместить фигур на доске . При решение одно, а при и решений нет. Дальнейшие значения не обязаны расти монотонно: для пяти фигур расстановок десять, для шести - четыре. Последовательность результатов полного подсчёта опубликована в OEIS.
Для поиска допустимых перестановок существует не более полных кандидатов; отсечение обычно уменьшает число посещённых ветвей, но не превращает задачу автоматически в полиномиальную. В представленном варианте на каждом узле цикл проверяет все столбцов. Если проверять занятость множествами за постоянное время, грубая верхняя оценка времени равна : число узлов дерева частичных перестановок не превосходит постоянного множителя от . При последовательном сравнении нового ферзя со всеми предыдущими, как в калькуляторе, дополнительный множитель даёт оценку . Сохранение всех решений требует дополнительной памяти, зависящей от их количества.
Есть и другая модель: считать клетки вершинами графа, а атакующие пары соединять рёбрами. Тогда ответ - независимое множество из вершин; соответствующее понятие объясняется в статье о независимых множествах. Такая формулировка полезна для вариантов с запрещёнными клетками или нестандартной доской, где готовые симметрии могут исчезнуть.
Частые ошибки
- Проверять только строки и столбцы. Перестановка столбцов может содержать диагональные конфликты; проверяйте обе диагонали.
- Считать возврат ошибкой алгоритма. Это штатный шаг: он удаляет выбор, у которого не нашлось продолжения.
- Путать 92 и 12. Первое число считает положения на фиксированной доске, второе - классы с точностью до симметрий.
- Останавливаться после первого ответа при подсчёте всех. Продолжайте поиск после полного размещения и возвращайтесь к предыдущим решениям.
FAQ
Можно ли поставить больше восьми ферзей без взаимных атак?
Нет: при девяти фигурах хотя бы две окажутся в одной из восьми строк. Восемь достижимы, что доказывает приведённая расстановка.
Обязательно ли уметь играть в шахматы?
Нет. Достаточно знать направления хода ферзя; здесь не рассматриваются шах, очередность ходов или остальные фигуры.
Почему не все классы симметрии содержат восемь расстановок?
Некоторые положения сохраняются при нетривиальном преобразовании квадрата. Такие преобразования не создают новых элементов класса, поэтому его размер может быть меньше восьми.
Коротко
Задача о восьми ферзях сводится к выбору по одной клетки в каждой строке и столбце без совпадающих диагоналей. Перебор с возвратом отсеивает конфликтующие частичные расстановки и возвращается из тупиков. На фиксированной доске существует 92 решения, а с учётом поворотов и отражений - 12 классов.
Читайте также

Числа Белла: разбиения множества и формула
Числа Белла считают разбиения множества на непустые группы. Разбираем подробные примеры, рекуррентную формулу, связь с числами Стирлинга и алгоритм вычисления.

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

Алгоритм Хопкрофта-Карпа: паросочетание по фазам
Алгоритм Хопкрофта-Карпа находит максимальное паросочетание в двудольном графе. Разбираем поиск кратчайших цепей, BFS и DFS, пример двух фаз и оценку сложности.

Число булевых функций от n переменных: формула
Сколько существует булевых функций от n переменных и почему ответ равен 2 в степени 2ⁿ? Вывод по таблице истинности, примеры и задачи с ограничениями.

Дерево Фенвика: суммы и обновления по шагам
Дерево Фенвика хранит суммы блоков массива и помогает быстро отвечать на запросы и менять элементы. Разбираем lowbit, пример вычислений, реализацию на Python и сложность операций.

Диаграммы Эйлера-Венна: решение задач
Диаграммы Эйлера-Венна для решения задач: как заполнить области двух и трёх множеств, найти число объектов вне кругов и проверить непротиворечивость данных.