Обход шахматной доски ходом коня

Конь должен побывать в каждой клетке доски размером ровно один раз. Примем нумерацию возможных ходов коня из клетки как это изображено на рисунке. В стеке будем хранить координаты покидаемой клетки и номер выполняемого хода. Когда обнару­жит­ся, что никакой ход из клетки невозможен, берем координаты предыдущей клетки из стека и пытаемся покинуть ее с помощью хода, имеющего номер на единицу больше, чем тот ход, с помощью которого ее покидали ранее (операция "возврат"). Если уже посетили все клеток, то задача решена, и трасса обхода лежит в стеке. Если при попытке взять клетку из стека, обнаруживается, что стек пуст, то это означает, что задача не имеет решения. Ниже приведен текст программы.

struct STACK{

int i,j; // координаты клетки

int move; // номер хода, которым покидаем клетку

}; // элемент стека

bool Horse(int n, STACK *stack);

//-----------------------------------

static bool Move(int N, int i1,int j1, int n, int *i2, int *j2){

// Ход коня. Конь ходит из клетки i1,j1 ходом номер n

// и попадает в клетку *i2,*j2

// N - размер доски

// Возвращает true при успехе

switch(n){

case 0:

*i2=i1+1;

*j2=j1+2;

Break;

case 1:

*i2=i1+2;

*j2=j1+1;

Break;

case 2:

*i2=i1+2;

*j2=j1-1;

Break;

case 3:

*i2=i1+1;

*j2=j1-2;

Break;

case 4:

*i2=i1-1;

*j2=j1-2;

Break;

case 5:

*i2=i1-2;

*j2=j1-1;

Break;

case 6:

*i2=i1-2;

*j2=j1+1;

Break;

case 7:

*i2=i1-1;

*j2=j1+2;

Break;

default:

// сюда можно попасть только при ошибке в программе

*i2=INT_MAX;

*j2=INT_MAX;

}

return (*i2>=0 && *i2<N && *j2>=0 && *j2<N);

}

//-----------------------------------

bool Horse(int n, STACK *stack){

// n - размер доски.

// результат будет получен в стеке stack.

// Каждый раз, когда покидаем клетку, ее координаты

// и номер хода помещаем в стек.

// возврат true - успех

bool **Board=NULL; // в массиве доска n*n помечаем факт посещения клетки

int i,j; // текущие координаты клетки

int v; // указатель стека








Дата добавления: 2014-12-02; просмотров: 926;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.