Головоломка «Восемь королев»

	а	б	с	г	е	ф	г	час
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 году. ^[1] Наук также расширил задачу до задачи о n ферзях, с n ферзями на шахматной доске размером n × n клеток.

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

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

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

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

Фундаментальное решение обычно имеет восемь вариантов (включая его исходную форму), полученных путем поворота на 90, 180 или 270° и последующего отражения каждого из четырех вариантов вращения в зеркале в фиксированном положении. Однако одно из 12 фундаментальных решений (решение 12 ниже) идентично своему собственному повороту на 180°, поэтому имеет только четыре варианта (само решение и его отражение, его поворот на 90° и его отражение). ^[b] Таким образом, общее число различных решений равно 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 без какого-либо поиска. ^{[3] [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 королев

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

Один из подходов ^[3] заключается в следующем:

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 . Доска 27×27 является доской наивысшего порядка, которая была полностью пронумерована. ^[5] В следующих таблицах указано число решений задачи n ферзей, как фундаментальных (последовательность A002562 в OEIS ), так и всех (последовательность A000170 в OEIS ), для всех известных случаев.

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

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

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

Более высокие измерения

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

Использование фигур, отличных от ферзей

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

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

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

Нестандартные доски

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

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

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

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

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

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

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

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

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

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

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

n- королев завершение

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

Этот раздел, возможно, содержит оригинальные исследования . Пожалуйста, улучшите его, проверив сделанные заявления и добавив встроенные цитаты . Заявления, состоящие только из оригинальных исследований, должны быть удалены. ( Декабрь 2024 ) ( Узнайте, как и когда удалять это сообщение )

Поиск всех решений головоломки восьми королев — хороший пример простой, но нетривиальной проблемы. По этой причине ее часто используют в качестве примера проблемы для различных методов программирования, включая нетрадиционные подходы, такие как программирование ограничений , логическое программирование или генетические алгоритмы . Чаще всего ее используют в качестве примера проблемы, которую можно решить с помощью рекурсивного алгоритма , индуктивно формулируя проблему 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 возможных размещений ферзя. Дальнейшее улучшение, которое исследует только 5 508 возможных размещений ферзя, заключается в объединении метода, основанного на перестановке, с методом ранней обрезки: перестановки генерируются в глубину, и пространство поиска обрезается, если частичная перестановка производит диагональную атаку. Программирование ограничений также может быть очень эффективным для этой проблемы.

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

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

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

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

def  queens ( n :  int ,  i :  int ,  a :  list ,  b :  list ,  c :  list ):  if  i  <  n :  for  j  in  range ( n ):  if  j  не  в  a  и  i  +  j  не  в  b  и  i  -  j  не  в  c :  yield from  queens ( n ,  i  +  1 ,  a  +  [ j ],  b  +  [ i  +  j ],  c  +  [ i  -  j ])  else :  yield  aдля  решения  в  ферзях ( 8 ,  0 ,  [],  [],  []):  распечатать ( решение )

Следующая программа представляет собой реализацию неформального описания решения Дональда Кнута на странице 31, раздел 7.2.2 Backtrack Programming из книги The Art of Computer Programming , том 4B, на языке программирования Python. ^[28]

def  property ( perm :  list ):  for  k  in  range ( 0 ,  len ( perm )):  for  j  in  range ( 0 ,  len ( perm )):  if  j  <  k :  if  perm [ k ]  ==  perm [ j ]:  return  False  elif  abs ( perm [ k ]  -  perm [ j ])  ==  k  -  j :  return  False  return  Truedef  extend ( perm :  list ,  n :  int ):  new_perm =  [  ]  для  p  в  perm :  для  i  в  range ( 0 ,  n ):  new_perm.append ( p + [ i ] ) return new_perm    def  n_queens ( n :  int ):  domain  =  list ( range ( 0 ,  n ))  perm  =  [[]]  for  i  in  range ( n ):  new_perm  =  list ( filter ( property ,  extend ( perm ,  n )))  perm  =  new_perm  return  len ( perm )

• В игре «Седьмой гость » восьмая головоломка: «Дилемма королевы» в игровой комнате особняка Штауфов — это де-факто головоломка восьми королев. ^{[29] : 48–49, 289–290}
• В игре «Профессор Лейтон и любопытная деревня » 130-я головоломка: «Слишком много королев 5» (クイーンの問題5 ) представляет собой головоломку с восемью королевами. ^[30]

• Математическая игра
• Математическая головоломка
• Проблема отсутствия трех в ряд
• Ладийный многочлен
• массив Костаса

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

В Wikibook Algorithm Implementation есть страница по теме: Проблема N-ферзей

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