Пазл о восьми ферзях - Eight queens puzzle

абcdежграммчас
8
Chessboard480.svg
f8 белая королева
d7 белая королева
g6 белая королева
а5 белая королева
h4 белая королева
b3 белая королева
e2 белая королева
c1 белая королева
8
77
66
55
44
33
22
11
абcdежграммчас
Единственное симметричное решение загадки восьми ферзей (вплоть до вращение и отражение)

В пазл восемь королев проблема размещения восьми шахматы королевы на 8 × 8 шахматная доска чтобы никакие две королевы не угрожали друг другу; таким образом, решение требует, чтобы никакие две ферзя не делили одну и ту же строку, столбец или диагональ. Головоломка с восемью ферзями является примером более общего п проблема королев размещения п не атакующие ферзи на п×п шахматная доска, решения которой существуют для всех натуральных чисел п за исключением п = 2 и п = 3.[1]

История

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

С тех пор многие математики, включая Карл Фридрих Гаусс, работали над головоломкой восьми ферзей и ее обобщенной пверсия королевы. В 1874 г. С. Гюнтер предложил метод с использованием детерминанты найти решения.[2] J.W.L. Глейшер усовершенствовал подход Гюнтера.

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

Конструирование и подсчет решений

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

Решения

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

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

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

Решение 10 имеет дополнительное свойство: нет трех ферзей на прямой линии.

Существование решений

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

Приведенные выше примеры могут быть получены с помощью следующих формул.[3] Позволять (я, j) быть квадратом в столбце я и ряд j на п × п шахматная доска k целое число.

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

  1. Если остаток от деления п на 6 не равно 2 или 3, то список состоит из всех четных чисел, за которыми следуют все нечетные числа, не превышающие п.
  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, 1, 3).
  5. Добавьте нечетный список к четному и разместите ферзей в строках, заданных этими числами, слева направо (a2, b4, c6, d8, e3, f1, g7, h5).

За п = 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.

Подсчет решений

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

пфундаментальныйвсе
111
200
300
412
5210
614
7640
81292
946352
1092724
113412,680
121,78714,200
139,23373,712
1445,752365,596
15285,0532,279,184
161,846,95514,772,512
1711,977,93995,815,104
1883,263,591666,090,624
19621,012,7544,968,057,848
204,878,666,80839,029,188,884
2139,333,324,973314,666,222,712
22336,376,244,0422,691,008,701,644
233,029,242,658,21024,233,937,684,440
2428,439,272,956,934227,514,171,973,736
25275,986,683,743,4342,207,893,435,808,352
262,789,712,466,510,28922,317,699,616,364,044
2729,363,495,934,315,694234,907,967,154,122,528

Загадка с шестью ферзями имеет меньше решений, чем загадка с пятью ферзями.

Нет известной формулы для точного числа решений или даже для его асимптотического поведения. Доска 27 × 27 - это доска высшего порядка, которая была полностью пронумерована.[4]

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

  • Высшие измерения
Найдите количество не атакующих ферзей, которые можно разместить в d-мерные шахматы Космос размера п. Больше, чем п ферзей можно разместить в более высоких измерениях (самый маленький пример - четыре не атакующих ферзя в шахматном пространстве 3 × 3 × 3), и фактически известно, что для любого k, есть более высокие измерения, где пk ферзей недостаточно, чтобы атаковать все клетки.[5][6]
  • Использование фигур кроме ферзей
На доске 8х8 можно разместить 32 рыцари, или 14 епископы, 16 короли или восемь грачи, так что никакие две фигуры не атакуют друг друга. Сказочные шахматы также были заменены на королев. В случае с рыцарями простое решение - разместить по одному на каждую клетку данного цвета, поскольку они перемещаются только к противоположному цвету. Решение также легко для ладей и королей. Восемь ладей могут быть размещены по длинной диагонали (среди тысяч других решений), а 16 королей размещаются на доске, разделив ее на 2 на 2 поля и поместив королей в эквивалентные точки на каждом поле.
  • Шахматные вариации
Связанные проблемы могут быть запрошены шахматные вариации Такие как сёги. Например, п+k проблема королей драконов просит разместить k пешки сёги и п+k взаимно не нападающий короли драконов на п×п доска сёги.[7]
В математике матрицу перестановок можно рассматривать геометрически как набор п точки, лежащие на квадратах п×п шахматная доска, так что каждая строка или столбец содержит только одну точку. Таким образом, порядок-п матрица перестановок является решением ппазл с ручьями.
  • Нестандартные доски
