Здравствуйте. Задача: рекурсивно обойти шахматную доску конем (программа просто выводит один вариант решения, без дополнительных наворотов, первый ход делается случайным образом, после каждого хода экран перерисовывается). Подскажите, пожалуйста, как нужно исправить код, чтобы функция находила решение. Сейчас поиск происходит бесконечно.
Знаю, что задача поднималась уже много раз и в сети полно решений - я пересмотрел многие, и все программы усложнены пока неизвестными мне функциями. Я выбрал одно решение и попытался его переделать, ведь единственный способ понять рекурсию - это понять рекурсию) Спасибо.
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <iostream>
#include <stdlib.h>
#include <math.h>
#include <time.h>
using namespace std;
const int n=8; //размер поля
int pole [n][n]={0};
int nstep=1; //счетчик шагов
static int xy[16] = { 1, 2, 2, 1, 2, -1, 1, -2, -1, -2, -2, -1, -2, 1, -1, 2 }; //возможные ходы
void show (int n,int nstep) //функция выводит на экран
{
system("cls"); //очистка экрана перед новом выводом на экран
for (int i=0;i<n;++i)
{
for (int j=0;j<n;++j)
{
if (!pole[i][j])
cout<<"* ";
else if(pole[i][j]%10>0) cout<<pole[i][j]<<" ";
else cout<<pole[i][j]<<" ";
}
cout<<'\n';
}
cout<<nstep;cout<<'\n';
}
int set(int startI,int startJ)
{
int x1, y1, q;
for (q = 0; q < 16; q += 2) // перебирает возможные ходы конем
{
x1=startI + xy[q];
y1 = startJ + xy[q + 1];
if (x1 >= 0 && x1 <= (n-1) && y1 >= 0 && y1 <= (n-1) && pole[x1][y1] == 0)
{
nstep++;
pole[x1][y1] = nstep;
if (nstep==n*n) return 1;
show(n,nstep);
if (set(x1,y1)) return 1;
pole[x1][y1] = 0;
nstep--;
}
}
return 0;
}
void main(){
srand((int)time(NULL));
int startI=rand()%n;
int startJ=rand()%n;
pole[startI][startJ]=1; //первый ход
show(n,nstep);
set(startI,startJ);
} |
|
(
