Nickolay.info. Алгоритмы. Путь коня по шахматной доске |
Ещё одна классическая задача. Нужно обойти конём все поля шахматной доски, начав с некоторого выбранного поля. Приведённая программа - консольная, но она иллюстрирует свои действия печатью того, какие варианты сейчас перебираются (на это и уходит 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
|