Pólya изучил п проблема королев на тороидальный (в форме бублика) и показал, что решение есть на п×п доска тогда и только тогда, когда п не делится на 2 или 3.[8] В 2009 году Пирсон и Пирсон алгоритмически заполнили трехмерные доски (п×п×п) с п2 королев, и предположил, что их кратность может дать решения для четырехмерной версии головоломки.[9][нужен лучший источник ]
  • Господство
Учитывая п×п доска, число господства это минимальное количество ферзей (или других фигур), необходимое для атаки или занятия каждой клетки. За п = 8 число доминирования ферзя равно 5.[10][11]
  • Королевы и другие предметы
Варианты включают смешивание ферзей с другими фигурами; например, размещение м королевы и м рыцари на п×п доска, чтобы ни одна фигура не нападала на другую[12] или размещение ферзей и пешек так, чтобы никакие два ферзя не атаковали друг друга.[13][нужен лучший источник ]
В 1992 году Демирёрс, Рафраф и Таник опубликовали метод преобразования некоторых магических квадратов в прешения королевы, и наоборот.[14]
В п×п матрицу, поместите каждую цифру от 1 до п в п расположений в матрице, чтобы никакие два экземпляра одной и той же цифры не находились в одной строке или столбце.
Рассмотрим матрицу с одним основным столбцом для каждого из п ряды доски, по одному основному столбцу для каждого из п файлов и по одному дополнительному столбцу для каждого из 4п - 6 нетривиальных диагоналей доски. Матрица имеет п2 строки: по одной для каждого возможного размещения ферзя, и каждая строка имеет 1 в столбцах, соответствующих рангу, вертикали и диагоналям этого квадрата, и 0 во всех остальных столбцах. Тогда п Задача ферзей эквивалентна выбору подмножества строк этой матрицы так, чтобы каждый первичный столбец имел 1 ровно в одной из выбранных строк, а каждый вторичный столбец имел 1 не более чем в одной из выбранных строк; это пример обобщенного точное покрытие проблема, из которых судоку другой пример.
  • п-Queens Завершение
Статья 2017 года[15] исследовал проблему "Учитывая п×п шахматная доска, на которой уже размещено несколько ферзей, можно ли разместить ферзя в каждом оставшемся ряду, чтобы никакие два ферзя не атаковали друг друга? »и несколько связанных проблем. НП-полный[16] и # P-complete.

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

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

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

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

мин-конфликты решение 8 ферзей

Альтернативой исчерпывающему перебору является алгоритм «итеративного ремонта», который обычно начинается со всех ферзей на доске, например, с одного ферзя на столбец.[17] Затем он подсчитывает количество конфликтов (атак) и использует эвристику, чтобы определить, как улучшить размещение ферзей. 'минимум конфликтов ' эвристический - перемещение фигуры с наибольшим числом конфликтов на поле в том же столбце, где число конфликтов наименьшее - особенно эффективно: оно находит решение проблемы 1000000 ферзей в среднем менее чем за 50 шагов. Это предполагает, что первоначальная конфигурация «достаточно хороша» - если миллион ферзей начинаются в одном ряду, потребуется не менее 999 999 шагов, чтобы исправить это. «Достаточно хорошую» отправную точку можно найти, например, поместив каждого ферзя в отдельный ряд и столбец так, чтобы он конфликтовал с наименьшим количеством ферзей, уже находящихся на доске.

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

Восемь королев-animation.gif

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

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

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

Ниже приводится Паскаль программа Никлаус Вирт в 1976 г.[20] Он находит одно решение проблемы восьми ферзей.

программа восемь королева1(выход); вар я : целое число; q : логический;    а : множество[ 1 .. 8] из логический;    б : множество[ 2 .. 16] из логический;    c : множество[ −7 .. 7] из логический;    Икс : множество[ 1 .. 8] из целое число; процедура пытаться( я : целое число; вар q : логический);    вар j : целое число;    начинать     j := 0;    повторение         j := j + 1;         q := ложный;        если а[ j] и б[ я + j] и c[ я − j] тогда            начинать             Икс[ я    ] := j;            а[ j    ] := ложный;             б[ я + j] := ложный;             c[ я − j] := ложный;            если я < 8 тогда                начинать                пытаться( я + 1, q);                если нет q тогда                    начинать                     а[ j] := истинный;                     б[ я + j] := истинный;                     c[ я − j] := истинный;                    конец                конец             еще                 q := истинный            конец    до того как q или же (j = 8);    конец; начинатьза я := 1 к  8 делать а[ я] := истинный;за я := 2 к 16 делать б[ я] := истинный;за я := −7 к  7 делать c[ я] := истинный;пытаться( 1, q);если q тогда    за я := 1 к 8 делать записывать( Икс[ я]:4);Writelnконец.

