Загадка «Восемь королев»

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Единственное симметричное решение головоломки о восьми ферзях ( с точностью до вращения и отражения )

Загадка восьми ферзей — это задача разместить восемь шахматных ферзей 8×8 на шахматной доске так, чтобы никакие два ферзя не угрожали друг другу; таким образом, решение требует, чтобы никакие два ферзя не находились в одной и той же строке, столбце или диагонали. Имеется 92 решения. Впервые эта проблема была поставлена ​​в середине 19 века. В современную эпоху ее часто используют в качестве примера задачи для различных методов компьютерного программирования .

Загадка с восемью ферзями — это частный случай более общей задачи о n ферзях , состоящей в размещении n неатакующих ферзей на шахматной доске размера n × n . Решения существуют для всех натуральных чисел n, за исключением n = 2 и n = 3. Хотя точное количество решений известно только для n ≤ 27, асимптотическая скорость роста числа решений составляет примерно (0,143 n ). ^н .

История

Шахматный композитор Макс Беззель опубликовал головоломку с восемью ферзями в 1848 году. Франц Наук опубликовал первые решения в 1850 году. Наук также расширил головоломку до задачи о n ферзях, где n ферзей находятся на шахматной доске из n × n клеток.

С тех пор многие математики , в том числе Карл Фридрих Гаусс , работали как над головоломкой о восьми ферзях, так и над ее обобщенной с n версией -ферзями. В 1874 г. С. Гюнтер предложил метод с помощью определителей . поиска решений Дж. У. Л. Глейшер усовершенствовал подход Гюнтера.

В 1972 году Эдсгер Дейкстра использовал эту проблему, чтобы проиллюстрировать силу того, что он назвал структурным программированием . Он опубликовал весьма подробное описание в глубину алгоритма поиска .

Построение и подсчет решений при n = 8

Проблема поиска всех решений проблемы 8 ферзей может быть весьма дорогостоящей в вычислительном отношении, поскольку существует 4 426 165 368 возможных расстановок восьми ферзей на доске 8 × 8. но всего 92 решения. Можно использовать ярлыки, которые уменьшают вычислительные требования, или практические правила, позволяющие избежать применения методов грубой силы . Например, применив простое правило, выбирающее по одному ферзю из каждого столбца, можно сократить число возможностей до 16 777 216 (т. е. 8 ⁸ ) возможные комбинации. Генерация перестановок еще больше снижает возможности до 40 320 (то есть до 8! ), которые затем можно проверить на наличие диагональных атак.

Головоломка о восьми королевах имеет 92 различных решения. Если решения, отличающиеся только симметричностью операций вращения и отражения доски, считать за одно, то головоломка имеет 12 решений. Это так называемые фундаментальные решения; представители каждого показаны ниже.

Фундаментальное решение обычно имеет восемь вариантов (включая его первоначальную форму), полученных поворотом на 90, 180 или 270° и последующим отражением каждого из четырех вариантов вращения в зеркале в фиксированном положении. Однако одно из 12 фундаментальных решений (решение 12 ниже) идентично собственному повороту на 180°, поэтому имеет только четыре варианта (само себя и его отражение, его поворот на 90° и его отражение). Таким образом, общее количество различных решений равно 11×8 + 1×4 = 92.

Все принципиальные решения представлены ниже:

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 1

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 2

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 3

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 4

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 5

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 6

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 7

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 8

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 9

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 10

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 11

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Решение 12

Решение 10 обладает тем дополнительным свойством, что никакие три ферзя не лежат на прямой линии .

Наличие решений

Алгоритмы грубого перебора для подсчета количества решений вычислительно выполнимы для n = 8 , но будут трудноразрешимы для задач с n ≥ 20 , поскольку 20! = 2,433 × 10 ¹⁸ . Если цель состоит в том, чтобы найти единственное решение, можно показать, что решения существуют для всех n ≥ 4, без какого-либо поиска. Эти решения демонстрируют ступенчатую структуру, как в следующих примерах для n = 8, 9 и 10:

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Лестничное решение для 8 двуспальных мест

	а	б	с	д	и	ж	г	час	я
9										9
8										8
7										7
6										6
5										5
4										4
3										3
2										2
1										1
	а	б	с	д	и	ж	г	час	я

Лестничное решение для 9 двуспальных мест

	а	б	с	д	и	ж	г	час	я	дж
10											10
9											9
8											8
7											7
6											6
5											5
4											4
3											3
2											2
1											1
	а	б	с	д	и	ж	г	час	я	дж

Лестничное решение для 10 двуспальных мест

Приведенные выше примеры можно получить с помощью следующих формул. Пусть ( i , j ) будет квадратом в столбце i и строке j на шахматной доске размера n × n , k — целое число.

