Головоломка с восемью ферзями

Головоломка с восемью ферзями - это задача разместить восемь шахматных ферзей на шахматной доске 8 × 8 так, чтобы никакие два ферзя не угрожали друг другу; таким образом, решение требует, чтобы никакие два ферзя не находились в одной и той же строке, столбце или диагонали. Есть 92 решения. Впервые проблема была поставлена ​​в середине 19 века. В современную эпоху она часто используется в качестве примера задачи для различных методов компьютерного программирования .

Головоломка с восемью ферзями — это частный случай более общей задачи о n ферзях, заключающейся в размещении n неатакующих ферзей на шахматной доске размером n × n . Решения существуют для всех натуральных чисел n , за исключением n = 2 и n = 3. Хотя точное количество решений известно только для n ≤ 27, работа Симкина в 2021 году установила, что асимптотическая скорость роста числа решений равна (0,143 н ) ^н .

Шахматный композитор Макс Беззель ^{опубликовал} головоломку с восемью ферзями в 1848 году. Франц Наук опубликовал первые решения в 1850 году .

С тех пор многие математики , в том числе Карл Фридрих Гаусс , работали как над головоломкой с восемью ферзями, так и над ее обобщенной версией с n ферзями. В 1874 г. С. Гюнтер предложил метод с использованием определителей для нахождения решений. ^[1] JWL Glaisher усовершенствовал подход Гюнтера.

В 1972 году Эдсгер Дейкстра использовал эту задачу, чтобы проиллюстрировать мощь того, что он назвал структурным программированием . Он опубликовал очень подробное описание алгоритма поиска с возвратом в глубину . ^[2]

Задача нахождения всех решений задачи о восьми ферзях может быть довольно затратной с вычислительной точки зрения, поскольку существует 4 426 165 368 возможных вариантов расположения восьми ферзей на доске 8 × 8, ^[a] , но только 92 решения. Можно использовать ярлыки, которые уменьшают требования к вычислениям, или эмпирические правила, которые избегают вычислительных методов грубой силы . Например, применяя простое правило, которое выбирает по одному ферзю из каждого столбца, можно уменьшить количество возможных комбинаций до 16 777 216 (то есть 8 ⁸ ). Генерация перестановок еще больше сокращает возможности до 40 320 (то есть 8! ), которые затем можно проверить на диагональные атаки.

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Единственное симметричное решение головоломки с восемью ферзями ( вплоть до поворота и отражения)

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 1

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 2

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 3

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 4

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 5

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 6

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 7

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 8

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 9

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 10

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 11

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Решение 12

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

Лестничное решение для 8 королев

	а	б	с	г	е	ф	г	час	я
9										9
8										8
7										7
6										6
5										5
4										4
3										3
2										2
1										1
	а	б	с	г	е	ф	г	час	я

Лестничное решение для 9 королев

	а	б	с	г	е	ф	г	час	я	Дж
10											10
9											9
8											8
7											7
6											6
5											5
4											4
3											3
2											2
1											1
	а	б	с	г	е	ф	г	час	я	Дж

Лестничное решение на 10 мест размера "queen-size"

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