КИРИЛЛ ТКАЧЕНКО, инженер 1-й категории, ФГАОУ ВО «Севастопольский государственный университет», tkachenkokirillstanislavovich@gmail.com

Простейший рекурсивный алгоритм
с возвратом и эвристикой решения задачи о ходе коня

Рассматривается реализация рекурсивного алгоритма с возвратом. Решается задача о ходе коня при использовании эвристики по Варнсдорфу для сокращения перебора. Программа реализовывается на школьном алгоритмическом языке, приводятся полный исходный текст и результаты работы

Изучение и совершенствование программирования, возможно, целесообразно производить на решении классических задач, для которых программная реализация имеет умеренную сложность.

Одной из таких задач является классическая задача о ходе коня [1], которая сводится к построению маршрута коня на шахматной доске, покрывающего все клетки доски. Для нее известны многочисленные программные реализации наПаскале [1] и подобным ему языкам, хрестоматийные программные реализации [2] и на языке 1С [3]. Для начального обучения программированию подходит школьный алгоритмический язык.

Целью публикации является разработка программной реализации на школьном алгоритмическом языке рекурсивного алгоритма с возвратом для решения классической задачи о ходе коня на шахматной доске с использованием эвристики поВарнсдорфу для сокращения перебора.

В целочисленных переменных N находится размер стороны шахматной доски, NN – количество клеток шахматной доски, Ndydx – наибольшее возможное число ходов из одной клетки для коня:

цел N = 8
цел NN
цел Ndydx = 8

В одномерных целочисленных массивах dy и dx хранятся приращения координаты для возможного хода коня из конкретной клетки шахматной доски:

цел таб dy[1:Ndydx]
цел таб dx[1:Ndydx]

Сама шахматная доска располагается в двумерном целочисленном массиве доска, на каждой клетке массива находится номер хода коня при посещении клетки:

цел таб доска[1:N, 1:N]

Целочисленные переменные кодСимволаA1 и лучшийВесНач хранят соответственно код символа «a» минус 1 и лучший начальный вес для эвристики:

цел кодСимволаA1
цел лучшийВесНач

Головной алгоритм выполняет инициализацию, после устанавливает на поле a1 коня:

алг SAMAG
нач
  Инициализация
  доска[1, 1] := 1;

Если из поля a1 возможно решение, то заполненная перемещениями коня шахматная доска печатается, иначе решений нет:

  если Решить(2, 1, 1)
    то
      ПечатьДоски;
    иначе
      вывод "Нет решений.", нс;
  все
кон

Алгоритм Инициализация производит установку начальных значений переменных. Целочисленные переменные у и x – счетчики циклов:

алг Инициализация
нач
  цел y, x;

В целочисленную переменную NN помещается количество клеток шахматной доски, в кодСимволаA1 – код символа «a» минус 1:

  NN := N * N;
  кодСимволаA1 := код("a") - 1;

Заполняются приращения координаты dy:

  dy[1] := 2;
  dy[2] := 1;
  dy[3] := -1;
  dy[4] := -2;
  dy[5] := -2;
  dy[6] := -1;
  dy[7] := 1;
  dy[8] := 2;

Заполняются приращения координаты dx:

  dx[1] := 1;
  dx[2] := 2;
  dx[3] := 2;
  dx[4] := 1;
  dx[5] := -1;
  dx[6] := -2;
  dx[7] := -2;
  dx[8] := -1;

Лучший начальный вес полагается равным (Ndydx+1)²:

  лучшийВесНач := (Ndydx + 1) * (Ndydx + 1);

Конь вначале не посетил ни одной клетки шахматной доски:

  нц для y от 1 до N
    нц для x от 1 до N
      доска[y, x] := 0;
    кц
  кц
кон

Алгоритм ПечатьДоски выводит на устройство вывода шахматную доску. Целочисленные переменные y, x – счетчики циклов:

алг ПечатьДоски
нач
  цел y, x;

Сообщаются по каждой горизонтали соответствующие клетки шахматной доски:

  нц для y от N до 1 шаг -1
    вывод y, " ";
    нц для x от 1 до N
      вывод доска[y, x]:4;
    кц
    вывод нс;
  кц

Затем отображаются номера вертикалей:

  вывод "  ";
  нц для x от 1 до N
    вывод "   ", символ(кодСимволаA1 + x);
  кц
  вывод нс;
