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

1. Дано

• Объект: Шахматный конь.
• Поле начала: Левый нижний угол (обычно обозначается как $a1$).
• Поле окончания: Правый верхний угол (обычно обозначается как $h8$).
• Требование: Конь должен посетить все поля доски по одному разу.

2. Найти

Возможно ли совершить полный обход доски $8 \times 8$ (64 поля) за 63 хода, начиная с $a1$ и заканчивая на $h8$?

3. Решение

Шахматная доска имеет $N=8 \times 8 = 64$ поля. Полный обход (если он существует) называется Гамильтоновым циклом (если начальное и конечное поле совпадают) или Гамильтоновым путём (если начальное и конечное поля различны). В нашем случае мы ищем Гамильтонов путь.

Ключевой инструмент для анализа этой задачи — раскраска полей.

Шаг 1: Анализ раскраски полей

Шахматная доска традиционно раскрашена в два цвета: черные и белые поля.

1. Общее количество полей: 64.
2. Количество полей каждого цвета: $64 / 2 = 32$ белых поля и 32 черных поля.

Шаг 2: Анализ хода коня

Конь всегда ходит буквой "Г" (две клетки в одном направлении, затем одна в перпендикулярном).

Важнейшее свойство хода коня: При каждом ходе конь всегда перемещается с поля одного цвета на поле другого цвета. *...