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