Задача о восьми ферзях ({g;gcg k fkv,bn syj[x])

Задача о восьми ферзях.
Одно из решений: a7, b4, c2, d8, e6, f1, g3, h5:(87)

Зада́ча о восьми́ фе́рзя́х — широко известная комбинаторная задача по расстановке фигур на шахматной доске. Исходная формулировка: «Расставить на стандартной 64-клеточной шахматной доске 8 ферзей так, чтобы ни один из них не находился под боем другого». Подразумевается, что ферзь бьёт все клетки, расположенные по вертикалям, горизонталям и обеим диагоналям.

Обобщение задачи — расставить таким же образом ферзей на произвольном прямоугольном поле, в частности, квадратном со стороной $n$.

Формулировка

Строго математически задачу можно сформулировать несколькими способами, например, так: «Заполнить матрицу размером $8\times 8$ нулями и единицами таким образом, чтобы сумма всех элементов матрицы была равна 8, при этом сумма элементов ни в одном столбце, строке или диагональном ряде матрицы не превышала единицы».

Конечная цель, поставленная перед решающим задачу, может формулироваться в нескольких вариантах:

• Построить одно любое решение задачи.
• Аналитически доказать, что решение существует.
• Определить количество решений.
• Построить все возможные решения.
• Создать компьютерную программу, находящую все возможные решения задачи. Одна из типовых задач по программированию алгоритмов перебора.

Иногда постановка задачи требует нахождения способов расстановки $N$ ферзей на доске $N\times N$ клеток (заметим, что при $1<N<4$ задача не имеет решения).

Особенности решения

Общее число возможных расположений 8 ферзей на 64-клеточной доске равно $4\,426\,165\,368={\dfrac {64!}{8!\,(64-8)!}}$ (формула сочетаний). Общее число возможных расположений, удовлетворяющих условию задачи, равно 92. Множество этих 92 расположений разбивается на 12 подмножеств (11 подмножеств по 8 расположений и одно из четырёх оставшихся), в каждом из которых все расположения получаются друг из друга путём преобразований симметрии: отражения от вертикальной и горизонтальной осей, отражения от диагоналей доски и поворотов на 90, 180 и 270 градусов.

Современные компьютеры уже позволяют произвести решение задачи (нахождение любого или всех решений) путём полного перебора всех возможных вариантов расстановки, но обычно такое решение считается некорректным: от решающего задачу требуется найти алгоритм, который позволил бы существенно сократить объём перебора. Например, очевидно, что на одной горизонтали или вертикали доски не может находиться больше одного ферзя, поэтому алгоритм решения изначально не должен включать в перебор позиции, где два ферзя стоят на одной горизонтали или вертикали. Даже такое простое правило способно существенно уменьшить число возможных расположений: $16\,777\,216=8^{8}$ вместо 4 426 165 368. Генерируя перестановки, являющиеся решениями задачи о восьми ладьях, и проверяя затем атаки по диагоналям, можно сократить число возможных расположений всего до $40\,320=8!$. Если же при генерации позиций также учитывать условие нападения по диагонали, то скорость счёта возрастает на порядок и число циклов для решения задачи составит 4022.

Один из типовых алгоритмов решения задачи — использование поиска с возвратом: первый ферзь ставится на первую горизонталь, затем каждый следующий ставится на следующую так, чтобы его не били ранее установленные ферзи. Если на очередном этапе постановки свободных полей не оказывается, происходит возврат на шаг назад — переставляется ранее установленный ферзь.

Ссылки

• Фрактальное решение задачи для досок $N\times N$ , если N=(a1)•(a2)•…•(an), где а1 ≥ 4 и а2,…,аn > 4 (А.Ермаков, 2011)
• Общий метод n queens с реализацией на java