Задачи о ходе коня

Автор: admin от 2022-06-7 16:06:28
Задачи о ходе коня

Необозримое море математических задач и головоломок возникает при появлении на доске шахматных фигур. Среди задач, связанных с их маршрутами, самой знаменитой является задача о ходе коня. Обойти конем все поля шахматной доски, занимая каждое из них ровно один раз.
Особая популярность этой головоломки объясняется тем, что в XVIII и XIX веках ею увлекались многие крупные математики, в том числе великий Леонард Эйлер, посвятивший ей большой мемуар "Решение одного любопытного вопроса, который, кажется, не поддается никакому исследованию". Хотя задача была известна и до Эйлера, именно он впервые обратил внимание на ее математическую сущность, и поэтому она часто связывается с его именем.
Значительно сложнее проблема, состоящая не в нахождении какого-то конкретного маршрута, а в поиске всех маршрутов коня и подсчете их числа. Увы, эта задача не решена и до сих пор, и, похоже, шансов на успех немного (что, видимо, и имел в виду Эйлер, когда давал название своей работе). Доказано только, что число искомых маршрутов превосходит 30 миллионов.
Придуманы различные способы для нахождения тех или иных маршрутов коня, но самым простым и эффективным до сих пор остается правило Варнсдорфа, придуманное полтора века назад: на каждом ходу конь должен занимать поле, с которого может сделать наименьшее число прыжков на еще не пройденные поля. В результате конь благополучно завершит путешествие по всем 64 полям доски.
Многие составители маршрутов коня стремились внести в свое занятие, насколько это возможно, эстетический элемент и достигли весьма любопытных результатов. Так называемый раздельный маршрут заключается в обходе одной половины доски, его симметричном дублировании и соединении обоих путей вместе.
Задачи о ходе коня

Если говорить о графиках маршрута коня, то придумано множество необычных решений, изображающих различные буквы и знаки (построен, например, маршрут коня, посвященный Наполеону). Вот два достопримечательных примера такого рода.
Задачи о ходе коня

График этого маршрута напоминает вазу, а следующий подобен цветку, части которого расположены в высшей степени симметрично.
Задачи о ходе коня

Непростые математические задачи возникают при поисках маршрутов коня на различных нестандартных досках. Доказано, например, что любую прямоугольную доску, обе стороны которой больше пяти, конь тоже в состоянии обойти с посещением всех полей по одному разу.
Задача о коне Аттилы
На доске находятся две фигуры - белый конь и черный король. Некоторые поля объявляются "горящими". Конь должен дойти до неприятельского короля, повергнуть его и вернуться на исходное место. При этом ему запрещено занимать как "горящие" поля, так и поля, уже пройденные.
"Трава не растет там, где ступил мой конь!" - похвалялся вождь гуннов Аттила, намекая, что предводительствуемые им полчища уничтожают все живое на своем пути.
Задачи о ходе коня

Здесь конь Аттилы расположен на g4, а неприятельский король на b3, горящие поля заштрихованы.
Соединяя отрезками все пары доступных коню полей, между которыми возможен его ход, получаем так называемый граф коня для данной задачи (полям доски соответствуют вершины этого графа). В результате дело сводится к нахождению в графе пути, не содержащего ни одной вершины более одного раза и, кроме того, проходящего через обе выделенные.
Методы решения подобных задач, называемых лабиринтными, хорошо известны. Впрочем, для коня Аттилы искомый путь нетрудно найти и непосредственно, он содержит 18 ходов: Kg4-f6-e8-g7-e6-f8-g6-е7-с6-а5:b3-d2-b1-a3-b5-d6-f7-h6-g4. Для достижения цели коню пришлось побывать на 18 полях из 35, не сожженных в начале сражения.

Карпов А., Гик Е. "Все о шахматах"
Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Комментарии:

Оставить комментарий