Задача о восьми ферзях

---

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

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

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

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

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

---