Математическая шахматная задача
Математическая шахматная задача — это математическая задача , сформулированная с использованием шахматной доски и шахматных фигур. Эти задачи относятся к развлекательной математике . Наиболее известными задачами такого рода являются головоломка о восьми ферзях и задача о путешествии коня , которые связаны с теорией графов и комбинаторикой . Многие известные математики изучали математические шахматные задачи, такие как Табит , Эйлер , Лежандр и Гаусс . [1] Помимо поиска решения конкретной задачи, математики обычно интересуются подсчетом общего числа возможных решений, поиском решений с определенными свойствами, а также обобщением задач на доски N×N или M×N.
Проблема независимости [ править ]
Проблема независимости (или незащищенность [ нужна ссылка ] ) — задача, в которой по заданному типу шахматных фигур (ферзя, ладьи, слона, коня или короля) необходимо найти максимальное число, которое можно разместить на шахматной доске так, чтобы ни одна из фигур не атаковала друг друга. Также необходимо найти фактическое расположение для этого максимального количества штук. Самая известная задача этого типа — головоломка с восемью ферзями . Проблемы расширяются, если задаться вопросом, сколько существует возможных решений. Дальнейшие обобщения применимы к платам NxN. [2] [3]
На шахматной доске 8×8 может быть 16 независимых королей, 8 независимых ферзей, 8 независимых ладей, 14 независимых слонов или 32 независимых коня. [4] Решения для королей, слонов, королев и коней показаны ниже. Чтобы получить 8 независимых ладей, достаточно расположить их на одной из главных диагоналей.
16 независимых королей |
8 независимых королев |
8 независимых ладей | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
14 независимых епископов |
32 независимых рыцаря | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Проблемы доминирования [ править ]
доминирования . (или покрытия ) Задача заключается в нахождении минимального количества фигур данного типа, которое можно разместить на шахматной доске, чтобы все свободные поля были атакованы хотя бы один раз Это частный случай задачи о вершинном покрытии . Минимальное количество доминирующих королей - 9, ферзей - 5, ладей - 8, слонов - 8, коней - 12. Чтобы получить 8 доминирующих ладей, достаточно разместить по одной на каждой вертикали. Решения для остальных частей представлены на схемах ниже.
9 доминирующих королей |
5 доминирующих королев | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
8 доминирующих слонов |
12 доминирующих рыцарей | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Проблемы доминирования также иногда формулируются как требование найти минимальное количество фигур, необходимое для атаки на все поля на доске, включая занятые. [5] Для ладей требуется восемь; решение состоит в том, чтобы разместить их все в одном файле или ранге. Решения для остальных частей приведены ниже.
12 королей атакуют все поля |
5 ферзей атакуют все поля | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
10 слонов атакуют все поля |
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 .
- Проблемы расстановки шахматных фигур Джорджа Джеллисса (из журнала «Игры и головоломки»).
- Задания на шахматной доске Эда Пегга-младшего.