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

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

Рассмотрим в качестве примера следующий маршрут:

Сначала попытаемся из незамкнутого маршрута сделать замкнутый. Для этого рассмотрим, куда можно пойти с полей 1 и 60. С поля 1 можно пойти на поля 2, 32 и 52, а с 60 — на 29, 51 и 59. В этих двух наборах есть поля, различающиеся на единицу, а именно — 51 и 52. Благодаря этому можно сделать маршрут замкнутым, обратив его часть. Для этого перенумеруем поля с 52 по 60 в обратном порядке. После этого у нас получается замкнутый маршрут:

Теперь можно включить в маршрут некоторые из непройденных клеток. Так как наш маршрут замкнутый, то его можно разорвать в произвольном месте и к одному из концов прицепить подходящую цепочку из непройденных клеток. Например, если разорвать цепочку в клетке 51 (перенумеровав клетки и сделав её последней, а 52 — первой), то сможем удлинить нашу цепочку на клетки a, b и d, которые станут клетками 61, 62 и 63.

Вандермонд попытался свести задачу к арифметической. Для этого он обозначал маршрут коня по доске в виде последовательности дробей x/y, где x и y — координаты поля на доске. Очевидно, что в последовательности дробей, соответствующей ходам коня, разность числителей двух соседних дробей может быть только 1 или 2, при том, что разность их знаменателей составляет соответственно 2 или 1. Кроме того, числитель и знаменатель не могут быть меньше 1 и больше 8.

Его метод нахождения подходящей последовательности аналогичен методу Эйлера, но позволяет находить маршруты коня только для досок чётной размерности.

Правило Варнсдорфа, являющееся разновидностью жадного алгоритма для отыскания маршрута коня, формулируется так:

При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей. Если таких полей несколько, то можно пойти на любое из них.

Долгое время считалось, что правило Варнсдорфа работает безукоризненно. Позднее с помощью компьютеров была установлена неточность во второй его части: если существует несколько подходящих полей, то не все они равноценны, и произвольный выбор поля может завести коня в тупик. Однако на практике вероятность попадания в тупик невелика даже при вольном пользовании второй частью правила Варнсдорфа.[4]

Маршрут коня, найденный К. Я. Янишем, образует полумагический квадрат, а при повороте доски на 180° первая половина маршрута (номера с 1 до 32) переходит во вторую (номера с 33 по 64). Маршрута же, представляющего собой настоящий магический квадрат, не существует для доски 8 × 8[5].

Маршрут, якобы найденный шахматным автоматом «Турок»

Шахматный автомат «Турок» демонстрировал замкнутый маршрут коня, изображенный на диаграмме справа.

Обойти конём все шахматные клетки по одному разу, к тому же сделать это «вслепую», начав или закончив на любой клетке по желанию «зрителя», можно следуя стихотворению:[6]

Первые буквы задают координаты ходов:

Алеет Осень = А1; Ценными Дарами = С2; и т. д.

В каждую строфу вставлена подсказка, помогающая не перепутать последовательность строф: ещё ОДИН, ДВА вечера, достаются ТРЁМ и т. д.

Количество замкнутых маршрутов с учётом направления в два раза больше. Замкнутые маршруты существуют на досках ${\displaystyle n\times n}$ для всех чётных ${\displaystyle n\geqslant 6}$ (последовательность A001230 в OEIS).

Для неквадратных досок незамкнутый обход конём существует только при выполнении следующих условий: если одна сторона доски равна 3, то другая должна быть либо 4, либо не меньше 7; если же обе стороны больше 3, то обход коня возможен на всех досках, кроме 4 × 4. В частности, незамкнутые маршруты существуют на квадратных досках ${\displaystyle n\times n}$ для всех ${\displaystyle n\geqslant 5}$.[7] Количество незамкнутых маршрутов на досках ${\displaystyle n\times n}$ образуют последовательность A165134 в OEIS.