Смотрите также

Рекомендации

  1. ^ Э. Дж. Хоффман и др., "Построение решений задачи m Куинса". Математический журнал, Vol. XX (1969), стр. 66–72. [1]
  2. ^ а б У. В. Роуз Болл (1960) «Проблема восьми королев», в Математические развлечения и эссе, Macmillan, New York, pp. 165–171.
  3. ^ а б c Бо Бернхардссон (1991). «Явные решения проблемы N ферзей для всех N». СИГАРТ Бык. 2 (2): 7. Дои:10.1145/122319.122322.
  4. ^ Проект Q27
  5. ^ Дж. Барр и С. Рао (2006), Проблема n-Куинса в более высоких измерениях, Elemente der Mathematik, том 61 (4), стр. 133–137.
  6. ^ Мартин С. Пирсон. «Королевы на шахматной доске - за гранью второго измерения» (php). Получено 27 января 2020.
  7. ^ Чатем, Дуг (1 декабря 2018 г.). "Размышления о проблеме n + k королей драконов". Журнал развлекательной математики. 5 (10): 39–55. Дои:10.2478 / rmm-2018-0007.
  8. ^ G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, Джордж Полиа: Сборник статей Vol. IV, G-C. Рота, изд., MIT Press, Кембридж, Лондон, 1984, стр. 237–247.
  9. ^ [2]
  10. ^ Burger, A. P .; Cockayne, E.J .; Минхардт, К. (1997), «Доминирование и неизбыточность в графе ферзей», Дискретная математика, 163 (1–3): 47–66, Дои:10.1016 / 0012-365X (95) 00327-S, HDL:1828/2670, МИСТЕР  1428557
  11. ^ Уикли, Уильям Д. (2018), «Королевы мира за двадцать пять лет», Гера, Ралукка; Хейнс, Тереза ​​В.; Хедетниеми, Стивен Т. (ред.), Теория графов: любимые гипотезы и открытые задачи - 2, Сборники задач по математике, Cham: Springer, стр. 43–54, Дои:10.1007/978-3-319-97686-0_5, МИСТЕР  3889146
  12. ^ «Проблема королев и рыцарей». Архивировано из оригинал 16 октября 2005 г.. Получено 20 сентября 2005.
  13. ^ Проблема девяти ферзей
  14. ^ О. Демирёрс, Н. Рафраф, М.М. Таник. Получение решений n ферзей из магических квадратов и построение магических квадратов из решений n ферзей. Журнал развлекательной математики, 24: 272–280, 1992.
  15. ^ Гент, Ян П .; Джефферсон, Кристофер; Соловей, Питер (август 2017 г.). "Сложность п-Queens Завершение ". Журнал исследований искусственного интеллекта. 59: 815–848. Дои:10.1613 / jair.5512. ISSN  1076-9757. Получено 7 сентября 2017.
  16. ^ "Загадка 8 королев". www.claymath.org. Институт математики Клэя. 2 сентября 2017.
  17. ^ Алгоритм полиномиального времени для задачи N-Queen Рок Сосич и Джун Гу, 1990. Описывает время выполнения до 500 000 Queens, что было максимальным значением, которое они могли запустить из-за ограничений памяти.
  18. ^ Цю, Цзунъянь (февраль 2002 г.). «Бит-векторное кодирование задачи n-queen». Уведомления ACM SIGPLAN. 37 (2): 68–70. Дои:10.1145/568600.568613.
  19. ^ Ричардс, Мартин (1997). Алгоритмы обратного отслеживания в MCPL с использованием битовых шаблонов и рекурсии (PDF) (Технический отчет). Компьютерная лаборатория Кембриджского университета. UCAM-CL-TR-433.
  20. ^ Вирт, 1976, стр. 145

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

внешняя ссылка