♞ Можно ли обойти конем шахматную доску? ♟

Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу. Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию», датированную 1759 годом.

В терминах теории графов каждый маршрут коня, проходящий через все поля шахматной доски, соответствует гамильтонову пути (или циклу, если маршрут замкнутый) в графе, вершинами которого являются поля доски, и два поля соединены ребром, если с одного можно попасть на другое за один ход коня.
Для доски 8 × 8 количество всех замкнутых маршрутов коня (гамильтоновых циклов) без учёта направления обхода равно 13 267 364 410 532. Количество всех незамкнутых маршрутов (с учётом направления обхода) равно 19 591 828 170 979 904.

Некоторые методы решения задачи:
▪️ Метод Эйлера. Конь двигается по произвольному маршруту, пока не исчерпает все возможные ходы. Затем оставшиеся непройденными клетки добавляются в сделанный маршрут, после специальной перестановки его элементов.
▪️ Метод Вандермонда. Используется арифметический подход: маршрут коня на доске обозначается последовательностью дробей x/y, где x и y — это координаты клеток.
▪️ Правило Варнсдорфа. При обходе доски конь следует на то поле, с которого можно пойти на минимальное число ещё не пройденных полей.

Практическое применение задачи связано с теорией графов и поиском гамильтоновых путей. Методы задачи полезны в логистике, криптографии и 3D-графике. #математика #math #опыты #шахматы #алгоритмы #science #наука #видеоуроки

💡 Physics.Math.Code // @physics_lib