Логика, Алгоритмы | Олег Брагинский, Рамиль Мамедов, Владислав Иванов
Настольные игры – прекрасный поставщик задач и примерный образец алгоритмов. Основатель «Школы траблшутеров» Олег Брагинский, ученики Рамиль Мамедов и Владислав Иванов решают задачу однократного прохождения всех позиций шахматной доски одним конём.
Из настолок в математику пришла задача о прохождении всего поля конём без повторения клеток. Первое упоминание о найденном решении в XVIII веке сообщил Леонард Эйлер. В то же время Александр Вандермонд предложил свой метод разгадки, сводимый к арифметическому тождеству.
Наиболее интересными подходами «старой» школы можно назвать метод Эйлера, заключающийся в произвольном движении с дальнейшим встраиванием цепочки ходов, соотношения координат ячеек Вандермонда и правило Варнсдорфа с выбором пути через минимизацию вариантов ходов.
Также стоит отметить достижение российского шахматиста Карла Яниша, сумевшего построить такой маршрут коня, который создаёт полумагический квадрат для доски 8х8. А советский чемпион Москвы 1929 года Василий Панов даже сумел закодировать путь в мнемоническое стихотворение.
С появлением теории графов найти способы прохождения поля оказалось ещё проще. Электронно-вычислительные машины сократили процесс до секунд. Хотя и количество решений при учёте направления движения доски 8х8 достигает 19’591’828’170’979’904 (девятнадцати квадриллионов).
Для поиска решения составим несложный, а затем более предусмотрительный алгоритм. Стартовая позиция фигуры неважна – станем следить только за движением.
Начиная с любой клетки делаем начальный ход, далее определяем конечность второго. Оцениваем возможности следующих продвижений и в случае отсутствия возможностей продвижения вперёд – отменяем сделанный шаг, возвращаясь на предыдущую клетку.
Алгоритм получается следующим:
Теперь добавим к нему счётчики ходов и возвратов:
Для демонстрации работы алгоритма воспользуемся языком программирования Python. Первым делом введём функцию проверки легитимности хода: находится ли в пределах доски и ступали ли мы уже на потенциальную клетку?
Следом напишем функцию поиска решения с перебором ходов из текущей позиции. Если решение найти невозможно, возвращаем «False»:
Третьим действием формализуем задачу: задаём размер доски, начальную позицию коня, встраиваем перемещения в системе координат: (-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1). Добавляем счётчики ходов и возвратов:
Последним шагом рисуем доску, размещаем на ней номера ходов и значения счётчиков:
Выставляем стартовую позицию – клетку А1 и программа отрисовывает найденный вариант:
Программа отслеживает ходы, окрашивая в оранжевый цвет, и все откаты назад (зелёный). Причём количество возвратов для каждой клетки учитывается отдельно. Например, для совершения хода №29 откатов не потребовалось, а для хода №63 алгоритм перебрал 160 тысяч вариантов.
Однако при попытке старта с другой позиции, например, D4, подобный жадный алгоритм с рекурсией упирается в глубину вызова, что приводит к бесконечному поиску решения и его доработка через цикл может оказаться бессмысленной.
Пробуем оптимизировать подход, применив вышеописанное правило Варнсдорфа. Обновлённая схема станет выглядеть следующим образом:
В код добавляем несколько блоков, модифицируем функцию для решения задачи методом Варнсдорфа:
Корректируем и функцию на перебор ходов с целью нахождения ограничивающего:
Теперь при выставлении любой начальной позиции алгоритм работает быстро и исправно. Также мы изменили значение зелёных чисел на доске – показывают минимальное число доступных следующих ходов. Проверим на С7:
Не забудем и про D4, «сломавшей» предыдущую итерацию алгоритма:
В книге Евгения Яковлевича Гика «Шахматы и математика» (1983) было приведено доказательство ограничения правила Варнсдорфа: не все возможные ходы с одинаковыми ограничениями являются равноценными. Некоторые способны завести коня в тупик. Однако шансы крайне малы.
Интересный факт: данная задача попадается в сборниках по математике и на школьных олимпиадах 3-5 классов, где правильным ответом считается отсутствие решения, так как стартовая клетка коня не соответствует цвету конечной, поэтому невозможно пройти поле без повторов.