Математическая шахматная задача

Математическая шахматная задача — это математическая задача , сформулированная с использованием шахматной доски и шахматных фигур. Эти задачи относятся к развлекательной математике . Наиболее известными задачами такого рода являются головоломка о восьми ферзях и задача о путешествии коня , которые связаны с теорией графов и комбинаторикой . Многие известные математики изучали математические шахматные задачи, такие как Табит , Эйлер , Лежандр и Гаусс . ^[1] Помимо поиска решения конкретной задачи, математики обычно интересуются подсчетом общего числа возможных решений, поиском решений с определенными свойствами, а также обобщением задач на доски N×N или M×N.

Проблема независимости [ править ]

( Проблема независимости или незащищенность ^{[ нужна цитата ]}) — задача, в которой по заданному типу шахматных фигур (ферзь, ладья, слон, конь или король) необходимо найти максимальное число, которое можно разместить на шахматной доске так, чтобы ни одна из фигур не атаковала друг друга. Также необходимо найти фактическое расположение для этого максимального количества штук. Самая известная задача этого типа — головоломка с восемью ферзями . Проблемы расширяются, если задаться вопросом, сколько существует возможных решений. Дальнейшие обобщения применимы к платам NxN. ^[2]^[3]

На шахматной доске 8×8 может быть 16 независимых королей, 8 независимых ферзей, 8 независимых ладей, 14 независимых слонов или 32 независимых коня. ^[4]Решения для королей, слонов, королев и коней показаны ниже. Чтобы получить 8 независимых ладей, достаточно расположить их на одной из главных диагоналей.

	а	б	с	д	Это	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	Это	ж	г	час

16 независимых королей

	а	б	с	д	Это	ж	г	час
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
	а	б	с	д	Это	ж	г	час

8 независимых ладей

	а	б	с	д	Это	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	Это	ж	г	час

14 независимых епископов

	а	б	с	д	Это	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	Это	ж	г	час

32 независимых рыцаря

Проблемы доминирования [ править ]

( Задача доминирования или покрытия ) . заключается в нахождении минимального количества фигур данного типа, которое можно разместить на шахматной доске, чтобы все свободные поля были атакованы хотя бы один раз Это частный случай задачи о вершинном покрытии . Минимальное количество доминирующих королей - 9, ферзей - 5, ладей - 8, слонов - 8, коней - 12. Чтобы получить 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
	а	б	с	д	Это	ж	г	час

5 доминирующих королев

	а	б	с	д	Это	ж	г	час
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
	а	б	с	д	Это	ж	г	час

12 доминирующих рыцарей

Проблемы доминирования также иногда формулируются как требование найти минимальное количество фигур, необходимое для атаки на все поля на доске, включая занятые. ^[5]Для ладей требуется восемь; решение состоит в том, чтобы разместить их все в одном файле или ранге. Решения для остальных частей приведены ниже.

	а	б	с	д	Это	ж	г	час
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
	а	б	с	д	Это	ж	г	час

5 ферзей атакуют все поля

	а	б	с	д	Это	ж	г	час
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
	а	б	с	д	Это	ж	г	час

14 рыцарей атакуют все поля

Доминирование ферзей на главной диагонали шахматной доски любого размера можно показать эквивалентным задаче теории чисел по поиску множества Салема-Спенсера , набора чисел, в котором ни одно из чисел не является средним из двух других. Оптимальное размещение ферзей достигается, если оставить свободным набор полей, которые имеют одинаковую четность (все находятся в четных позициях или все в нечетных позициях по диагонали) и которые образуют набор Салема – Спенсера. ^[6]

Проблемы частичным с туром

Задачи такого рода требуют найти обход определенной шахматной фигуры, который посещает все клетки шахматной доски. Самая известная задача такого рода — Knight's Tour . Помимо коня, такие туры существуют для короля, ферзя и ладьи. Слоны не могут дойти до каждой клетки доски, поэтому задача для них ставится так, чтобы дойти до всех клеток одного цвета. ^[7]

Проблемы с обменом шахматами [ править ]

В шахматных задачах на перестановку белые фигуры меняются местами с черными фигурами. ^[8]Это делается с помощью обычных разрешенных ходов фигур во время игры, но поочередные ходы не требуются. Например, белый конь может ходить дважды подряд. Захват фигур не допускается. Две такие проблемы показаны ниже. В первом цель – поменять местами белых и черных коней. Во втором необходимо поменять местами слонов с дополнительным ограничением, чтобы фигуры противника не атаковали друг друга.

Загадка об обмене рыцарями

головоломка со сменой епископов

См. также [ править ]

Шахматная головоломка

Примечания [ править ]

^ Гик, стр.11
^ "Тур Independent Pieces!" . Личесс . Проверено 9 июля 2022 г.
^ «Mathrecreation: Математические шахматные головоломки» . матретворение . Проверено 9 июля 2022 г.
^ Гик, стр.98
^ Гик, стр.101.
^ Кокейн, Э.Дж.; Хедетниеми, С.Т. (1986), «О проблеме доминирования диагональных ферзей», Журнал комбинаторной теории , серия A, 42 (1): 137–139, doi : 10.1016/0097-3165(86)90012-9 , MR 0843468
^ Гик, стр. 87.
^ "Загадка обмена конями - Шахматные форумы" .

Ссылки [ править ]

Евгений Дж. Гик (1986). Шахматы и математика . Москва, издательство МИР и Лейпциг, издательство Урания. ISBN 978-3930640379 . (in German). Some chapters of the book are available online: Евгений Гик "Шахматы и математика" and as DJVU file (in Russian).

Внешние ссылки [ править ]

«Шахматы» Вайсштейна Эрика В. из MathWorld .
Проблемы расстановки шахматных фигур Джорджа Джеллисса (из журнала «Игры и головоломки»).
Задачи на шахматной доске Эда Пегга-младшего.

[1] Гик, стр.11

[2] "Тур Independent Pieces!" . Личесс . Проверено 9 июля 2022 г.

[3] «Mathrecreation: Математические шахматные головоломки» . матретворение . Проверено 9 июля 2022 г.

[4] Гик, стр.98

[5] Гик, стр.101.

[6] Кокейн, Э.Дж.; Хедетниеми, С.Т. (1986), «О проблеме доминирования диагональных ферзей», Журнал комбинаторной теории , серия A, 42 (1): 137–139, doi : 10.1016/0097-3165(86)90012-9 , MR 0843468

[7] Гик, стр. 87.

[8] "Загадка обмена конями - Шахматные форумы" .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]