Пазл о восьми ферзях

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

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

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

История

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

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

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

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

Проблема нахождения всех решений проблемы 8 ферзей может быть довольно затратной с вычислительной точки зрения, поскольку существует 4 426 165 368 (т.е. ₆₄ C ₈ ) возможных расстановок восьми ферзей на доске 8 × 8, но только 92 решения. Можно использовать ярлыки, которые сокращают вычислительные требования, или практические правила, позволяющие избежать применения вычислительных методов методом грубой силы . Например, применяя простое правило, ограничивающее каждого ферзя одним столбцом (или строкой), которое все еще считается грубой силой, можно уменьшить количество возможных комбинаций до 16 777 216 (то есть 8 ⁸ ) возможных комбинаций. Генерация перестановок еще больше сокращает возможности до 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.

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

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 1

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 2

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 3

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 4

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 5

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 6

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 7

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 8

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 9

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 10

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 11

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение 12

Решение 10 имеет дополнительное свойство, заключающееся в том, что никакие три ферзя не находятся на прямой . В решениях 1 и 8 есть линия из 4 ферзей.

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

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

	а	б	c	d	е	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	г	час

Решение для лестницы на 8 ферзей

	а	б	c	d	е	ж	г	час	я
9										9
8										8
7										7
6										6
5										5
4										4
3										3
2										2
1										1
	а	б	c	d	е	ж	г	час	я

Решение для лестницы на 9 ферзей

	а	б	c	d	е	ж	г	час	я	j
10											10
9											9
8											8
7											7
6											6
5											5
4											4
3											3
2											2
1											1
	а	б	c	d	е	ж	г	час	я	j

Лестничное решение для 10 королев

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

Один из подходов ^[3] -

