последние 30 сообщений Сделать стартовой Добавить в Избранное

*сНежный форум* - территория отдыха для всей семьи!

Объявление

Letyshops [lifetime]

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.


Вы здесь » *сНежный форум* - территория отдыха для всей семьи! » Программирование » Обход конем шахматной доски


Обход конем шахматной доски

Сообщений 1 страница 4 из 4

1

Как обойти конем шахматную доску, не побывав ни на каком поле дважды и вернувшись в исходную клетку?

Совершенно заслуженно выражение "ход конем" означает в русском языке очень хитроумный и нетривиальный замысел. Вот и задача обхода доски является довольно крепким орешком, на котором обламывают зубы даже некоторые профессионалы. Нет, конечно, найти какой-то один обход не так сложно. Например, легко можно нарисовать на бумаге маршрут обхода конем доски 4x4, а потом разорвать 4 этих маршрута вблизи центра доски и склеить из них один маршрут. Есть и другой известный способ: сначала обойти "кайму" доски шириной в две клетки, а потом - центральные 16 клеток.

Но меня в этом сюжете интересует (и всегда интересовало) не реализация конкретного обхода, найденного фактически вручную, а совершенно другое. Например, пусть обход уже начат - конь уже побывал на нескольких клетках. Можно ли завершить этот обход? Если да, то как действовать? Очевидно, что здесь задача совершенно не зависит от конкретного размера и даже от формы доски. Точно такую же задачу можно поставить на совершенно произвольном графе. Единственное, что нам здесь нужно от коня и доски - это знать, какие клетки для коня являются "соседними", а какие - нет.

Вот как раз в этой задаче полный перебор всех вариантов недоступен даже для нынешних компьютеров, так что приходится искать иные пути. Собственно, хорошие идеи давно известны. Например, известно такое правило: конь всегда должен перескакивать на клетку, для которой количество возможных ходов с нее является наименьшим. А если таких клеток несколько? Однозначного рецепта, как видите, нет…

затравка - отсюда

Тут даже можно купить готовое решение-программу на Паскале. Но интересней разобраться с алгоритмом самому.

Как Панов решает задачу вслепую - мнемонический трюк!

Алгоритмы дискретной математики для этой задачи - шамильтонов цикл и не только.

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

Другой способ состоит в нахождении маршрута по половинке доски, симметричном дублировании его и соединении обоих маршрутов.

2

Математические варианты решения:

Схема перебора с возвратом >> правило Варнсдорфа (MathCad)

Наиболее толковые описания:

тут и на алголисте.

3

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

Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(Warnsdorff) в 1983 году.

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

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

Эвристика всегда работает на досках от 5x5 до 76x76 клеток, при больших размерах доски конь может зайти в тупик. Кроме того, базирующийся на правиле алгоритм не дает всех возможных решений (т.е путей коня): можно пойти против правила и все равно получить удовлетворяющий условию задачи обход.

Существует линейный алгоритм для досок любого размера, который делит доску на меньшие части, но, из-за обилия особых случаев, он довольно сложный и не такой интересный, как эта элегантная эвристика.

4

Переборное решение

Другой способ решения задачи, состоит, очевидно, в переборе с отходом назад. Ниже дана иллюстрация подхода для доски 8x8.

Используем два одномерных массива row[64] и col[64] для хранения соответственно номеров строк и колонок, которые конь последовательно проходит по доске.

Конь, находящийся в позиции (i, j), может следующим ходом оказаться в клетках с координатами (i-2, j+1), (i-1, j+2), (i+1, j+2), (i+2, ,j+1), (i+2, ,j-1), (i+1, j-2), (i-1, j-2), (i-2, j-1). Заметим, что если конь находится вблизи края доски, то некоторые ходы могут вызвать перемещение коня за ее пределы, что, конечно же, недопустимо. Восемь возможных перемещений коня могут быть заданы в виде двух массивов ktmov1[] и ktmov2[], как продемонстрировано в следующем фрагменте программы.

Исходя из этого, конь, находящийся в позиции (i, j) может переместиться в позицию (i+ktmov[k], j+ktmov2[k]), где k - какое-либо значение из диапазона 0 - 7, выбираемое из условия, что конь должен остаться на доске. Итак, программа, реализующая перемещение коня в соответствии с вышеприведенными условиями будет выглядеть следующим образом:
int arr[8][8], row[64], col[64];
int ktmov1[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int ktmov2[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

int i, j, move_num, d;
 
main() {
  addknight( );
}
 
addknight( )  {
  register int a, b, e;
      
/* пометить клетку как посещенную и запомнить координаты клетки */
  arr[i][j] = 1;
  row[move_num] = i;
  col[move_num] = j;
  move_num++;
      
/* проверить 8 возможных перемещений коня */
  for ( a = 0 ; a <= 7 ; a++ ) {
   /* если все ходы сделаны, печатаем их */
    if ( move_num >= 64 ) {
      writeboard( );
      exit ( 0 );
    }
     
   /* определяем колонку и строку для следующего хода */
    b = i + ktmov1[a];
    e = j + ktmov2[a];
     
   /* проверяем, что после выполенения хода конь остается на шахматной доске */
    if ( b < 0 || b > 7 || e < 0 || e > 7 )
      continue;

   /* проверяем, были ли мы уже в этой клетке */
    if ( arr[b][e] == 1 )
      continue;
     i = b; j = e;
    addknight();
  }
      
/* уменьшить счетчик ходов и попробовать сделать следующий ход */
  move_num-- ;
 
/* освобождаем клетку, ранее занятую конем */
  arr[row[move_num]][col[move_num]] = 0;
  move_num--;  /* пробуем сделать следующий ход */
  i = row[move_num]; j = col[move_num];
  move_num++;
}
 
writeboard( ) {
  int a;
      
  clrscr( );
  gotoxy ( 1, 10 );
  printf ( "Hit any key for next move " );
  gotoxy ( 1, 11 );
  for ( a = 0 ; a <= 63 ; a++ ) {
    if ( a % 8 == 0 )
      printf ( "\n" );
    printf ( "#" );
  }
  for ( a = 0 ; a &lt;= 63 ; a++ ) {
    gotoxy ( col[a] * 3 + 1, 12 + row[a] );
    printf ( "%3d", a + 1 );
    getch( );
  }
}


Вы здесь » *сНежный форум* - территория отдыха для всей семьи! » Программирование » Обход конем шахматной доски