Ответ на 9-ю задачу челленджа!
Ответ на 9-ю задачу челленджа! Можно ли обойти конем всю шахматную доску, побывав на каждой клетке ровно один раз? Ответ: Да, это возможно. Эта знаменитая задача называется «обход конём». Она известна ещё со Средних веков и до сих пор интересна не только шахматистам, но и математикам, и программистам. Самое удивительное, что правильный маршрут не один. Их существует огромное количество — триллионы! Существует два вида решений этой задачи. 🔹 Замкнутый маршрут — конь заканчивает путь на клетке, с которой одним ходом может вернуться в начало. Такой маршрут образует замкнутый цикл, поэтому стартовой можно считать любую клетку этого пути. 🔹 Открытый маршрут — конь заканчивает путь на клетке, из которой уже нельзя одним ходом попасть в исходную точку. При таком типе обхода конь не сможет пройти тот же маршрут, если изменить его начальную позицию. Почему маршрутов так много? Разные стартовые клетки дают разные маршруты. Но даже если зафиксировать одну конкретную стартовую клетку, количество возможных обходов всё равно остаётся астрономическим. Интересно, что для построения такого маршрута часто используют правило Варнсдорфа. Его идея очень проста: на каждом ходе выбирать ту клетку, из которой в дальнейшем будет меньше всего возможных продолжений. Звучит немного нелогично, но именно такой подход помогает не загнать коня в тупик и значительно повышает шансы успешно обойти всю доску👆🏻 Именно поэтому задача оказалась настолько интересной для математиков. Сегодня она связана с теорией графов, а похожие алгоритмы применяются в информатике, логистике и при разработке программ. Удалось ли вам пройти хотя бы большую часть пути, не загнав коня в тупик?🤓 #30днейумныхрешений