Ещё одна классическая задача. Нужно обойти конём все поля шахматной доски, начав с некоторого выбранного поля. Приведённая программа - консольная, но она иллюстрирует свои действия печатью того, какие варианты сейчас перебираются (на это и уходит 99% времени работы, лень было писать прямо в видеопамять). Константа N в программе задаёт размер доски, сейчас там значение 5 - при значении N=8, думаю, будет считаться довольно долго (метод простейший - полный рекурсивный перебор возможных путей). Нумерация полей - слева и сверху, с нуля. Путь из левого верхнего угла для доски 5x5 будет успешно найден.

//Путь коня по шахматной доске
#include <stdio.h>
#include <conio.h>
 
const int N=5;                                           // размер доски
 
int desk[N][N];                                          // поля доски
int nstep;                                               // номер шага
 
void Print (void) {
int i,j;
 clrscr();
 for (i=0; i<N; i++)
 for (j=0; j<N; j++) {
  gotoxy (j*3+1 ,i+1);
  printf ("%02d ", desk[i][j]);
 }
}
 
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;                              // локальный параметр - номер хода
Print();
if (x0 < 0 || x0 >N-1 || y0 < 0 || y0 >N-1 ) return(0);                              // выход за пределы доски
if (desk[x0][y0] !=0)
 return(0);                                 // поле уже пройдено
desk[x0][y0] = ++nstep;                     // отметить свободное поле
if (nstep == N*N)
     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);                            // последовательность не найдена
}
 
int Path(int x0, int y0)
{
int i,j;                                              // очистка доски
for (i=0; i<N; i++)
     for (j=0; j<N; j++) desk[i][j] =0;
nstep = 0;                                    // установить номер шага
return step(x0,y0);                           // вызвать функцию для исходной
}                                             // позиции
 
void main (void) {
 int n=Path (0,0); // нумерация полей - слева и сверху, с нуля
 Print();
 printf ("\nRes=%d",n);
}

P.S. Кстати, не так уж долго это работает, вот листинги некоторых результатов с вычислением требуемого числа шагов.

На доске 4*4 или менее решения не существует.

Для доски 5*5:

01 08 19 14 25
18 13 02 09 06
03 20 07 24 15
12 17 22 05 10
21 04 11 16 23
Res=1,Steps=614838

Для доски 6*6:
01 24 27 12 09 36
22 11 02 25 28 13
03 26 23 10 35 08
18 21 04 31 14 29
05 32 19 16 07 34
20 17 06 33 30 15
Res=1,Steps=82995890

Для доски 7*7:
01 20 29 42 45 38 31
28 43 02 19 30 41 46
03 18 21 44 39 32 37
22 27 04 17 36 47 40
05 08 11 26 33 16 35
12 23 06 09 14 25 48
07 10 13 24 49 34 15
Res=1,Steps=84376540

Для доски 8*8:
36 31 48 57 38 41 50 59
47 56 37 30 49 58 39 42
32 35 54 45 40 29 60 51
55 46 33 26 53 62 43 28
34 25 06 13 44 27 52 61
07 14 17 24 05 12 63 20
16 23 02 09 18 21 04 11
01 08 15 22 03 10 19 64
Res=1,Steps=174326079

Для доски 9*9:

В этих тестах использовалась чуть изменённая версия программы (убрана промежуточная печать и добавлен общий счётчик числа шагов). Кроме того, массив xy незачем делать локальным. Для доски 8x8 с начального поля (0,0) решение в разумное время вообще не нашлось, а вот с левого нижнего поля доски

int n=Path (N-1,0);

получилось быстро.

#include <stdio.h>
#include <conio.h>

const int N=7;
int desk[N][N];
int nstep;
double p=0; //Число шагов

static int xy[8][2] = {
 { 1,-2},{ 1, 2},{-1,-2},{-1, 2},{ 2,-1},{ 2, 1},{-2, 1},{-2,-1}
};

int step(int x0, int y0) {
 int i;
 p++;
 if (x0 < 0 || x0 >N-1 || y0 < 0 || y0 >N-1 ) return(0);
 if (desk[x0][y0] !=0) return(0);
 desk[x0][y0] = ++nstep;
 if (nstep == N*N) 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);
}

int Path(int x0, int y0) {
 int i,j;
 for (i=0; i<N; i++)
 for (j=0; j<N; j++) desk[i][j] =0;
 nstep = 0;
 return step(x0,y0);
}

void main (void) {
 int n=Path (0,0);
 clrscr();
 int i,j;
 for (i=0; i<N; i++)
 for (j=0; j<N; j++) {
  gotoxy (j*3+1 ,i+1);
  printf ("%02d ", desk[i][j]);
 }
 printf ("\nRes=%d,Steps=%.0lf",n,p);
}

Следует понимать, что как и любое рекурсивное решение, программа активно пользуется стеком и при "плохой" компиляции может привести к переполнению стека.

гостевая; E-mail