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

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

Методы оптимизации

К одному из наиболее интересных разделов программирования относятся задачи из области искусственного интеллекта, в которых решение ищется методом проб и ошибок [1,2]. При этом имеет место перебор при поиске решения, а его продолжительность может быть сокращена за счет применения тех или иных эвристических правил (методы оптимизации).

Класс алгоритмов, позволяющий решать подобные задачи, в англоязычной литературе называется «backtracking algorithms» («алгоритмы с возвратом»). Такие алгоритмы применяются тогда, когда не подходят более «направленные» методы [3].

Давайте исследуем одну из наиболее известных задач данного класса — о ходе коня [3—5]. Она состоит в том, чтобы найти обход доски размером NxM конем, перемещающимся по правилам шахматной игры. Если такой обход существует, то каждое поле посещается только один раз (выполняется NxM-1 шагов). Здесь мы проанализируем методы оптимизации (сокращение перебора) и исследуем работу итеративной, рекурсивной и автоматной программ. Рассмотрим сначала методы оптимизации, применяемые для сокращения перебора в итеративной программе:

• определение клеток, обход из которых невозможен (оптимизация 1);
• выявление заблокированных клеток (оптимизация 2);
• применение правила Варнсдорфа (оптимизация 3);
• использование различных массивов для ходов коня (оптимизация 4).

Определение клеток, обход из которых невозможен

Если количество клеток доски нечетно (число белых и черных клеток отличается на единицу), то обход существует только из клеток того цвета, которых будет больше. Нетрудно заметить, что путь коня проходит по клеткам, чередующимся по цвету. Если общее число клеток доски нечетно, то первая и последняя клетки пути, пройденного конем, будут одного и того же цвета. Значит, обход будет существовать только тогда, когда он начнется клеткой того цвета, который имеют наибольшее число клеток.

Выполнение данного условия проверяется следующей функцией:

Листинг 1

int solution_impossible() 
{
  // Если произведение сторон доски нечетно и
 сумма координат начальной позиции
  // нечетна, то решения не существует.
  return ((size_x*size_y) % 2 != 0) &&
 ((start_x+start_y) % 2 != 0) ;
}

Однако приведенное правило не охватывает всех клеток, для которых обхода не существует. Так, для доски размером 3x7 клеток помимо тех, для которых выполняется приведенное правило, обход невозможен также из клетки (2,4).

Выявление заблокированных клеток

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

Его развитием стало определение групп заблокированных клеток, связанных друг с другом, но отрезанных от остальной части доски. В рассматриваемой программе определяются группы из двух заблокированных клеток, что значительно уменьшает количество возвратов для небольших досок, а при использовании вместе с правилом Варнсдорфа — и для больших (например, размером 100x100 клеток).

Применение правила Варнсдорфа

Среди многих эвристических методов, используемых для сокращения перебора [5], правило Варнсдорфа является наиболее простым. В соответствии с ним при обходе доски шахматного коня следует каждый раз ставить на то поле, из которого он может сделать наименьшее число ходов по еще не пройденным полям. Если таких полей несколько, то можно выбрать любое из них, что может, однако, завести коня в тупик и потребовать возврата. Отметим, что наилучшим образом правило Варнсдорфа работает для угловых полей.

Использование различных массивов для ходов коня

Ходы коня могут быть заданы, например, в виде массива:

int possible_moves_sh[][2] = {
{-1, -2}, {-2, -1}, {-2,  1}, { 1, -2},
{-1, 2}, { 2, -1}, { 1, 2}, { 2, 1} };

Каждый его элемент определяет один возможный ход коня и содержит изменения его координат на доске при совершении хода. При использовании различных массивов для ходов коня количество возвратов может различаться. В программе применяются пять массивов, содержащих возможные ходы коня в различном порядке. В ней задается максимальное число возвратов (GOOD_RET), и когда оно будет достигнуто, поиск пути начинается заново с использованием уже другого массива. При поиске обхода с применением последнего массива количество возвратов ограничивается значением MAX_RET. Если при совместном использовании всех предложенных методов оптимизации установить значение GOOD_RET равным единице, то для досок, близких к квадратным, можно строить обходы без единого возврата для всех клеток, из которых существует обход. Обход без единого возврата из каждой клетки не удается получить для «вытянутых» досок (например, 14x3 клетки) и для больших (например, 100x100 клеток).

