Обход шахматной доски
В качестве примера рассмотрим проектирование функции для поиска последовательности обхода конем шахматной доски.
Шаг 1. Алгоритм обхода можно разбить на последовательность шагов. Каждый шаг характеризуется начальным состоянием - текущим положением коня. Алгоритм на каждом шаге предполагает проверку возможности сделать ход в каждом из 8 допустимых направлений. Схема алгоритма имеет вид:
void step(int x0, int y0)
{ // формальные параметры -
// текущая позиция коня
// приращения координат для 8 ходов
static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода
if (x < 0 || x >=7 || y < 0 || y >=7 )
return; // выход за пределы доски
for (i=0; i< 8; i++)
step(x0+xy[i][0], y0+xy[i][1]);
// выполнить следующий ход
}
Шаг 2. Предыдущий шаг дает полный перебор возможных последовательностей ходов коня. Функция имеет результат void, то есть является безусловной. Далее необходимо определить, как производить выбор необходимой последовательности. Очевидно, функция должна давать логический результат - 0, если при выполнении очередного хода в данном направлении задача не решается и 1, если решается успешно. При этом цикл, в котором происходит рекурсивный вызов - просмотр очередных ходов, выполняется до первого успешного вызова:
int step(int x0, int y0)
{
static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода
if (x < 0 || x >=7 || y < 0 || y >=7 )
return(0); // выход за пределы доски
for (i=0; i< 8; i++)
if (step(x0+xy[i][0], y0+xy[i][1]))
return(1); // поиск успешного хода
return(0); // последовательность не найдена
}
Шаг 3. Далее необходимо определить условия начала и завершения рекурсивного процесса, а также условия взаимодействия шагов между собой. Условием завершения процесса является обход всех 64 полей доски. При этом не должно производиться повторное попадание на то же самое поле.
Тогда необходимо фиксировать количество пройденных полей и отмечать пройденные. Это можно сделать только используя внешние переменные, так как они проверяются на разных шагах рекурсии. Номер шага будем использовать также для отметки поля. По завершению программы массив полей будет содержать номера шагов коня.
//------------------------------------------------------bk54-02.cpp
//------Обход шахматной доски конем
int desk[8][8]; // поля доски
int nstep; // номер шага
int step(int x0, int y0)
{
static int xy[8][2] = {{ 1,-2},{ 1, 2},{-1,-2},{-1, 2},
{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};
int i; // локальный параметр - номер хода
if (x0 < 0 || x0 >=7 || y0 < 0 || y0 >=7 )
return(0); // выход за пределы доски
if (desk[x0][y0] !=0)
return(0); // поле уже пройдено
desk[x0][y0] = nstep++; // отметить свободное поле
if (nstep == 64)
return(1); // все поля отмечены - успех
for (i=0; i< 8; i++)
if (step(x0+xy[i][0], y0+xy[i][1]))
return(1); // поиск успешного хода
nstep--; // вернуться на ход назад
desk[x0][y0] = 0; // стереть отметку поля
return(0); // последовательность не найдена
}
void Path(int x0, int y0)
{
int i,j; // очистка доски
for (i=0; i< 8; i++)
for (j=0; j< 8; j++) desk[i][j] =0;
nstep = 1; // установить номер шага
step(x0,y0); // вызвать функцию для исходной
} // позиции
