Задача о восьми ферзях

Задача о восьми ферзях — классическая комбинаторная задача, заключающаяся в расстановке восьми ферзей на шахматной доске размером 8×8 таким образом, чтобы ни один из них не атаковал другого. Ферзь, как самая сильная фигура в шахматах, может ходить по горизонталям, вертикалям и диагоналям на любое количество клеток. Поэтому условие задачи сводится к тому, чтобы никакие два ферзя не находились на одной горизонтали, одной вертикали и одной диагонали. Задача является частным случаем более общей проблемы о расстановке N ферзей на доске N×N. Она служит классическим примером для изучения алгоритмов перебора с возвратом (backtracking) и часто используется в учебных курсах по программированию и теории алгоритмов.

История

Впервые задача была сформулирована в 1848 году немецким шахматистом Максом Беззелем. В 1850 году её решение опубликовал Франц Наук, который нашёл 40 из 92 существующих решений. Позднее, в 1850-х годах, полное число решений (92) было установлено английским математиком Джеймсом Глэйшером. Задача привлекла внимание многих математиков, включая Карла Фридриха Гаусса, который, по некоторым данным, самостоятельно нашёл 72 решения.

В XX веке, с развитием вычислительной техники, задача о восьми ферзях стала популярным тестом для алгоритмов и программ. В 1960-х годах она использовалась для демонстрации возможностей первых компьютеров, а в 1970-х — для обучения методам искусственного интеллекта. В 1990-х годах задача была решена с помощью генетических алгоритмов и нейронных сетей.

Формулировка и условия

Задача формулируется следующим образом: на стандартной шахматной доске 8×8 необходимо разместить 8 ферзей так, чтобы ни один из них не находился под боем другого. Формальные условия:

• Никакие два ферзя не могут находиться на одной горизонтали (строке).
• Никакие два ферзя не могут находиться на одной вертикали (столбце).
• Никакие два ферзя не могут находиться на одной диагонали (как главной, так и побочной).

Таким образом, каждое решение представляет собой перестановку чисел от 1 до 8, где номер строки соответствует номеру столбца, а значение — номеру горизонтали, на которой стоит ферзь. Дополнительно требуется, чтобы разность номеров строк и столбцов для любых двух ферзей была различна (условие диагоналей).

Решения

Количество решений

Задача имеет ровно 92 различных решения. Если учитывать симметрию (повороты и отражения доски), то число фундаментально различных решений сокращается до 12. Фундаментальные решения — это такие, которые не могут быть получены друг из друга путём поворота доски на 90°, 180° или 270° или отражения относительно вертикальной, горизонтальной или диагональной оси.

Примеры решений

Одно из классических решений (в координатах (столбец, строка)): (1, 5), (2, 3), (3, 1), (4, 7), (5, 2), (6, 8), (7, 6), (8, 4). В шахматной нотации это соответствует расстановке: ферзи на a5, b3, c1, d7, e2, f8, g6, h4.

Другое известное решение: (1, 1), (2, 5), (3, 8), (4, 6), (5, 3), (6, 7), (7, 2), (8, 4).

Симметрия

Из 92 решений 11 являются симметричными относительно центра доски (то есть при повороте на 180° они переходят сами в себя). Остальные 81 решение образуют пары, связанные симметрией. Фундаментальные решения (12) — это те, которые не могут быть получены друг из друга симметричными преобразованиями.

Алгоритмы решения

Перебор с возвратом (Backtracking)

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

Псевдокод алгоритма (рекурсивная функция solve(col)):

`` function solve(col): if col == 8: // найдено решение print(board) return for row in 0..7: if is_safe(board, col, row): place_queen(board, col, row) solve(col + 1) remove_queen(board, col, row) ``

Функция is_safe проверяет, не атакован ли ферзь в позиции (col, row) уже установленными ферзями. Для этого достаточно проверить, что в той же строке и на тех же диагоналях нет других ферзей.

Оптимизации

Для ускорения перебора используются дополнительные структуры данных: массивы занятых строк и диагоналей. Например, можно хранить три булевых массива: rows[8] (занятые строки), diag1[15] (главные диагонали, индекс = col + row) и diag2[15] (побочные диагонали, индекс = col - row + 7). Это позволяет проверять безопасность за O(1).

Другие алгоритмы

• Генетические алгоритмы: популяция решений эволюционирует через скрещивание и мутацию. Используется для нахождения одного решения, но не гарантирует нахождения всех.
• Метод Монте-Карло: случайная расстановка с последующей проверкой. Эффективен только для малых N.
• Алгоритм с использованием перестановок: генерируются все перестановки чисел от 1 до 8 (8! = 40320), и для каждой проверяется условие диагоналей. Это даёт все решения, но менее эффективно, чем backtracking.

Обобщение: задача о N ферзях

Задача о восьми ферзях является частным случаем задачи о N ферзях на доске N×N. Для N = 1 существует 1 решение, для N = 2 и N = 3 решений нет. Для N = 4 — 2 решения, для N = 5 — 10, для N = 6 — 4, для N = 7 — 40, для N = 8 — 92. Далее количество решений быстро растёт: для N = 9 — 352, для N = 10 — 724, для N = 11 — 2680, для N = 12 — 14200, для N = 13 — 73712, для N = 14 — 365596, для N = 15 — 2279184, для N = 16 — 14772512, для N = 17 — 95815104, для N = 18 — 666090624, для N = 19 — 4968057848, для N = 20 — 39029188884.

Точная формула для числа решений не найдена, но существуют асимптотические оценки. Для больших N задача становится вычислительно сложной: полный перебор требует O(N!) операций, что делает его непрактичным для N > 20. Однако существуют эвристические алгоритмы, позволяющие найти одно решение за полиномиальное время, например, алгоритм на основе «танцующих ссылок» (Dancing Links) или метод с использованием «ладейных» перестановок.

Применение

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

• Программирование: как классический пример рекурсии и алгоритмов с возвратом.
• Теория алгоритмов: для демонстрации методов перебора, оптимизации и анализа сложности.
• Искусственный интеллект: как тестовая задача для поисковых алгоритмов, генетических алгоритмов и нейронных сетей.
• Комбинаторика: для изучения перестановок и симметрий.

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

Интересные факты

• В 1874 году немецкий математик Эрнст Шрёдер доказал, что число решений задачи о восьми ферзях равно 92.
• В 1960-х годах задача была решена на компьютере IBM 7090 за несколько минут.
• Существует вариант задачи, в котором требуется расставить ферзей так, чтобы они занимали все клетки доски (так называемая «задача о доминировании ферзей»), но это другая задача.
• В 1992 году была опубликована статья, в которой утверждалось, что задача о N ферзях является NP-полной, однако это не было строго доказано.
• В 2017 году с помощью распределённых вычислений было найдено решение для N = 27 (доска 27×27), что потребовало около 10^18 операций.

Источники

• Bell, J. (2007). The Eight Queens Problem. Mathematics Magazine, 80(3), 187–197.
• Knuth, D. E. (2000). Dancing Links. In Millennial Perspectives in Computer Science, 187–214.
• N. J. A. Sloane. Sequence A000170: Number of ways to place n non-attacking queens on an n X n board. OEIS.
• Watkins, J. J. (2004). Across the Board: The Mathematics of Chess Problems. Princeton University Press.
• Гарднер, М. (1975). Математические головоломки и развлечения. Мир.