Если остаток от деления n на 6 не равен 2 или 3, то в списке просто все четные числа, за которыми следуют все нечетные числа, не превышающие n .
В противном случае напишите отдельные списки четных и нечетных чисел (2, 4, 6, 8 - 1, 3, 5, 7).
Если остаток равен 2, поменяйте местами 1 и 3 в нечетном списке и переместите 5 в конец ( 3, 1 , 7, 5 ).
Если остаток равен 3, переместите 2 в конец четного списка и 1,3 в конец нечетного списка (4, 6, 8, 2 - 5, 7, 1, 3 ).
Добавьте нечетный список к четному и разместите ферзей в строках, заданных этими числами, слева направо (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 \times 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

Головоломка с шестью ферзями имеет меньше решений, чем головоломка с пятью ферзями.

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

Число решений имеет асимптотику вида ^[5]^[6] с, в то время как асимптотика для тороидальной шахматной доски имеет равенство всякий раз, когда ^[7]^[8] ${\ displaystyle {\ mathcal {Q}} (n) = ((1 \ pm o (1)) ne ^ {- \ alpha}) ^ {n}}$ ${\ displaystyle \ alpha = 1,942 \ pm 3 \ times 10 ^ {- 3}}$ ${\ Displaystyle Т (п) \ leq ((1 + о (1)) ne ^ {- 3}) ^ {п}}$ ${\ Displaystyle п \ экв 1,5 \ mod 6.}$

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

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

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

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

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

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

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

Матрица перестановок

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

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

Полиа изучил задачу n ферзей на тороидальной («пончиковой») доске и показал, что решение существует на доске n × n тогда и только тогда, когда n не делится на 2 или 3. ^[12] В 2009 г. Пирсон и Пирсон алгоритмически заселил трехмерные доски ( n × n × n ) n ² ферзями и предположил, что их кратные числа могут дать решения для четырехмерной версии головоломки. ^[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 -Queens Завершение

В статье 2017 г. ^[19] исследуется проблема « На шахматной доске размером n × n , на которой уже размещено несколько ферзей, можно ли разместить ферзя в каждом оставшемся ряду, чтобы никакие две ферзя не атаковали друг друга?» и несколько связанных проблем. Авторы утверждают, что эти задачи являются NP-полными ^[20] и # P-полными .

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

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

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

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

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

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

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

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

программа  8queen1 ( вывод ) ; var  i  :  целое число ;  q  :  логический ;  a  :  массив [  1  ..  8 ]  логических значений  ; b : массив [ 2..16 ] логических значений ; _ _ c : массив [ - 7 .. 7 ] логических значений ; x : массив [ 1 .. 8 ] целых чисел ;                        процедура  try (  i  :  integer ;  var  q  :  boolean ) ;  var  j  :  целое число ;  начало  j  : =  0 ;  повторить  j  : =  j  +  1 ;  q  : =  ложь ;  если  a [  j ]  и  b [  i  +  j ]  и  c [  i  -  j ] ,  то  начинаем  x [ i  ]  : =  j ;  a [  j ]  : =  ложь ;  b [  i  +  j ]  : =  ложь ;  c [  i  -  j ]  : =  ложь ;  если  i  <  8,  то  начать  попытку (  i  +  1 ,  q ) ;  если  не  q,  то  начинаем  a [  j ]  : =  true ;  б[  i  +  j ]  : =  верно ;  c [  i  -  j ]  : =  верно ;  конец  конец  else  q  : =  истина  конец  до  q  или  ( j  =  8 ) ;  конец ; начинают для  I  : =  1  до  8  сделать  [ я ] : = верно ; для i : = от 2 до 16 выполните b [ i ] : = true ; для i : = - от 7 до 7 сделать c [ i ] : = true ; попробуйте ( 1 , q ) ; если q, то для i : = 1                                до  8  сделать  запись (  х [  я ] : 4 ) ; Writeln end .

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

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

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

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

использованная литература

^ EJ Hoffman et al., "Построение решений m проблемы Куинса". Математический журнал , Vol. XX (1969), стр. 66–72. [1]
^ a b У. У. Роуз Болл (1960) «Проблема восьми королев», в « Mathematical Recreations and Essays» , Macmillan, New York, pp. 165–171.
^ a b c Бо Бернхардссон (1991). «Явные решения проблемы N-ферзей для всех N». SIGART Bull . 2 (2): 7. DOI : 10,1145 / 122319,122322 .
^ Проект Q27
^ Симкин, Майкл (28 июля 2021). «Количество конфигураций $ n $-королев» . Цитировать журнал требует |journal=( помощь )
^ Sloman, Leila (21 сентября 2021). «Математик отвечает на шахматную задачу об атаке ферзей» . Журнал Quanta . Проверено 22 сентября 2021 года .
↑ Лурия, Зур (15 мая 2017 г.). «Новые границы количества конфигураций n ферзей» . Цитировать журнал требует |journal=( помощь )
^ Bowtell, Candida; Кееваш, Питер (16 сентября 2021 г.). «Проблема $ n $ королев» . Цитировать журнал требует |journal=( помощь )
↑ Дж. Барр и С. Рао (2006), Проблема n-Куинса в более высоких измерениях, Elemente der Mathematik, том 61 (4), стр. 133–137.
^ Мартин С. Пирсон. «Королевы на шахматной доске - за гранью второго измерения» (php) . Проверено 27 января 2020 года .
↑ Chatham, Doug (1 декабря 2018 г.). «Размышления о проблеме n + k драконьих королей» . Журнал развлекательной математики . 5 (10): 39–55. DOI : 10,2478 / РММ-2018-0007 .
^ G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, Джордж Полиа: Сборник статей Vol. IV, GC. Рота, изд., MIT Press, Кембридж, Лондон, 1984, стр. 237–247.
^ [2]
^ Бургер, AP; Кокейн, EJ; Mynhardt, CM (1997), «Доминирование и неизбыточность в графе ферзей», Дискретная математика , 163 (1–3): 47–66, DOI : 10.1016 / 0012-365X (95) 00327-S , HDL : 1828 / 2670 , Руководство по ремонту 1428557
^ Уикли, Уильям Д. (2018), «Куинс по всему миру за двадцать пять лет», в Гере, Ралукка; Хейнс, Тереза В .; Хедетниеми, Стивен Т. (ред.), Теория графов: любимые гипотезы и открытые задачи - 2 , Проблемные книги по математике, Cham: Springer, стр. 43–54, doi : 10.1007 / 978-3-319-97686-0_5 , Руководство по ремонту 3889146
^ "Королева и проблема рыцарей" . Архивировано из оригинального 16 октября 2005 года . Проверено 20 сентября 2005 года .
^ Проблема девяти ферзей
^ О. Демирёрс, Н. Рафраф и М. М. Таник. Получение решений n ферзей из магических квадратов и построение магических квадратов из решений n ферзей. Журнал развлекательной математики, 24: 272–280, 1992.
^ Гент, Ян П .; Джефферсон, Кристофер; Соловей, Питер (август 2017). «Сложность завершения n -Queens» . Журнал исследований искусственного интеллекта . 59 : 815–848. DOI : 10.1613 / jair.5512 . ISSN 1076-9757 . Проверено 7 сентября 2017 года .
^ "Загадка 8 королев" . www.claymath.org . Математический институт Клэя . 2 сентября 2017.
^ Алгоритм полиномиального времени для задачи N-Queen Рока Сосича и Джун Гу, 1990. Описывает время выполнения до 500 000 Queens, что было максимальным значением, которое они могли выполнить из-за ограничений памяти.
^ Ие, Zongyan (февраль 2002). «Бит-векторное кодирование задачи n-queen». Уведомления ACM SIGPLAN . 37 (2): 68–70. DOI : 10.1145 / 568600.568613 .
^ Ричардс, Мартин (1997). Алгоритмы обратного отслеживания в MCPL с использованием битовых шаблонов и рекурсии (PDF) (Технический отчет). Компьютерная лаборатория Кембриджского университета. UCAM-CL-TR-433.
↑ Wirth, 1976, стр. 145
^ DeMaria, Rusel (15 ноября 1993). Седьмой гость: официальное руководство по стратегии (PDF) . Prima Games. ISBN 978-1-5595-8468-5. Проверено 22 апреля 2021 года .
^ "ナゾ 130 クイーンの問題 5" .ゲームの匠(на японском) . Проверено 17 сентября 2021 года .

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

Белл, Иордания; Стивенс, Бретт (2009). «Обзор известных результатов и областей исследований для n- королев» . Дискретная математика . 309 (1): 1–31. DOI : 10.1016 / j.disc.2007.12.043 .
Уоткинс, Джон Дж. (2004). Через доску: Математика шахматных задач . Принстон: Издательство Принстонского университета. ISBN 978-0-691-11503-0.
О.-Дж. Даль , Э. У. Дейкстра , Структурное программирование К. Хоара , Academic Press, Лондон, 1972 ISBN 0-12-200550-3, см. Стр. 72–82 для решения Дейкстры проблемы 8 Куинсов .
Allison, L .; Yee, CN; МакГоги, М. (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), Instituto de Matematicas, Area de la Investigacion Cientifica, Circuito Exterior, Ciudad Universitaria, Мексика.
Вирт, Никлаус (1976), «Алгоритмы + структуры данных = программы» , Серия Прентис-Холла в автоматических вычислениях , Прентис-Холл, Bibcode : 1976adsp.book ..... W , ISBN 978-0-13-022418-7
Вирт, Никлаус (2004 г.) [обновлено 2012 г.]. «Проблема восьми королев». Алгоритмы и структуры данных (PDF) . Версия Оберона с исправлениями и авторизованными доработками. С. 114–118.

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

В разделе " Реализация алгоритма Викибука" есть страница на тему: Проблема N-ферзей.

Вайсштейн, Эрик В. "Проблема Королевы" . MathWorld .
queens-cpm на GitHub Eight Queens Puzzle в Turbo Pascal для CP / M
8-queens.py на GitHub Eight Queens Puzzle однострочное решение на Python
Решения на более чем 100 различных языках программирования (на Rosetta Code )

[1] EJ Hoffman et al., "Построение решений m проблемы Куинса". Математический журнал , Vol. XX (1969), стр. 66–72. [1]

[rouse_ball_1960-2] У. У. Роуз Болл (1960) «Проблема восьми королев», в « Mathematical Recreations and Essays» , Macmillan, New York, pp. 165–171.

[bernhardsson-3] Бо Бернхардссон (1991). «Явные решения проблемы N-ферзей для всех N». SIGART Bull . 2 (2): 7. DOI : 10,1145 / 122319,122322 .

[4] Проект Q27

[5] Симкин, Майкл (28 июля 2021). «Количество конфигураций $ n $-королев» . Цитировать журнал требует |journal=( помощь )

[6] Sloman, Leila (21 сентября 2021). «Математик отвечает на шахматную задачу об атаке ферзей» . Журнал Quanta . Проверено 22 сентября 2021 года .

[7] Лурия, Зур (15 мая 2017 г.). «Новые границы количества конфигураций n ферзей» . Цитировать журнал требует |journal=( помощь )

[8] Bowtell, Candida; Кееваш, Питер (16 сентября 2021 г.). «Проблема $ n $ королев» . Цитировать журнал требует |journal=( помощь )

[9] Дж. Барр и С. Рао (2006), Проблема n-Куинса в более высоких измерениях, Elemente der Mathematik, том 61 (4), стр. 133–137.

[10] Мартин С. Пирсон. «Королевы на шахматной доске - за гранью второго измерения» (php) . Проверено 27 января 2020 года .

[11] Chatham, Doug (1 декабря 2018 г.). «Размышления о проблеме n + k драконьих королей» . Журнал развлекательной математики . 5 (10): 39–55. DOI : 10,2478 / РММ-2018-0007 .

[12] G. Pólya, Uber die "doppelt-periodischen" Losungen des n-Damen-Problems, Джордж Полиа: Сборник статей Vol. IV, GC. Рота, изд., MIT Press, Кембридж, Лондон, 1984, стр. 237–247.

[13] [2]

[14] Бургер, AP; Кокейн, EJ; Mynhardt, CM (1997), «Доминирование и неизбыточность в графе ферзей», Дискретная математика , 163 (1–3): 47–66, DOI : 10.1016 / 0012-365X (95) 00327-S , HDL : 1828 / 2670 , Руководство по ремонту 1428557

[15] Уикли, Уильям Д. (2018), «Куинс по всему миру за двадцать пять лет», в Гере, Ралукка; Хейнс, Тереза В .; Хедетниеми, Стивен Т. (ред.), Теория графов: любимые гипотезы и открытые задачи - 2 , Проблемные книги по математике, Cham: Springer, стр. 43–54, doi : 10.1007 / 978-3-319-97686-0_5 , Руководство по ремонту 3889146

[16] "Королева и проблема рыцарей" . Архивировано из оригинального 16 октября 2005 года . Проверено 20 сентября 2005 года .

[17] Проблема девяти ферзей

[18] О. Демирёрс, Н. Рафраф и М. М. Таник. Получение решений n ферзей из магических квадратов и построение магических квадратов из решений n ферзей. Журнал развлекательной математики, 24: 272–280, 1992.

[19] Гент, Ян П .; Джефферсон, Кристофер; Соловей, Питер (август 2017). «Сложность завершения n -Queens» . Журнал исследований искусственного интеллекта . 59 : 815–848. DOI : 10.1613 / jair.5512 . ISSN 1076-9757 . Проверено 7 сентября 2017 года .

[20] "Загадка 8 королев" . www.claymath.org . Математический институт Клэя . 2 сентября 2017.

[21] Алгоритм полиномиального времени для задачи N-Queen Рока Сосича и Джун Гу, 1990. Описывает время выполнения до 500 000 Queens, что было максимальным значением, которое они могли выполнить из-за ограничений памяти.

[22] Ие, Zongyan (февраль 2002). «Бит-векторное кодирование задачи n-queen». Уведомления ACM SIGPLAN . 37 (2): 68–70. DOI : 10.1145 / 568600.568613 .

[23] Ричардс, Мартин (1997). Алгоритмы обратного отслеживания в MCPL с использованием битовых шаблонов и рекурсии (PDF) (Технический отчет). Компьютерная лаборатория Кембриджского университета. UCAM-CL-TR-433.

[24] Wirth, 1976, стр. 145

[25] DeMaria, Rusel (15 ноября 1993). Седьмой гость: официальное руководство по стратегии (PDF) . Prima Games. ISBN 978-1-5595-8468-5. Проверено 22 апреля 2021 года .

[26] "ナゾ 130 クイーンの問題 5" .ゲームの匠(на японском) . Проверено 17 сентября 2021 года .

[ 1]

vтеМагические полигоны
Типы	Магический круг Магический шестиугольник Магическая гексаграмма Магический квадрат Волшебная звезда Магический треугольник
Связанные фигуры	Альфа-магический квадрат Антимагический квадрат Геомагический квадрат Гетероквадрат Пандиагональный магический квадрат Самый совершенный магический квадрат
Формы более высоких размеров	Волшебный куб классы Магический гиперкуб Волшебный гиперпучок
Классификация	Ассоциативный магический квадрат Пандиагональный магический квадрат Мультимагический квадрат
Связанные понятия	Латинский квадрат Слово квадрат Номер Scrabble Пазл о восьми ферзях Магическая константа Магический граф Волшебная серия