кон

Алгоритм МожноХодить возвращает «да», если клетка с целочисленными координатами y и x принадлежит шахматной доске и на нее конь не ходил, и «нет», в противном случае:

алг лог МожноХодить(цел y, цел x)
нач
  знач := (1 <= y) и (y <= N) и (1 <= x) и (x <= N) и (доска[y, x] = 0);
кон

Алгоритм ЛучшийХод с учетом эвристики по Варнсдорфу для расположения коня в клетке с координатами y и x возвращает номер направления перемещения, пригодного для использования в качестве индекса массивов dy и dx. Вцелочисленных переменных лучшееНапр и лучшийВес находятся найденные лучшее направление перемещения и вес для него, напр, напр2, вес – номер направления перемещения, номер следующего за ним направления, вес по следующему направлению рассчитанный, ny, nx – новые координаты местоположения коня с учетом приращений координат:

алг цел ЛучшийХод(цел y, цел x)
нач
  цел лучшееНапр, лучшийВес;
  цел напр, напр2, вес;
  цел ny, nx;

Вначале лучшее направление перемещения неопределенно и лучшим весом направления перемещения считается наибольший возможный с запасом:

  лучшееНапр := -1;
  лучшийВес := лучшийВесНач;

По всем номерам возможных направлений перемещения коня формируется новое положение коня:

  нц для напр от 1 до Ndydx
    ny := y + dy[напр];
    nx := x + dx[напр];

Если в эту клетку шахматной доски можно ходить, то производится оценка веса этой клетки:

    если МожноХодить(ny, nx)
      то
        вес := 0;

Для этого подсчитывается количество клеток доски, в которые из рассматриваемой клетки возможен переход конем, то есть вес клетки доски:

        нц для напр2 от 1 до Ndydx
          если МожноХодить(ny + dy[напр2], nx + dx[напр2])
            то
              вес := вес + 1;
          все
        кц

Если вес меньше лучшего, то запоминаются направление и вес:

        если вес < лучшийВес
          то
            лучшееНапр := напр;
            лучшийВес := вес;
        все
    все
  кц

Возвращается значение номера лучшего по эвристике направления:

  знач := лучшееНапр;
кон

Алгоритм Решить ищет решение рекурсивно начиная с хода коня номерХода, когда конь находится на клетке шахматной доски с координатами y и x. В целочисленных переменных содержатся: напр – номер направления в любом измассивов с приращениями, ny, nx – координаты клетки, куда конь пойдет:

алг лог Решить(цел номерХода, цел y, цел x)
нач
  цел напр;
  цел ny, nx;

Если номер хода коня превышает число клеток, то успешное завершение:

  если номерХода > NN
    то
      знач := да;
      выход;
  все

Иначе определяем лучшее направление перемещения и координаты для хода коня:

  напр := ЛучшийХод(y, x);
  ny := y + dy[напр];
  nx := x + dx[напр];

Если конь этот ход может совершить, то он его совершает:

  если МожноХодить(ny, nx)
    то
      доска[ny, nx] := номерХода;

Если допускается решение из совершенного хода, то ус-пешное завершение, иначе происходит отмена хода коня:

      если Решить(номерХода + 1, ny, nx)
        то
          знач := да;
          выход;
        иначе
          доска[ny, nx] := 0;
      все
  все

В любом другом случае решений нет:

  знач := нет;
кон

Рисунок 1. Результаты работы программы

Полный исходный текст программы находится на сайте журнала http://samag.ru. Статья позволят изучать и совершенствовать программирование на примере классической задачи информатики с умеренной сложностью.

1. Вирт Н. Алгоритмы + структуры данных = программы / Н. Вирт. – М.: Мир, 1985. 406 с.
2. Knight's tour // Rosetta Code. URL: http://rosettacode.org/wiki/Knight's_tour (дата обращения: 04.10.2018).
3. Ткаченко К. Простейший рекурсивный алгоритм с возвратом и эвристикой в 1С на примере задачи о ходе коня. // «Системный администратор», № 1-2, 2018 г. – С. 65-67. URL: http://samag.ru/archive/article/3584 (дата обращения:04.10.2018).

Ключевые слова: задача о ходе коня, рекурсивный алгоритм с возвратом, рекурсивный алгоритм с эвристикой, школьный алгоритмический язык.

Комментарии могут оставлять только зарегистрированные пользователи