Обход шахматной доски конем
Back Home Up Next

Несколько иное воплощение абстрактной схемы перебора с возвратом можно применить к другой известной задаче об обходе конем шахматной доски размера n´n. Будем считать, что строки и столбцы доски пронумерованы соответственно сверху вниз и слева направо цифрами от 0 до n-1, а конь перемещается по доске согласно обычным шахматным правилам. Найти обход доски с конкретного поля - значит получить последовательность позиций перемещения коня такую, что каждое поле посещается им ровно один раз. Для доски 8´8 эта задача впервые была поставлена Л.Эйлером.

адача 4. Обход доски конем. На шахматной доске размера n´n в позиции (x, y) находится конь (см. рис.2). Составить рекурсивную программу-функцию, находящую методом перебора с возвратом обход доски конем, если он существует. При отсутствии обхода должно быть выдано соответствующее сообщение.

Решение. На рис.2 приведен фрагмент доски. Конь K стоит в позиции (x, y). Клетки с цифрами вокруг K - это поля, на которые конь может переместиться из (x, y) (0 £ x, y £ n-1) за один ход. Множество этих полей обозначим через M(x, y). Для фиксированного поля (x, y) множество M(x, y) может содержать от двух до восьми элементов. Попробуем упорядочить эти множества. Рассмотрим вспомогательную матрицу приращений:

                                                  (1)

Для поля (x, y) построим последовательность полей

(x + D0,k, y + D1,k)     (k = 0, 1, ..., 7)                                                      (2)

и отберем из них те, для которых

0 £ x + D0,k £ n-1   и  0 £ y + D1,k £ n-1   (k = 0, 1, ..., 7).                                 (3)

Рис. 2. Схема упорядочивания множества возможных ходов коня

Именно эти поля и составляют множество M(x, y). Каждому элементу (a, b)ÎM(x, y) припишем номер k столбца D, элементы которого в соответствии с (2)-(3) задают приращения по осям для перемещений коня из (x, y) в (a, b). Таким образом, возможные ходы коня из (x, y) упорядочены по полученным ими номерам. На рис.2 эти номера проставлены в соответствующих клетках. Заметим, что иные варианты матрицы D, а всего их 8!=40320, дают иные способы упорядочивания M(x, y).

Решая поставленную задачу с помощью общей схемы 3 перебора с возвратом, мы должны последовательно формировать вектор длины n2. Нам удобней строить не вектор, а матрицу размером n´n, отмечая в её клетках номера ходов коня от единицы и до n2. Делать это можно с помощью функций main() и Ktour().

Параметры головной функции main(n, x, y) - это размер доски (n) и начальная точка (x, y), с которой начинаются перемещения коня. В main() инициируется нулями доска-матрица H размером n´n и осуществляется первый ход. Далее реализуется обращение к рекурсивной функции Ktour() и после вычислений выводится матрица H с полным туром коня или сообщение об отсутствии решений.

Параметры рекурсивной функции Ktour(n, x, y, H, boo, j) - это размер доски (n), точка (x, y), с которой осуществляется очередной ход коня, доска (H), глубина рекурсивных обращений (j) и вспомогательная переменная boo. Функция Ktour() возвращает текущую матрицу H и величину boo, которая равна нулю или единице в зависимости от того, удалось или нет осуществить ход конем в текущем рекурсивном обращении.

В каждом рекурсивном вызове глубины j делается попытка разместить коня в очередное j-е поле доски. Позицию, из которой коня продвинуть дальше нельзя, назовем тупиком. Попадание в тупик приводит к завершению текущего рекурсивного вызова, то есть к возврату к предыдущему полю и продолжению работы с ним. Иных случаев завершения рекурсивных вызовов не существует. Поэтому базой рекурсии, как и в задаче 1, мы должны считать совокупность всех тупиков. Элементы базы заранее до вычислений неизвестны. Если в очередном рекурсивном вызове продвинуть коня удается (boo=1), то осуществляется переход к следующему рекурсивному вызову. Если удается продвинуть коня на последнюю из незанятых клеток Н, то осуществляются последовательные возвраты на первый рекурсивный уровень (j=0) и возвращается решение (H). Если осуществлен возврат на первый рекурсивный уровень при незаполненной доске и на этом уровне уже испытаны все допустимые ходы, то выдается сообщение об отсутствии решений.

Замечание. Попытки решать задачу 2 при n ³ 8 с помощью программ main() и Ktour(), реализованных на языке программирования Mathcad, наталкиваются на сложности, связанные с недостатком памяти или продолжительностью вычислений. Не спасает и реализация этих программ на каких-либо языках программирования компилирующего типа. Незначительное ускорение вычислений может обеспечить переход к нерекурсивному варианту функции Ktour(). Поэтому для решения задачи 2 даже для обычной шахматной доски (n=8) требуются какие-либо иные подходы. Об одном из них и пойдет речь в следующем пункте.

Home Содержание Схемы ООД Доска объявлений Поиск