Итеративная программа

Полный перебор

Идея алгоритма для итеративной программы заключается в следующем:

• на каждом шаге ищется фрагмент пути, начинающийся из текущей клетки и не включающий уже пройденные;
• при совершении хода из массива возможных ходов извлекается очередной элемент, который приводит в незанятую клетку, находящуюся в пределах доски;
• если ход невозможен, то происходит возврат в предыдущую клетку (отмена хода);
• поиск пути считается успешным тогда, когда номер текущего хода станет равным количеству клеток на доске. Если из начальной клетки перебраны все возможные ходы, то пути не существует.

Структура функции, выполняющей перебор, приведена в листинге 2.

Листинг 2

void find_path()
{
  for( move_num = 1 ; move_num <= max_moves ; )
  {
    if( make_move() )      // Сделать ход.
      move_num++ ;
    else                   // Ход невозможен.
      if( move_num > 1 )
      {
        undo_move() ;      // Отменить ход.
        move_num— ;
      }
      else
        return ;           // Обход невозможен.
  }        
}

Номер использованного варианта для каждого из ходов запоминается в массиве, размер которого выбирается в соответствии с размером доски. Описанный алгоритм выполняет перебор вариантов и находит решение, если оно имеется. Отсутствие решения приводит к полному перебору всех вариантов. В табл. 1 для иллюстрации выполнения возвратов приведен протокол обхода доски размером 3x4 клетки из клетки (2,4).

Таблица 1. Протокол обхода доски размером 3x4 клетки из клетки (2,4)

Для некоторых клеток программа работает чрезвычайно медленно уже при небольших размерах доски. Так, для доски 6x6 клеток при старте из клетки (5,2) поиск пути требует 291 077 505 возвратов.

Результаты работы программы с оптимизацией

Из работы [5] известно, что для досок размером NxM и MxN:

• не существует ни одного обхода при N, M < 3; N = 3, M = 5, 6; N = M = 4;
• имеется как минимум одна клетка, из которой возможен обход доски при N = 3, M = 4; N = 3, M >7; N > 4, M > 5.

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

Для примера рассмотрим результаты обхода некоторых досок. Для доски размером 5x5 клеток приводится таблица, где указывается количество возвратов, выполненное при нахождении обхода из соответствующей клетки (табл. 2). В случае отсутствия обхода в клетке ставится символ N, а если количество возвратов превысило задаваемую в программе величину (MAX_RET = 400 000), то поиск пути прекращается, а в соответствующей клетке выводится сокращение LIM. В таблицах, построенных для метода оптимизации, когда используются различные массивы вариантов для хода коня, в клетке дополнительно дается обозначение того массива (от A до E), при применении которого обход совершался без возвратов (GOOD_RET = 1). Причем если результат был получен для первого массива, то соответствующий ему символ A не выводится.

Таблица 2. Результаты работы программы для доски размером 5 x 5 клеток

Для классической шахматной доски размером 8x8 клеток получены такие результаты:

• для оптимизаций 1 и 2 в большинстве клеток превышено предельное значение числа возвратов. Минимальное количество возвратов в клетке (5,5) - 2502;
• для оптимизаций 1 и 3 во всех клетках получился ноль возвратов, кроме клеток (4,1) и (6,4), где вышло 9 и 79 возвратов соответственно;
• для оптимизаций 1-3 в клетке (6,4) было три возврата, а в остальных - ноль возвратов;
• для оптимизаций 1-4 во всех клетках вышел ноль возвратов, а в клетке (6,4) был использован второй массив возможных ходов.

Для доски размером 100x100 клеток получены такие результаты:

• для оптимизаций 1-3 в большинстве клеток получен ноль возвратов, а количество возвратов в остальных клетках варьируется от единицы до значений, превышающих заданный предел;
• для оптимизаций 1-4 во всех клетках, за исключением клеток (94,24) и (94,79), вышел ноль возвратов.

Рекурсивная программа

