» Задание повышенной сложности про шахматного коня

Привет всем!
Помогите доделать задачку:
Дана шахматная доска размером 8х8 и шахматный конь. Программа должна запросить у пользователя координаты клетки поля и поставить туда коня. Задача программы найти и вывести путь коня, при котором он обойдет все клетки доски, становясь в каждую клетку только один раз.

На доске 5х5 доходил до 20 хода.
А как сделать чтоб до конца дошол.
А на 8х8 пока не делал.
Пробовал через рекурсию....

Пишу на С++.
Так что если есть предложения так пишите.
С удовольствием обговорю методы решения.
Даже не так хочется решить, а хочется понять....

________________________________
Подпись надо заработать. Wowik

Ну как.. как.. рекурсией, ессно

Дык то что через рекурсию я знаю...
Я не представляю как енто сделать.
программированием занимаюсь с декабря месяца

Задача эта есть в книге Дейтела "Как программировать на С++" (упраж к главе массивы - задача Эйлера путешествие коня). Кода там нет, но подробно описано как делать.

8 вариантов ходов конем. В первую очередь нужно обходить трудные клетки.
23444432
34666643
46888864
46888864
46888864
46888864
34666643
23444432

Ходить на клетку с меньшим числом доступности. ...

Ну смотри.. сколько у тебя максимум возможных ходов коня от любой позиции?
8
Перебираешь их по кругу, к примеру, и проверяешь, что:
а) место в пределах доски
б) еще не использовалось
если так, то идешь на него, и передаешь это место как первоначальное этой же функции . Если нет - рассматриваешь следующее место. А если такого нет, возвращаяешься выше (то есть на пред. ход)
и начинается все с самого начала.

дык так я и пробовал сделать...
конечно может я что-то вообще не так делаю но все же гляньте код:
#include <iostream.h>
const int n=8,m=8;
int npol=0,vilet=0;
int cord[n][2];
int *hmicord;
void vibmest(int*,int*);
void printBoard(int[][n]);
void hod(int*,int*);
void main()
{

int pole[n][n],currentRow=0,currentColumn=0,startRow=0, startColumn=0;

for(int a=0;a<n;a++)
{
for(int s=0;s<n;s++)
{
pole[a][s]=0;
}
}
cout<<"Vvedite nachalnie koordinati konya ";
cin>>startRow
>>startColumn;
pole[currentRow][currentColumn]=1;
printBoard(pole);




for(int i=1;i<n*n;i++)
{
hod(&startRow,&startColumn);
vibmest(&startRow,&startColumn);
// bool flag=true;
// hod(pole,moveNumber,horizontal,vertical,&currentRow,&currentColumn,&startRow,&startColumn,&flag);
pole[startRow][startColumn]=i+1;
// if(flag==false)
// {
// cout<<"Kon do konca ne dosol! A }|{alb! \n";
// break;
// }
// startRow=currentRow;
// startColumn=currentColumn;
printBoard(pole);
}
printBoard(pole);
cin>>startRow;
}

/*
void hod2(int pole[n][n],int moveNumber, int horizontal[m],int vertical[m],int *currentRw,int *currentCl,int *startR,int *startC,bool *flag)
{

*currentRw =*startR + horizontal[moveNumber];
*currentCl =*startC + vertical[moveNumber];
if(*currentRw<0||*currentRw>=n||*currentCl<0||*currentCl>=n)
hod(pole,moveNumber+1,horizontal,vertical,currentRw,currentCl,startR,startC,flag);
if(moveNumber==m)
moveNumber=0;
if(pole[*currentRw][*currentCl]!=0)
{
vilet++;
hod(pole,moveNumber+1,horizontal,vertical,currentRw,currentCl,startR,startC,flag);
}
if(vilet>=7)
*flag=false;
}
*/
void printBoard(int pboard[][n])
{
cout<<npol<<"________________\n";
for(int a=0;a<n;a++)
{
for(int s=0;s<n;s++)
{
if(pboard[a][s]<10)
cout<<pboard[a][s]<<" |";
else
cout<<pboard[a][s]<<"|";

}
cout<<"\n";
}
cout<<npol<<"________________\n";
npol++;
}
void hod(int *startR,int *startC)
{
int currentCl,currentRw,
horizontal[8]={2,1,-1,-2,-2,-1,1,2},
vertical[8]={-1,-2,-2,-1,1,2,2,1};
int count=0;
for(int c=0;c<m;c++)
{
currentRw =*startR + horizontal[c];
currentCl =*startC + vertical[c];
if(currentRw>=0&&currentCl>=0&&currentRw<=n&&currentCl<=n)
{
cord[count][1]=currentRw;
cord[count][2]=currentCl;
++count;
}
}
hmicord=&count;
}
void vibmest(int* moveRw,int *moveCl)
{
int *vibor=new int[*hmicord];
int prior[n][n]={{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}};
for(int co=0;co<=*hmicord;co++)
{
vibor[co]=prior[cord[co][1]][cord[co][2]];
cout<<vibor[co]<<"\n";
}
int min=vibor[0],number=0;

for(int cv=1;cv<*hmicord;cv++)
{
if(min>vibor[cv])
{
min=vibor[cv];
number=cv;
}
}
*moveRw=cord[number][1];
*moveCl=cord[number][2];
delete[] vibor;
}

плохо пробовал через рекурсию.
25 клеток расставляет за 329 ходов.
64 - пока не знаю. Простой алгоритм рекурсивного перебора слишком долог.


Цитата:

// cout<<"Kon do konca ne dosol! A }|{alb! \n";

