Оригинальное правило, дающее линейный по времени алгоритм обхода доски, было предложена Варнсдорфом(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( );
  }
}