Наиболее известное решение для задачи обхода конем — рекурсивное [2]. При этом структура функции, выполняющей перебор, имеет следующий вид:

Листинг 3

int find_path( int cur_x, int cur_y,
 int move_num )
{
  desk_state[cur_x][cur_y] = move_num ; 
// Запомнить ход.
  if( move_num > max_moves ) return 1 ; 
// Проверить завершение обхода.
  // Проверить каждый возможный ход
 из текущей клетки.
  for( int i = 0 ; i < 8 ; i++ )      
  {
    int next_x = cur_x + possible_moves[i][0] ;
 // Определить следующее поле.
    int next_y = cur_y + possible_moves[i][1] ;
    if(    move_possible( next_x, next_y ) 
        && find_path( next_x, next_y,
 move_num+1 )) return 1 ;
  }
  // Возврат.
  desk_state[cur_x][cur_y] = 0 ;
  back_ret++ ;
  return 0 ; 
}

В этой программе могут быть использованы все виды оптимизаций, описанные выше.

Автоматная программа

Если две первые программы для решения этой задачи вполне традиционны [2], то автоматные к таковым не относятся. Отметим, что автоматная программа может быть формально построена из описанной выше итеративной с помощью метода, изложенного в работе [7]. Автоматная программа может быть также формально построена и по приведенной рекурсивной программе с использованием метода, предложенного в работе [8].

Рис. 1. Схема связей автомата

Кроме того, можно создать автоматную программу путем непосредственного построения автомата по условиям задачи. На рис. 1, 2 приведены соответствующие схема связей и граф переходов автомата Мили.

Рис. 2. Граф переходов автомата

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

Упрощенный текст функции, реализующей этот автомат, приведен в листинге 4.

Листинг 4

void find_path_switch( int limit )
{
  y = 0 ;
  do
    switch( y )
    {
      case 0:
        if     ( x4())               y = 3 ;
        else           { z1_0() ;    y = 1 ; }
 break ;
      case 1:
        if     ( x1())               y = 4 ;
        else if( x3()) { z1_1() ; }
        else if( x2()) { z2() ;
                          z1_2() ;   y = 2 ; }
        else                          y = 3 ;
   break ;
      case 2:
        if     ( x5(limit))        y = 5 ;
        else                         y = 1 ;
   break ;
      case 3:                        y = 0 ;
   break ;
      case 4:                        y = 0 ;
   break ;
      case 5:                        y = 0 ;
   break ;
    }
  while( y < 3 ) ;
}

Что же лучше?

Совместное применение сравнительно простых и известных методов оптимизации позволило резко сократить перебор, благодаря чему удается относительно быстро находить пути в досках весьма большой размерности. Так, на компьютере, оснащенном 400-МГц Pentium II, поиск обхода из каждой клетки доски размером 200x200 клеток занял примерно 20 минут (на поиск одного обхода — около 0,03 с), причем для большинства клеток обход выполняется без единого возврата. В программе наряду с рассмотренными могли бы использоваться и другие методы оптимизации [5]. А на досках очень большого размера, например 2000x2000 клеток, нахождение даже одного пути занимает значительное время.

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

Результаты других экспериментов и полный текст программы, с помощью которой они были выполнены, будут приведены на сайтах is.ifmo.ru и www.softcraft.ru в разделе «Автоматы».

Настоящая работа выполнена на кафедре «Компьютерные технологии» С.-Петербургского государственного института точной механики и оптики (технического университета). Авторы выражают благодарность А. Э. Григорьеву, студенту этой кафедры, принимавшему участие в начале данной работы. Она выполнялась при поддержке Российского фонда фундаментальных исследований.

ОБ АВТОРАХ

Анатолий Абрамович Шалыто — ученый секретарь, профессор СПбГИТМО (ТУ). С ним можно связаться по адресу: mail@avrorasystems.com («для Шалыто»).

Никита Иосифович Туккель — инженер-программист. С ним можно связаться по адресу: cynical@mail.ru.

Никита Назимович Шамгунов — трехкратный чемпион Урала по программированию, двухкратный финалист чемпионатов мира по программированию ACM, аспирант СПбГИТМО (ТУ).