В шахматной математике популярна задача об обходе конем всех клеток шахматной доски 8 x 8,которой с успехом занимался Леонард Эйлер и, возможно, первым решил ее. В письме к Х. Гольдбаху он сообщал: "…Воспоминание о предложенной когда-то мне задаче послужило для меня недавно поводом к некоторым тонким изысканиям, в которых обыкновенный анализ, как кажется, не имеет никакого применения… Я нашел, наконец, ясный способ находить сколько угодно решений (число их, однако, не бесконечно), не делая проб. Подобное решение представлено на рисунке" (Цитируется по книге: Игнатьев Е. И. В царстве смекалки. - М.: Наука, 1987, с. 81. ).
(Иллюстрация 1)
Письмо датировано 26 апреля 1757 года. Так что можно говорить о 250-летнем юбилее этой задачи, интерес к которой не остывает до сих пор. Задача неоднократно обобщалась - например, разработаны универсальные алгоритмы обходов конем квадратных досок размером n x n, прямоугольных досок размером n x m (см. "Наука и жизнь" № 1, 2003 г.).
В этой статье рассмотрим вопрос об обходе шахматным конем фигурных досок определенного класса. Фигуру, изображенную на рисунке, назовем ступенчатым квадратом. Порядок или размер его определим по числу ступенек на каждой стороне. Например, на рисунке приведен ступенчатый квадрат 8-го порядка.
(Иллюстрация 2)
Оказывается, все клетки ступенчатого квадрата любого порядка можно обойти шахматным конем, побывав в каждой клетке только один раз. На рисунках показаны замкнутые маршруты коня для ступенчатых квадратов 2-го, 3-го и 4-го порядков.
(Иллюстрация 3)
Доказательство этого факта состоит из следующих шагов:
1. Строят замкнутые обходы для пяти базовых фигур. К ним относятся ступенчатые квадраты 2-го, 3-го, 4-го порядков и еще двух фигур, изображенных на рисунке.
2. Обосновывают возможность разбиения ступенчатого квадрата любого порядка на базовые фигуры.
3. Показывают возможность объединения обходов базовых фигур в один замкнутый маршрут.
Построим замкнутый маршрут шахматного коня по всем клеткам ступенчатого квадрата 8-го порядка. Для этого разобьем его на базовые фигуры и для каждой из них построим замкнутые обходы.
(Иллюстрация 4)
Остается объединить эти маршруты в один. Заметим, что данный ступенчатый квадрат разбит на базовые фигуры двух видов. На рисунке вверху показаны всевозможные пары соседних базовых фигур предложенного разбиения ступенчатого квадрата. В каждой паре выделены красным цветом два звена маршрута, по одному в каждой базовой фигуре. Если эти красные звенья перекинуть как "мостик" на соседнюю фигуру в той же паре, получим замкнутый обход в объединенной паре. Таким образом можно объединить обходы любых двух базовых фигур разбиения в один замкнутый маршрут.
(Иллюстрация 5)
Конечно, нужна стратегия объединения обходов фигур разбиения. В качестве одной из них можно предложить объединение соседних фигур "змейкой", изображенной на рисунке в правой колонке. В результате такого объединения получим замкнутый маршрут шахматного коня по всем клеткам ступенчатого квадрата 8-го порядка.
(Иллюстрация 6)
Подобным методом можно построить маршрут коня для ступенчатых квадратов порядка n = 3k + 2. Заметим, что предложенный метод почти универсален. Различия возникают при разбиении ступенчатого квадрата на базовые фигуры, а это зависит от его порядка n. Как разбивать ступенчатые квадраты порядка n = 3k и n = 3k + 1 на базовые фигуры, показано на следующих рисунках (см. с. 121, 122, 123).
(Иллюстрация 7)
Далее строят обходы для каждой фигуры разбиения (а они все базовые) и "змеевидной" стратегией перекидывания мостиков объединяют в один замкнутый маршрут шахматного коня. Руководствуясь этим алгоритмом, можно построить обходы конем ступенчатых квадратов порядка n = 3k и n = 3k + 1.
(Иллюстрация 8)
Это значит, что рассмотренным методом можно построить обход конем клеток ступенчатого квадрата любого порядка. Но на этом задача Эйлера не исчерпала себя. Любознательный читатель может изучить возможность обхода конем клеток, например, ступенчатого прямоугольника. Но это уже другая задача.
(Иллюстрация 9)
