Task #108. Обход доски конем

Задача: Постройте маршрут коня на доске размером 9?9, проходящий через каждую клетку доски ровно один раз.

В этой задаче ровно один тест, входных данных нет никаких. Программа должна вывести 81 строку, в каждой строке должна быть указана координата одной клетки, состоящая из строчной буквы латинского алфавита от a до i и цифры от 1 до 9. Каждые две соседние клетки должны быть соединены ходом коня. Каждая клетка доски должна встречаться ровно один раз.

Например, если бы требовалось построить маршрут коня на доске 4?5, то вывод программы мог бы быть таким:

a1, c2, d4, b5, a3, b1, d2, c4, a5, b3, c1, a2, b4, d5, c3, d1, b2, a4, c5, d3

Разбор

Это задача поиска гамильтонова пути в графе. Гамильтоновым циклом в графе называют цикл, проходящий через все вершины.
Построение гамильтонова цикла — сложная задача, в настоящее время неизвестно эффективного алгоритма его решения, но можно придумать переборное решение, сложность которого будет порядка O(n!).

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

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

При входе программы рекурсивно в функцию построения гамильтонова пути, построим список всех ребер, исходящих из данных вершин, выбросив те ребра, которые ведут в уже посещенные вершины. Этот список упорядочим по возрастанию такого параметра — сколько ходов можно сделать из данной клетки? То есть при дальнейшем переборе ребер будем сначала пытаться идти в те вершины, из которых возможно малое число ходов. Это ускорит перебор (так как перебираются сначала клетки с малым числом возможных продолжений), а также упростит задачу поиска пути в дальнейшем, так как мы сначала стараемся убрать клетки с малым числом допустимых ходов и оставить клетки, с большими возможностями для маневров.

Дополнительный материал

• Вики
• Algo List: Обход доски шахматным конем

Реализация

https://gist.github.com/unilecs/89865296eff5c7782c20c8ec7586c349

Play-test

https://repl.it/@unilecs/KnightMove2cpp

Источник: m.vk.com

Комментарии: