Загадка восьми королев - Eight queens puzzle

а б c d е ж грамм час
8
Chessboard480.svg
f8 white queen
d7 white queen
g6 white queen
a5 white queen
h4 white queen
b3 white queen
e2 white queen
c1 white queen
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 - целое число.

Один из подходов

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

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

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

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

Eight-queens-animation.gif

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

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

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

Ниже приводится программа на языке 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.

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

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

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

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

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