Question

Можно ли обойти шахматным конём всю шахматную доску так, чтобы конь побывал на каждой клетке по одному разу и вернулся на начальную клетку? А доску 8Х8

Answer 1

Нет нельзя так делать

Answer 2

Да, такой маршрут существует и называется "Ход коня". Чтобы конь обошел всю шахматную доску размером 8x8, посетив каждую клетку ровно один раз и вернулся на начальную клетку, нужно выполнить следующую последовательность ходов:

1. Начать из любой клетки на доске (начальная клетка).
2. Перемещайтесь согласно правилам хода коня до тех пор, пока не посетите все клетки на доске, кроме последней.
3. Для последней клетки выберите ход таким образом, чтобы вы вернулись в начальную клетку.

Идеальный маршрут коня для доски 8x8:

1 -> 18 -> 33 -> 44 -> 59 -> 42 -> 27 -> 8 -> 1 -> 10 -> 25 -> 40 -> 57 -> 62 -> 51 -> 36 -> 17 -> 2 -> 9 -> 24 -> 39 -> 58 -> 63 -> 52 -> 37 -> 16 -> 3 -> 12 -> 23 -> 38 -> 61 -> 56 -> 41 -> 26 -> 7 -> 4 -> 15 -> 22 -> 43 -> 60 -> 53 -> 64 -> 47 -> 34 -> 19 -> 6 -> 13 -> 20 -> 35 -> 50 -> 55 -> 46 -> 31 -> 14 -> 5 -> 32 -> 49 -> 54 -> 45 -> 30 -> 21 -> 28 -> 11 -> 29 -> 48

Последний ход 48 -> 1 завершает маршрут, вернув коня на начальную клетку (1).

Такой маршрут можно обнаружить, применив специальные алгоритмы для задач коммивояжёра или использовав компьютерные программы для решения задач охвата (coverage problems).