Загадка восьми королев - Eight queens puzzle
а | б | 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.
История
Шахматный композитор Макс Беззел опубликовал восемь ферзей головоломки в 1848. Франц Nauck опубликовал первые решения в 1850. Nauck также расширили головоломки в п Куинз проблемы с п ферзей на шахматной доске п × п квадратов.
С тех пор многие математики , в том числе Карл Фридрих Гаусс , работали как над головоломкой о восьми ферзях, так и над ее обобщенной версией n- королев. В 1874 г. С. Гюнтер предложил метод поиска решений с использованием определителей . JWL Glaisher усовершенствовал подход Гюнтера.
В 1972 году Эдсгер Дейкстра использовал эту проблему, чтобы проиллюстрировать мощь того, что он назвал структурным программированием . Он опубликовал очень подробное описание алгоритма поиска с возвратом в глубину . 2
Конструирование и подсчет решений
Проблема поиска всех решений проблемы 8 ферзей может быть довольно затратной в вычислительном отношении, поскольку существует 4 426 165 368 (т.е. 64 C 8 ) возможных расстановок восьми ферзей на доске 8 × 8, но только 92 решения. Можно использовать ярлыки, которые снижают вычислительные требования, или практические правила, позволяющие избежать вычислительных методов грубой силы . Например, применяя простое правило, ограничивающее каждого ферзя одним столбцом (или строкой), которое все еще считается грубой силой, можно уменьшить количество возможных комбинаций до 16 777 216 (то есть 8 8 ) возможных комбинаций. Генерация перестановок еще больше сокращает возможности до 40 320 (то есть 8! ), Которые затем проверяются на диагональные атаки.
Решения
У головоломки с восемью ферзями есть 92 различных решения. Если решения, которые отличаются только операциями симметрии вращения и отражения доски, засчитываются как одно, головоломка имеет 12 решений. Это так называемые фундаментальные решения; представители каждого из них показаны ниже.
Фундаментальное решение обычно имеет восемь вариантов (включая его исходную форму), полученных путем поворота на 90, 180 или 270 ° и последующего отражения каждого из четырех вариантов поворота в зеркале в фиксированном положении. Однако, если решение эквивалентно собственному повороту на 90 ° (как это происходит с одним решением с пятью ферзями на доске 5 × 5), это фундаментальное решение будет иметь только два варианта (само и его отражение). Если решение эквивалентно собственному повороту на 180 ° (но не повороту на 90 °), оно будет иметь четыре варианта (само и его отражение, его поворот на 90 ° и его отражение). Если n > 1, решение не может быть эквивалентным своему собственному отражению, потому что для этого потребуется, чтобы две ферзя смотрели друг на друга. Из 12 фундаментальных решений проблемы с восемью ферзями на доске 8 × 8 ровно одно (решение 12 ниже) равно его собственному повороту на 180 °, и ни одно не равно его повороту на 90 °; таким образом, количество различных решений равно 11 × 8 + 1 × 4 = 92.
Все принципиальные решения представлены ниже:
|
|
|
|
|
|
|
|
|
|
|
|
Решение 10 имеет дополнительное свойство, заключающееся в том, что никакие три ферзя не находятся на прямой . В решениях 1 и 8 есть линия из 4 ферзей.
Существование решений
Алгоритмы грубой силы для подсчета количества решений вычислительно управляемы для n = 8 , но были бы неразрешимыми для задач n ≥ 20 , как 20! = 2,433 × 10 18 . Если цель состоит в том, чтобы найти единственное решение, можно показать, что решения существуют для всех n ≥ 4, без какого-либо поиска. Эти решения демонстрируют ступенчатые модели, как в следующих примерах для n = 8, 9 и 10:
|
|
Приведенные выше примеры могут быть получены с помощью следующих формул. Пусть ( i , j ) - квадрат в столбце i и строке j на шахматной доске n × n , k - целое число.
Один из подходов
- Если остаток от деления 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 × 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 - это доска высшего порядка, которая была полностью пронумерована.
Число решений имеет асимптотик вида с в то время как асимптотика для тороидальной шахматной доски с равенством когда это
Связанные проблемы
- Высшие измерения
- Найдите количество не атакующих ферзей, которые могут быть помещены в d- мерное шахматное пространство размера n . Более n ферзей могут быть помещены в некоторые более высокие измерения (наименьший пример - четыре не атакующих ферзя в шахматном пространстве 3 × 3 × 3), и фактически известно, что для любого k существуют более высокие измерения, где n k ферзей недостаточно, чтобы атаковать все клетки.
- Использование фигур кроме ферзей
- На доске 8х8 можно разместить 32 коня или 14 слонов , 16 королей или восемь ладей , чтобы никакие две фигуры не атаковали друг друга. Фигуры фей также заменены ферзями. В случае с рыцарями простое решение - разместить по одному на каждую клетку данного цвета, поскольку они перемещаются только к противоположному цвету. Решение также легко для ладей и королей. Восемь ладей могут быть размещены по длинной диагонали (среди тысяч других решений), а 16 королей размещаются на доске, разделив ее на 2 на 2 клетки и разместив королей в эквивалентных точках на каждой клетке.
- Шахматные вариации
- Связанные проблемы могут быть заданы для разновидностей шахмат, таких как сёги . Например, задача n + k королей драконов требует разместить k пешек сёги и n + k взаимно не атакующих королей-драконов на доску сёги n × n .
- В математике, матрица перестановок можно рассматривать геометрически как набор п точек , лежащих на площадях в п × п шахматной доске, таким образом, что каждая строка или столбец содержит только одну точку. Таким образом, матрица перестановок порядка n является решением головоломки с n ручьями.
- Нестандартные доски
- Полиа изучил задачу n ферзей на тороидальной («пончиковой») доске и показал, что существует решение на доске n × n тогда и только тогда, когда n не делится на 2 или 3. В 2009 году Пирсон и Пирсон алгоритмически заселили трехмерные доски ( n × n × n ) с n 2 ферзями, и предположил, что их кратные могут дать решения для четырехмерной версии головоломки.
- Господство
- Для доски размером n × n число доминирования - это минимальное количество ферзей (или других фигур), необходимое для атаки или занятия каждой клетки. Для n = 8 число доминирования ферзя равно 5.
- Королевы и другие предметы
- Варианты включают смешивание ферзей с другими фигурами; например, размещение m ферзей и m рыцарей на доске n × n так, чтобы ни одна фигура не атаковала другую, или размещение ферзей и пешек так, чтобы никакие две ферзя не атаковали друг друга.
- В 1992 году Демирёрс, Рафраф и Таник опубликовали метод преобразования некоторых магических квадратов в решения n- королев, и наоборот.
- В матрице размера n × n разместите каждую цифру от 1 до n в n местах матрицы, чтобы никакие два экземпляра одной и той же цифры не находились в одной строке или столбце.
- Рассмотрим матрицу с одним основным столбцом для каждого из n рангов доски, одним основным столбцом для каждого из n файлов и одним второстепенным столбцом для каждой из 4 n - 6 нетривиальных диагоналей доски. Матрица имеет n 2 строк: по одной для каждого возможного размещения ферзя, и каждая строка имеет 1 в столбцах, соответствующих рангу, вертикали и диагоналям этого квадрата, и 0 во всех остальных столбцах. Тогда проблема n ферзей эквивалентна выбору подмножества строк этой матрицы так, чтобы каждый первичный столбец имел 1 ровно в одной из выбранных строк, а каждый вторичный столбец имел 1 не более чем в одной из выбранных строк; это пример обобщенной задачи о точном покрытии , другим примером которой является судоку .
- n -Queens Завершение
- В статье 2017 года исследовалась проблема: «На шахматной доске размером n × n, на которой уже размещено несколько ферзей, можно ли разместить ферзя в каждом оставшемся ряду, чтобы никакие две ферзя не атаковали друг друга?» и несколько связанных проблем. Авторы утверждали, что эти задачи NP-полны и # P-полны .
Упражнения по разработке алгоритмов
Нахождение всех решений загадки восьми ферзей - хороший пример простой, но нетривиальной задачи. По этой причине он часто используется в качестве примера проблемы для различных методов программирования, включая нетрадиционные подходы, такие как программирование с ограничениями , логическое программирование или генетические алгоритмы . Чаще всего он используется как пример проблемы, которую можно решить с помощью рекурсивного алгоритма , индуктивно формулируя задачу n ферзей в терминах добавления одного ферзя к любому решению задачи размещения n −1 ферзей на n ферзях. × n шахматная доска. Индукционный отжался с решением «проблемами» размещение 0 ферзей на шахматной доске, которая является пустой шахматной доской.
Этот метод можно использовать гораздо более эффективно, чем наивный алгоритм перебора , который рассматривает все 64 8 = 2 48 = 281 474 976 710 656 возможных слепых размещений восьми ферзей, а затем фильтрует их, чтобы удалить все размещения, которые ставят два ферзей либо на одном поле (остается только 64! / 56! = 178 462 987 637 760 возможных размещений), либо во взаимно атакующих позициях. Этот очень плохой алгоритм, среди прочего, будет давать одни и те же результаты снова и снова во всех различных перестановках назначений восьми ферзей, а также повторять одни и те же вычисления снова и снова для разных подмножеств каждого. решение. Более совершенный алгоритм прямого перебора размещает по одному ферзю в каждом ряду, что приводит только к 8 8 = 2 24 = 16 777 216 блайндам.
Можно сделать намного лучше. Один алгоритм решает загадку с восемью ладьями , генерируя перестановки чисел от 1 до 8 (из которых 8! = 40 320), и использует элементы каждой перестановки в качестве индексов для размещения ферзя в каждом ряду. Затем он отбрасывает доски с диагональными атакующими позициями. Программа поиска с возвратом в глубину , небольшое усовершенствование метода перестановки, строит дерево поиска , рассматривая одну строку платы за раз, устраняя большинство нерешенных позиций платы на очень ранней стадии их построения. Поскольку он отклоняет ладьи и диагональные атаки даже на неполных досках, он проверяет только 15 720 возможных размещений ферзя. Дальнейшее улучшение, которое исследует только 5508 возможных размещений ферзей, заключается в объединении метода на основе перестановок с методом раннего отсечения: перестановки генерируются в первую очередь в глубину, а пространство поиска сокращается, если частичная перестановка вызывает диагональную атаку. Программирование с ограничениями также может быть очень эффективным для решения этой проблемы.
Альтернативой исчерпывающему поиску является алгоритм «итеративного ремонта», который обычно начинается со всех ферзей на доске, например, с одного ферзя на столбец. Затем он подсчитывает количество конфликтов (атак) и использует эвристику, чтобы определить, как улучшить размещение ферзей. В « минимальной конфликты » эвристический - перемещение куска с наибольшим числом конфликтов на площадь в той же самой колонке , где число конфликтов является наималейшим - особенно эффективно: он находит решение проблемы 1000000 ферзя менее чем за 50 шагов в среднем. Это предполагает, что первоначальная конфигурация «достаточно хороша» - если все миллионы ферзей начинаются в одном ряду, потребуется не менее 999 999 шагов, чтобы исправить это. «Достаточно хорошую» отправную точку можно найти, например, поместив каждого ферзя в отдельный ряд и столбец так, чтобы он конфликтовал с наименьшим количеством ферзей, уже находящихся на доске.
В отличие от поиска с возвратом, описанного выше, итеративное восстановление не гарантирует решения: как и все жадные процедуры, оно может застрять на локальном оптимуме. (В таком случае алгоритм может быть перезапущен с другой начальной конфигурацией.) С другой стороны, он может решать проблемы, размер которых на несколько порядков выходит за рамки поиска в глубину.
Эта анимация иллюстрирует возврат для решения проблемы. Ферзь помещается в колонну, которая, как известно, не вызывает конфликта. Если столбец не найден, программа возвращается в последнее хорошее состояние и затем пробует другой столбец.
В качестве альтернативы отслеживанию с возвратом решения можно подсчитывать путем рекурсивного перечисления действительных частичных решений, по одной строке за раз. Блокированные диагонали и столбцы отслеживаются с помощью побитовых операций, вместо того, чтобы строить позиции целиком. Это не позволяет восстанавливать отдельные решения.
Пример программы
Ниже приводится программа на языке Pascal, написанная Никлаусом Виртом в 1976 году. Она находит одно решение проблемы восьми ферзей.
program eightqueen1(output);
var i : integer; q : boolean;
a : array[ 1 .. 8] of boolean;
b : array[ 2 .. 16] of boolean;
c : array[−7 .. 7] of boolean;
x : array[ 1 .. 8] of integer;
procedure try( i : integer; var q : boolean);
var j : integer;
begin
j := 0;
repeat
j := j + 1;
q := false;
if a[ j] and b[ i + j] and c[ i − j] then
begin
x[ i ] := j;
a[ j] := false;
b[ i + j] := false;
c[ i − j] := false;
if i < 8 then
begin
try( i + 1, q);
if not q then
begin
a[ j] := true;
b[ i + j] := true;
c[ i − j] := true;
end
end
else
q := true
end
until q or (j = 8);
end;
begin
for i := 1 to 8 do a[ i] := true;
for i := 2 to 16 do b[ i] := true;
for i := −7 to 7 do c[ i] := true;
try( 1, q);
if q then
for i := 1 to 8 do write( x[ i]:4);
writeln
end.
В популярной культуре
- В игре «Седьмой гость» восьмая головоломка: «Дилемма королевы» в игровой комнате особняка Штауфа фактически представляет собой головоломку с восемью царицами.
- В игре « Профессор Лейтон и любопытная деревня» 130-я головоломка: «Слишком много королев 5» (ク イ ー ン の 問題 5 ) представляет собой головоломку с восемью ферзями.
Смотрите также
- Математическая игра
- Математическая головоломка
- Нет проблем с тремя рядами
- Полином ладьи
- Массив Костаса
использованная литература
дальнейшее чтение
- Белл, Иордания; Стивенс, Бретт (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.
внешние ссылки
- Вайсштейн, Эрик В. "Проблема королевы" . MathWorld .
- queens-cpm на GitHub Eight Queens Puzzle в Turbo Pascal для CP / M
- 8-queens.py на GitHub Eight Queens Puzzle однострочное решение на Python
- Решения на более чем 100 различных языках программирования (на Rosetta Code )