Задача о ходе коня
Маршрут коня — это последовательность ходов коня, которая проходит через каждое поле шахматной доски ровно один раз. Это одна из старейших головоломок занимательной математики: маршрут по половине доски встречается в индийской поэме IX века, а Леонард Эйлер изучал эту задачу в 1759 году.
Старинная головоломка
В сочинении «Кавьяланкара», написанном индийским поэтом Рудратой в IX веке, стих расположен на половине шахматной доски так, что его можно прочитать вдоль пути коня. Леонард Эйлер написал первое математическое исследование маршрута коня в 1759 году и описал в нём способы строить маршруты и превращать их в замкнутые.
Путь в графе
Представьте каждое поле точкой, а каждый ход коня — линией между двумя точками. Тогда маршрут коня — это путь, проходящий через каждую точку ровно один раз; математики называют его гамильтоновым путём, а замкнутый маршрут — гамильтоновым циклом. В большинстве сетей такой путь найти очень трудно. Сеть коня щедра: маршрутов в ней так много, что хорошее правило быстро находит один из них.
Правило Варнсдорфа
Х. К. фон Варнсдорф описал своё правило в 1823 году: всегда прыгать на поле, с которого остаётся меньше всего дальнейших ходов. У полей вдоль края мало соседей, поэтому правило посещает их рано, а не оставляет отрезанными. Когда у двух полей это число одинаково, нужно выбирать, и неудачный выбор всё равно может завести коня в тупик. В приложении золотые числа отмечают поля, которые выбрало бы правило.
Поиск с возвратом
«Решить» следует порядку Варнсдорфа, но не доверяет ему слепо. Поиск идёт в глубину: как только до какого-нибудь непосещённого поля уже нельзя добраться, эта ветвь отбрасывается и пробуется следующий ход. На досках до 10×10 маршрут обычно находится сразу. Если ваш собственный путь запер коня, «Решить» сначала отступает на несколько ходов.
Цвета и замкнутые маршруты
Каждый ход коня меняет цвет поля. На нечётной доске, например 5×5, полей углового цвета на одно больше, чем другого, поэтому маршрут должен начинаться и заканчиваться на угловом цвете. Замкнутый маршрут там невозможен, потому что в цикле, где цвета чередуются, полей каждого цвета поровну. На чётных досках замкнутые маршруты существуют начиная с 6×6.
Попробуйте в PictorX
Откройте «Ход коня» и щёлкните поле, чтобы начать. Подсвеченные поля — это допустимые прыжки, золотое число — выбор Варнсдорфа, а доска хранит порядок ваших ходов. «Размер» задаёт доску от 5×5 до 10×10, флажок «Замкнутый маршрут» просит «Решить» найти петлю, а «Отменить» возвращает любой ход. Сохраните готовый путь в PNG.
Часто задаваемые вопросы
Кто первым изучил маршрут коня?
Маршруты были известны задолго до того, как их начали изучать математически. Леонард Эйлер написал первое математическое исследование в 1759 году, а Варнсдорф предложил своё правило в 1823 году.
Есть ли маршрут на любой доске?
На квадратных досках начиная с 5×5 есть открытые маршруты, а на чётных начиная с 6×6 — ещё и замкнутые. На досках 2×2, 3×3 и 4×4 маршрута нет вовсе.
Сколько маршрутов на шахматной доске?
Существует 26 534 728 821 064 замкнутых маршрута, если маршрут и тот же маршрут, пройденный в обратном порядке, считать по отдельности. Число открытых маршрутов — около 19,6 квадриллиона.
Загружает ли PictorX что-нибудь?
Нет. Доска рисуется на холсте в браузере. Кнопка «Сохранить» скачивает PNG, а кнопка «Редактировать» открывает это изображение в редакторе PictorX.
Сопутствующие инструменты
Ход коня
Проведите шахматного коня по всем полям доски, побывав на каждом ровно один раз. Играйте сами с подсказками Варнсдорфа или смотрите, как «Решить» завершает открытый или замкнутый маршрут. Сохраните путь в PNG.
Восемь ферзей
Расставьте восемь ферзей на шахматной доске так, чтобы ни один не бил другого. Попробуйте сами, посмотрите, как поиск с возвратом шаг за шагом находит решение, и переберите все 92 решения.
Задача о восьми ферзях
История и математика задачи о восьми ферзях: Макс Беццель и Гаусс, 92 решения в 12 семействах, задача об n ферзях и поиск с возвратом.
Ханойская башня
Перенесите в браузере башню из дисков между тремя стержнями. По одному диску, никогда больший на меньший. Кратчайшее решение — 2ⁿ − 1 ходов.
Ханойская башня
Ханойская башня: три стержня, по одному диску, и никогда больший на меньший. Кратчайшее решение — 2ⁿ−1 ходов. Эдуард Люка представил головоломку в 1883 году.
Муравей Лэнгтона
Запустите муравья Лэнгтона в браузере. Посмотрите на симметрию, хаос и шоссе с циклом в 104 шага, а затем попробуйте многоцветные правила, нескольких муравьёв, шестиугольную сетку и турмитов.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать «Ход коня»