Войти
| a | b | c | d | e | f | g | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
Задача о восьми ферзях - это задача размещения восьми шахмат ферзей на доске 8 × 8 так, чтобы никакие две ферзя не угрожали друг другу; таким образом, решение требует, чтобы никакие две ферзя не делили одну и ту же строку, столбец или диагональ. Головоломка с восемью ферзями является примером более общей задачи n ферзей размещения n не атакующих ферзей на шахматной доске размером n × n, решения которой существуют для всех натуральных чисел n, за исключением n = 2. и n = 3.
Шахматный композитор Макс Беззель опубликовал головоломку с восемью ферзями в 1848 году. Опубликовал первые решения в 1850 году. Наук также расширил головоломку до задачи n ферзей с n ферзями на шахматной доске n × n клеток.
С тех пор многие математики, в том числе Карл Фридрих Гаусс, работали как над головоломкой о восьми ферзях, так и над ее обобщенной версией n-ферзей. В 1874 г. предложил метод с использованием определителей для поиска решений. J.W.L. Глейшер усовершенствовал подход Гюнтера.
В 1972 году Эдсгер Дейкстра использовал эту задачу, чтобы проиллюстрировать мощь того, что он назвал структурным программированием. Он опубликовал очень подробное описание алгоритма depth-first поиска с возвратом.
Проблема поиска всех решений проблемы 8 ферзей может быть довольно сложной. вычислительно затратно, так как существует 4 426 165 368 (т. е. 64C8 ) возможных расположений восьми ферзей на доске 8 × 8, но только 92 решения. Можно использовать ярлыки, снижающие вычислительные требования, или практические правила, позволяющие избежать вычислительных методов грубой силы. Например, применяя простое правило, ограничивающее каждого ферзя одним столбцом (или строкой), хотя оно все еще считается грубой силой, можно уменьшить количество возможных комбинаций до 16 777 216 (то есть 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 имеет дополнительное свойство что никакие три ферзя не находятся на прямой.
Эти алгоритмы грубой силы для подсчета количества решений вычислительно управляемы для n = 8, но были бы неразрешимыми для проблем n ≥ 20, как 20! = 2,433 × 10. Если цель состоит в том, чтобы найти единственное решение, можно показать, что решения существуют для всех n ≥ 4, без какого-либо поиска. Эти решения демонстрируют ступенчатые шаблоны, как в следующих примерах для n = 8, 9 и 10:
|
|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
приведенные выше примеры могут быть получены с помощью следующих формул. Пусть (i, j) - квадрат в столбце i и строке j на шахматной доске размера n × n, k - целое число.
Один из подходов:
Для n = 8 это приводит к фундаментальному решению 1. Далее следуют еще несколько примеров.
В следующих таблицах указано количество решений для размещения n ферзей на доске n × n, как основных (последовательность A002562 в OEIS ), так и всех (последовательность A000170 в OEIS ).
| n | основной | все | ||
|---|---|---|---|---|
| 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 | <4,973,333,324314,666,222,712 | |||
| 22 | 336,376,244,042 | 2,691,008,701,644 | ||
| 23 | 3,029,242,658,210 | 24,233,937,684,440 <5266> | 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,4665648,2440,340,3165,466,510>27 | 29,363,495,934,315,694 | 234,907,967,154,122,528 |
Загадка с шестью ферзями имеет меньше решений, чем головоломка с пятью ферзями.
Нет известной формулы для точного количества решений или даже для его асимптотического поведения. Доска 27 × 27 - это доска высшего порядка, которая была полностью пронумерована.
Нахождение всех решений загадки восьми ферзей является хорошим примером простая, но нетривиальная проблема. По этой причине он часто используется в качестве примера проблемы для различных методов программирования, включая нетрадиционные подходы, такие как программирование с ограничениями, логическое программирование или генетические алгоритмы. Чаще всего он используется в качестве примера проблемы, которую можно решить с помощью рекурсивного алгоритма, индуктивно формулируя задачу 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), и использует элементы каждой перестановки в качестве индексов для размещения ферзя в каждом ряду.. Затем он отбрасывает доски с диагональными атакующими позициями. Программа backtracking поиск в глубину, небольшое улучшение метода перестановки, строит дерево поиска , рассматривая одну строку доски за раз, исключая большинство нерешенных позиций на очень ранней стадии их построения. Поскольку он отклоняет ладьи и диагональные атаки даже на неполных досках, он проверяет только 15 720 возможных размещений ферзя. Дальнейшее усовершенствование, которое исследует только 5508 возможных размещений маток, состоит в объединении метода на основе перестановок с методом раннего отсечения: перестановки генерируются в глубину, а пространство поиска сокращается, если частичная перестановка дает диагональная атака. Программирование ограничений также может быть очень эффективным для решения этой проблемы.
мин-конфликты решение для 8 ферзей Альтернативой исчерпывающему поиску является алгоритм «итеративного восстановления», который обычно начинается со всех ферзей на доске, например, с одного ферзя на столбец. Затем он подсчитывает количество конфликтов (атак) и использует эвристику, чтобы определить, как улучшить размещение ферзей. Эвристика «минимальные конфликты » - перемещение фрагмента с наибольшим числом конфликтов в квадрат в том же столбце, где число конфликтов наименьшее - особенно эффективен: он находит решение проблемы 1 000 000 ферзей в среднем менее чем за 50 шагов. Это предполагает, что первоначальная конфигурация «достаточно хороша» - если миллион ферзей начинаются в одном ряду, потребуется не менее 999 999 шагов, чтобы исправить это. «Достаточно хорошую» отправную точку можно найти, например, поместив каждого ферзя в отдельный ряд и столбец так, чтобы он конфликтовал с наименьшим количеством ферзей, уже находящихся на доске.
В отличие от поиска с возвратом, описанного выше, итеративное восстановление не гарантирует решения: как и все жадные процедуры, оно может застрять на локальном оптимуме. (В таком случае алгоритм может быть перезапущен с другой начальной конфигурацией.) С другой стороны, он может решать задачи, размер которых на несколько порядков выходит за рамки поиска в глубину.
Эта анимация иллюстрирует возврат для решения проблемы. Ферзь помещается в колонну, которая заведомо не вызывает конфликта. Если столбец не найден, программа возвращается в последнее хорошее состояние и затем пробует другой столбец.
В качестве альтернативы отслеживанию с возвратом решения можно подсчитывать путем рекурсивного перечисления допустимых частичных решений по одной строке за раз. Блокированные диагонали и столбцы отслеживаются с помощью побитовых операций, вместо того, чтобы строить позиции целиком. Это не позволяет восстанавливать отдельные решения.
Ниже приводится программа Pascal, созданная Никлаусом Виртом в 1976 году. одно решение проблемы восьми ферзей.
программа 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], то begin x [i]: = j; a [j]: = ложь; b [i + j]: = ложь; c [i - j]: = ложь; 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.
 | В Wikibook Реализация алгоритма есть страница по теме: Задача N-королев |
