Задача о ходе коня¶

Для иллюстрирования второго распространённого алгоритма для графов мы возьмём другую классическую задачу: “о ходе коня”. Она разыгрывается на шахматной доске всего одной фигурой - конём. Целью головоломки является поиск такой последовательности ходов (маршрута), чтобы конь посетил каждую клетку доски ровно один раз. Эта задача очаровывает шахматных игроков, математиков и информатиков уже в течение многих лет. Верхний предел количества возможных маршрутов для шахматной доски 8х8 равен \(1.305 \times 10^{35}\). Однако, тупиковых вариантов неизмеримо больше. Очевидно, что задача из тех, которые требуют человеческого разума, компьютерных мощностей или и того, и другого вместе.

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

• Представим в виде графа осуществимые ходы коня по доске.
• Используем алгоритм для поиска в графе пути длиной \(rows \times columns - 1\), где каждая вершина будет посещена ровно один раз.