Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Математика / Комбинаторика и переборные задачи /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Обход доски шахматным конем - Программирование от RIN.RU
Обход доски шахматным конем

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


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

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь
Спеши купить Чанган CS95 kuntsevo.changanauto.ru в Москве.