Тут 2 способа!
только один через рекурсию как коментарий.
Я не знаю как сделать чтоб в рекурсивном способе сделать анализ хода коня.

Рекурсия очень долго будет работать, надо использовать поиск в ширину. Алгоритмы на графах проходил?

Нет!
Я читал в нете про графы, но ничего не понял
И там пример на паскале.

krol придется тебе приблизительно узнать паскакаль тогда :) Тебе ж чтоб в нете инфу нарыть нормальную, иногда английский приходится знать, да? Ну вот и здесь то же :)

Да в принципе с паскалем я знаком немного.
Да и с англ. впиринципе нормально.
Вот тока времени мало....
Просто если я сделаю программку мне экзамен в академии автоматом будет.
А вообще кто-то про код может что-то сказать?
Это праильно записано?
int *vibor=new int[*hmicord];

А то так долго думает на этом месте.

krol

Цитата:

int *vibor=new int[*hmicord];

Смотря что ты этим имел в виду
Если нужен 2-мерный динамический массив, то его надо обьявить так:

int **vibor;

А потом инициализировать

*vibor = new int[arr_length];

и дальше

for(i=0; i<arr_length; i++)
{
vibor[i] = new int[arr_depth];
}


A eсли это просто одномерный массив - то так:

int *vibor[length];

Не это надо одномерный динамический массив для хранения значений!

Почитай тут...
http://forum.ru-board.com/topic.cgi?forum=33&topic=0873#1
если сильно надо могу написать на выходных как посвободнее буду

FuzzyLogic

Я б был не против увидить готовый код, но мне самому интересно понятьь....
А ту что я написал не идет?
может просто подправить ее..

Типичная задача на применение эвристики...делать ход в ту клетку, откуда возможно наибольшее количество ходов. Как ни странно, в данной задаче это помогает.

krol
Это простейшая задачка по backtracking рекурсии

Код:
typedef int Matrix[N][M] ;
typedef int boolean ;

/*Функция проверки правильности клетки*/
boolean legal(Matrix mat ,int i, int j)
{
return !( (i>=N||i<0) || (j>=M||j<0) || mat[i][j] );
}

/*Проход по доске*/
boolean fill_board(Matrix mat,int i,int j)
{
int t;
static int cnt = 0 ;
static int d_row[] = {2,2,-2,-2,1,1,-1,-1} ;
static int d_col[] = {1,-1,1,-1,2,-2,2,-2} ;

mat[i][j] = ++cnt ;
if(cnt==M*N) { /* Stopping condition */
cnt = 0 ;
return TRUE;
}
for(t = 0 ;t < 8 ; ++t) /* All possible continuation */
if(legal(mat , i+d_row[t] , j+d_col[t]))
if(fill_board(mat , i+d_row[t] , j+d_col[t]))
return TRUE;

mat[i][j] = 0 ; /* We can't fill the remaining entries from this entry */
cnt--;
return FALSE;
}

рекурсией все конечно очень просто... элементарно, я бы даже сказал... но скорость (
а количество вариантов просто ужасающее. даже если 1 Мвариант в секунду - это надолго... эвристику пока не пробовал, рекурсия тогда сильно усложняется.
попробую - выложу.

В эвристике нет никакой рекурсии, там всё настолько просто что проще просто некуда

Цитата:

boolean legal(Matrix mat ,int i, int j)
{
return !( (i>=N||i<0) || (j>=M||j<0) || mat[i][j] );
}

Зачем после return "!"?

Цитата:

typedef int Matrix[N][M] ;
typedef int boolean ;

Что это???

И еще этот код для С?
У меня С++ не берет его!

krol

Цитата:

И еще этот код для С?

Да, ANSI C

Цитата:

У меня С++ не берет его!  

Так это не полная прога,это всего лишь часть отвечающая за алгоритм


Цитата:

typedef int Matrix[N][M] ;  
typedef int boolean ;  
 

Что это???

Первое определение шахматной доски размером N на M клеток
Второе определение нового типа для TRUE/FALSE (для АНСИ Си )


Цитата:

Зачем после return "!"?

Чтобы возвращала TRUE если мы находимся на шахматной доске и FALSE если нет

А на С++ надо вместо
boolean legal(Matrix mat ,int i, int j)
{
return !( (i>=N||i<0) || (j>=M||j<0) || mat[i][j] );
}

писать
bool legal(Matrix mat ,int i, int j)
{
return !( (i>=N||i<0) || (j>=M||j<0) || mat[i][j] );
}

Matrix mat -- ???

krol

Цитата:

Matrix mat  -- ???

Mat это переменая типа Matrix,которая определена с помощью
Цитата:

typedef int Matrix[N][M] ;

П.С.Ты на алгоритм смотри,а не на сорцы

FuzzyLogic
Как бы ты (в виде реализации) применил бы эвристику? Насколько это можно оптимизировать?

А это тебе что не эвристика:
void vibmest(int* moveRw,int *moveCl)
{
int *vibor=new int[*hmicord];
int prior[n][n]={{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}};
for(int co=0;co<*hmicord;co++)
{
vibor[co]=prior[cord[co][1]][cord[co][2]];

}
int min=vibor[0],number=0;

for(int cv=1;cv<*hmicord;cv++)
{
if(min>vibor[cv])
{
min=vibor[cv];
number=cv;
}
}
*moveRw=cord[number][1];
*moveCl=cord[number][2];
delete[] vibor;
}

Вот тут откопал готовую прогу!
Если кому интересно можно скачать тут
http://krol-forum.webm.ru/download.htm
или глянуть описание тут
http://krol-forum.webm.ru/cgi-bin/YaBB.cgi?board=news;action=display;num=1045596771;start=4#4