Один подход является

1. Если остаток от деления n на 6 не равен 2 или 3, то список представляет собой просто все четные числа, за которыми следуют все нечетные числа, не превышающие n .
2. В противном случае напишите отдельные списки четных и нечетных чисел (2, 4, 6, 8 – 1, 3, 5, 7).
3. Если остаток равен 2, поменяйте местами 1 и 3 в нечетном списке и переместите 5 в конец ( 3, 1 , 7, 5 ).
4. Если остаток равен 3, переместите 2 в конец четного списка и 1,3 в конец нечетного списка (4, 6, 8, 2 – 5, 7, 9, 1, 3 ).
5. Добавьте нечетный список к четному списку и поместите ферзей в строки, заданные этими числами, слева направо (a2, b4, c6, d8, e3, f1, g7, h5).

Для n = 8 это приводит к фундаментальному решению 1, приведенному выше. Далее следует еще несколько примеров.

• 14 ферзей (осталось 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
• 15 ферзей (осталось 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15, 1, 3.
• 20 ферзей (осталось 2): 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 3, 1, 7, 9, 11, 13, 15, 17, 19, 5.

Счетные решения для других размеров n

Точное перечисление

Не существует известной формулы для точного количества решений для размещения n ферзей на доске размера n × n, то есть количества независимых наборов размера n в n × n графе ферзей размера . Доска 27×27 — это доска высшего порядка, которая была полностью пронумерована. В следующих таблицах указано количество решений проблемы n ферзей, как фундаментальных (последовательность A002562 в OEIS ), так и всех (последовательность A000170 в OEIS ), для всех известных случаев.

н	фундаментальный	все
1	1	1
2	0	0
3	0	0
4	1	2
5	2	10
6	1	4
7	6	40
8	12	92
9	46	352
10	92	724
11	341	2,680
12	1,787	14,200
13	9,233	73,712
14	45,752	365,596
15	285,053	2,279,184
16	1,846,955	14,772,512
17	11,977,939	95,815,104
18	83,263,591	666,090,624
19	621,012,754	4,968,057,848
20	4,878,666,808	39,029,188,884
21	39,333,324,973	314,666,222,712
22	336,376,244,042	2,691,008,701,644
23	3,029,242,658,210	24,233,937,684,440
24	28,439,272,956,934	227,514,171,973,736
25	275,986,683,743,434	2,207,893,435,808,352
26	2,789,712,466,510,289	22,317,699,616,364,044
27	29,363,495,934,315,694	234,907,967,154,122,528

Известно количество расстановок, в которых, кроме того, ни на одной прямой линии нет трех ферзей. $n\leq 25$ (последовательность A365437 в OEIS ).

Асимптотическое перечисление

В 2021 году Майкл Симкин доказал, что для больших чисел n количество решений проблемы n ферзей примерно равно $(0.143n)^{n}$. Точнее, число ${\mathcal {Q}}(n)$ решений имеет асимптотический рост $${\mathcal {Q}}(n)=((1\pm o(1))ne^{-\alpha })^{n}$$ где $\alpha$ — константа, лежащая между 1,939 и 1,945. (Здесь o (1) представляет собой небольшое обозначение o .)

Если вместо этого рассмотреть тороидальную шахматную доску (где диагонали «огибают» от верхнего края к нижнему и от левого края к правому), на ней можно разместить только n ферзей. $n\times n$ доска, если $n\equiv 1,5\mod 6.$ В этом случае асимптотическое число решений равно $$T(n)=((1+o(1))ne^{-3})^{n}.$$

Связанные проблемы

Высшие измерения

Найдите количество неатакующих ферзей, которые можно разместить в d -мерном шахматном пространстве размера n . Более n ферзей можно разместить в некоторых более высоких измерениях (наименьший пример — четыре неатакующих ферзя в шахматном пространстве 3×3×3), и фактически известно, что для любого k существуют более высокие измерения, где n ^к ферзей недостаточно, чтобы атаковать все поля.

Использование фигур, кроме ферзей

На доске 8х8 можно разместить 32 коня или 14 слонов , 16 королей или восемь ладей так, чтобы никакие две фигуры не атаковали друг друга. В случае с конями простое решение — поставить по одному на каждую клетку заданного цвета, поскольку они ходят только на противоположный цвет. Решение также легко для ладей и королей. На доске можно разместить шестнадцать королей, разделив ее на клетки 2х2 и разместив королей в одинаковых точках на каждой клетке. Размещение n ладей на доске размера n × n находится в прямом соответствии с порядка n матрицами перестановок .

Шахматные вариации

Похожие задачи можно задать и для шахматных вариаций, таких как сёги . Например, задача n + k королей драконов требует разместить k пешек сёги и n + k взаимно не атакующих королей драконов на доске сёги n × n .

Нестандартные платы

Полиа изучил задачу о n ферзях на тороидальной («пончиковой») доске и показал, что решение существует на доске n × n тогда и только тогда, когда n не делится на 2 или 3.

Доминирование

Для n × n доски размера число доминирования — это минимальное количество ферзей (или других фигур), необходимое для атаки или занятия каждой клетки. Для n = 8 число доминирования ферзя равно 5.

Королевы и другие фигуры

Варианты включают смешивание ферзей с другими фигурами; например, разместив m ферзей и m коней на доске n × n так, чтобы ни одна фигура не атаковала другую. или расставить ферзей и пешки так, чтобы два ферзя не атаковали друг друга.

Магические квадраты

В 1992 году Демирёрс, Рафраф и Таник опубликовали метод преобразования некоторых магических квадратов в решения с n -ферзями и наоборот.

Латинские квадраты

В матрице размера n × n поместите каждую цифру от 1 до n в n местах матрицы так, чтобы никакие два экземпляра одной и той же цифры не находились в одной строке или столбце.

Точное покрытие

Рассмотрим матрицу с одним главным столбцом для каждого из n рангов доски, одним основным столбцом для каждого из n файлов и одним второстепенным столбцом для каждой из 4 n − 6 нетривиальных диагоналей доски. Матрица имеет n ² ряды: по одному для каждого возможного размещения ферзя, и каждая строка имеет 1 в столбцах, соответствующих рангу, вертикали и диагоналям этого поля, и 0 во всех остальных столбцах. Тогда проблема n ферзей эквивалентна выбору подмножества строк этой матрицы так, чтобы в каждом основном столбце была 1 ровно в одной из выбранных строк, а в каждом вторичном столбце была 1 не более чем в одной из выбранных строк; это пример обобщенной задачи точного покрытия , еще одним примером которой является судоку .

n -ферзей завершение

Задача завершения состоит в том, можно ли на шахматной доске размера n × n , на которой уже размещено несколько ферзей, разместить ферзя в каждом оставшемся ряду так, чтобы никакие два ферзя не атаковали друг друга. Этот и связанные с ним вопросы являются NP-полными и #P-полными . Любое размещение максимум n /60 ферзей может быть завершено, однако существуют частичные конфигурации примерно из n /4 ферзей, которые невозможно завершить.

Упражнение по разработке алгоритма

Поиск всех решений головоломки с восемью ферзями — хороший пример простой, но нетривиальной задачи. По этой причине его часто используют в качестве примера задачи для различных методов программирования, включая нетрадиционные подходы, такие как программирование в ограничениях , логическое программирование или генетические алгоритмы . Чаще всего он используется как пример проблемы, которую можно решить с помощью рекурсивного алгоритма , индуктивно сформулировав проблему n ферзей в терминах добавления одного ферзя к любому решению проблемы размещения n -1 ферзей на n × n шахматная доска. Индукция . завершается решением «проблемы» размещения 0 ферзей на шахматной доске, которая является пустой шахматной доской

Этот метод можно использовать гораздо эффективнее, чем наивный алгоритм поиска методом перебора , который учитывает все 64 ⁸  = 2 ⁴⁸ = 281 474 976 710 656 возможных слепых размещений восьми ферзей, а затем фильтрует их, чтобы удалить все размещения, при которых два ферзя размещаются либо на одном поле (оставляя только 64!/56! = 178 462 987 637 760 возможных размещений), либо во взаимно атакующих позициях. Этот очень плохой алгоритм, среди прочего, будет выдавать одни и те же результаты снова и снова во всех различных перестановках назначений восьми ферзей, а также повторять одни и те же вычисления снова и снова для разных подмножеств каждого решение. Усовершенствованный алгоритм грубой силы помещает по одному ферзя в каждую строку, в результате чего получается всего 8 ⁸  = 2 ²⁴ = 16 777 216 слепых размещений.

Можно сделать гораздо лучше, чем это. Один алгоритм решает головоломку с восемью ладьями , генерируя перестановки чисел от 1 до 8 (которых 8! = 40 320), и использует элементы каждой перестановки в качестве индексов для размещения ферзя в каждой строке. Затем он отклоняет доски с диагональными атакующими позициями.

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

Программа с обратным поиском поиска в глубину , представляющая собой небольшое усовершенствование метода перестановок, строит дерево поиска , рассматривая одну строку доски за раз, исключая большинство позиций доски, не имеющих решения, на очень ранней стадии их построения. Поскольку он отвергает ладейные и диагональные атаки даже на неполных досках, он исследует только 15 720 возможных расстановок ферзей. Дальнейшее улучшение, в котором рассматриваются только 5508 возможных ферзей. размещения, заключается в объединении метода, основанного на перестановке, с ранним метод обрезки: перестановки генерируются в глубину, и пространство поиска сокращается, если частичная перестановка дает диагональная атака. Программирование с ограничениями также может быть очень эффективным в решении этой проблемы.

мин-конфликтов для 8 ферзей Решение

Альтернативой исчерпывающему перебору является алгоритм «итеративного восстановления», который обычно начинается со всех ферзей на доске, например, с одного ферзя на столбец. Затем он подсчитывает количество конфликтов (атак) и использует эвристику, чтобы определить, как улучшить расположение ферзей. « минимальных конфликтов » Эвристика – перемещение фигуры с наибольшим количеством конфликтов на поле в том же столбце, где количество конфликтов наименьшее – особенно эффективна: она легко находит решение даже проблемы 1 000 000 ферзей.

В отличие от описанного выше поиска с возвратом, итеративный ремонт не гарантирует решения: как и все жадные процедуры, он может застрять на локальном оптимуме. (В таком случае алгоритм может быть перезапущен с другой начальной конфигурацией.) С другой стороны, он может решать проблемы размеров, которые на несколько порядков выходят за рамки поиска в глубину.

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

Пример программы

Следующая программа представляет собой перевод решения Никлауса Вирта на язык программирования Python , но в ней отсутствует индексная арифметика , присутствующая в оригинале, а вместо этого используются списки , чтобы сделать программный код максимально простым. Используя сопрограмму в виде функции-генератора , обе версии оригинала могут быть унифицированы для вычисления одного или всех решений. Рассматривается только 15 720 возможных расстановок ферзей.

def queens(n: int, i: int, a: list, b: list, c: list):
    if i < n:
        for j in range(n):
            if j not in a and i + j not in b and i - j not in c:
                yield from queens(n, i + 1, a + [j], b + [i + j], c + [i - j])
    else:
        yield a


for solution in queens(8, 0, [], [], []):
    print(solution)

В популярной культуре

• В игре The 7th Guest , the 8th Puzzle: «The Queen's Dilemma» в игровой комнате особняка Штауф находится де-факто головоломка с восемью королевами.
• В игре «Профессор Лейтон и любопытная деревня » 130-я головоломка: «Слишком много королев 5» представляет собой головоломку на восемь королев.

См. также

• Математическая игра
• Математическая головоломка
• Нет проблемы с тремя рядами
• Полином Ладьи
• Массив Костаса

Дальнейшее чтение

• Белл, Джордан; Стивенс, Бретт (2009). «Обзор известных результатов и областей исследования n -ферзей» . Дискретная математика . 309 (1): 1–31. дои : 10.1016/j.disc.2007.12.043 .
• Уоткинс, Джон Дж. (2004). Через доску: Математика шахматных задач . Принстон: Издательство Принстонского университета. ISBN  978-0-691-11503-0 .
• Эллисон, Л.; Да, CN; Макгоги, М. (1988). «Трехмерные задачи NxN-ферзей» . Кафедра компьютерных наук, Университет Монаша, Австралия.
• Нудельман, С. (1995). «Модульная проблема N-ферзей в более высоких измерениях» . Дискретная математика . 146 (1–3): 159–167. дои : 10.1016/0012-365X(94)00161-5 .
• Энгельхардт, М. (август 2010 г.). «Родословная диаграммы решений проблемы 8 ферзей» : . 68–71
• О модульной проблеме N-ферзя в более высоких измерениях , Рикардо Гомес, Хуан Хосе Монтеллано и Рикардо Штраус (2004), Институт математики, Область научных исследований, Внешний вид цепи, Университетский городок, Мексика.
• Бадд, Тимоти (2002). «Пример из практики: загадка восьми королев» (PDF) . Введение в объектно-ориентированное программирование (3-е изд.). Эддисон Уэсли Лонгман. стр. 125–145. ISBN  0-201-76031-2 .
• Вирт, Никлаус (2004 г.) [обновлено в 2012 г.]. «Проблема восьми ферзей». Алгоритмы и структуры данных (PDF) . Версия Оберона с исправлениями и авторизованными модификациями. стр. 114–118.

Внешние ссылки

• Вайсштейн, Эрик В. «Проблема Квинса» . Математический мир .
• queens-cpm на GitHub Головоломка восьми королев в Turbo Pascal для CP/M
• восемь-queens.py на GitHub Однострочное решение головоломки «Восемь королев» на Python
• Решения на более чем 100 различных языках программирования (на Rosetta Code )