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