:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте ::
Путь: Математика » Комбинаторика и перебор » Обход доски шахматным конем
На правах рекламы
срочные тиражи дисков до 1000 шт
  Обход доски шахматным конем




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



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

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

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

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

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


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



Другой способ решения задачи, состоит, очевидно, в переборе с отходом назад. Ниже дана иллюстрация подхода для доски 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( );
  }
}