Ход конём: конь, который перепрыгнул века (Knight's tour)
В 1759 году Леонард Эйлер, один из величайших умов Просвещения, опубликовал работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому известному методу». Речь шла о задаче, знакомой каждому шахматисту: как пройти конём по всем 64 клеткам доски, не посетив ни одну дважды?
Со временем задача неоднократно обобщалась. Например, доска не обязательно содержит 64 клетки — это может быть произвольная прямоугольная доска, разделённая на m × n одинаковых клеток.
Частные решения этой задачи нашли Леонард Эйлер, Александр Вандермонд и другие. Конечно же, решали и известные шахматисты, например, Карл Андреевич Яниш и Василий Николаевич Панов.
В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня. Для доски 8 × 8 количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532. Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.
Задача допускает разные математические модели и алгоритмы, компьютерные программы, решается и шахматными автоматами.
В 1823 году некто Варнсдорф издал брошюру «Простейшее и наиболее общее решение задачи о ходе коня», в которой предложил алгоритм для обхода доски размером 8 × 8.
«На каждом ходу ставь коня на такое поле, из которого можно совершить наименьшее число ходов на ещё не пройденные поля. Если таких полей несколько, разрешается выбирать любое из них.»
На практике это правило легко позволяет строить обходы доски. Тем не менее, долгое время не было известно, справедливо ли оно. Опровержение правила Варнсдорфа приведено в нескольких работах. Для любого исходного поля доски существуют контрпримеры, построенные с помощью компьютера. Иными словами, с какого бы поля конь ни начал движение, следуя правилу Варнсдорфа, его можно завести в тупик до полного обхода доски.
Тем не менее, попробуйте применить это правило. Надо полагать, что клетки каким-нибудь образом занумерованы (например, так, как на рисунке). Клетки, в которых конь уже побывал, надо перечёркивать. Для определённости алгоритма, надо выбирать ту клетку, которая имеет наименьший номер.
Эта задача встречается в некоторых сборниках старинных и занимательных задач, например:
- Балк М. Б., Балк Г. Д. Математика после уроков. Пособие для учителей. — М.: «Просвещение», 1971. — 462 с.
- Гик Е. Я. Шахматы и математика. — М.: Наука, 1983. — 176 с.
- Игнатьев Е. И. В царствие смекалки. — М: Наука, 1978. — 192 с.
