Добрый день , друзья.
Помогите дилетанту .
Не могу разобраться , почему моя рекурсивная функция переполняет кучу.
Тупая реализация классической задачки на обход конем доски. Я правда так и не разобрался пока как закончить её выполнение. Но это не сильно и важно. (на данный момент просто хотелось бы добиться чтобы высветилось хотя бы одно решение, пусть и с зацикливанием)
Пытаюсь даже выводить грубо глубину рекурсии - она теоретически не должна превышать 64 - так и есть.
Однако при длительной работе (а дерево разрастается очень стремительно) высвечивает Java heap space.
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.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
package horses;
import java.util.concurrent.TimeUnit;
public class horse {
int qty_of_hourse = 65;
int [][] x = new int[9][9];
int [] is = new int[65];
int [] js = new int[65];
long depth = 0;
int i_start=1;
int j_start=1;
int horse_count = 1;
public horse() {
x[i_start][j_start]=1;
is[1] = i_start;js[1] = j_start;
System.out.println("start");
print_field();
}
public String try_horse(int current_horse) {
String res="good" ;
int [] moving= new int [2];
int mc=1;
int x1=0;
int y1=0;
depth++;
System.out.println("Глубина = " + depth);
if (current_horse==2) {x1=i_start; y1=j_start; is[current_horse] = x1;js[current_horse] = y1;}
do {
moving = move_horse(mc,is[current_horse-1],js[current_horse-1]);
if (moving[0]!=0 && moving[1]!=0) { //если можно поставить коня
x1 = moving[0];
y1 = moving[1];
x[x1][y1]=current_horse;/*ставим*/
is[current_horse] = x1;
js[current_horse] = y1;
System.out.println("Можно ! Передвигаем коня на "+x1+ " "+y1+", ход №"+current_horse);
print_field();
if (current_horse<=64) { res=try_horse(current_horse+1); }
if (res=="bad") {
System.out.println("Плохо ! Вынуждены убрать коня с "+is[current_horse]+ " "+js[current_horse]);
x[is[current_horse]][js[current_horse]]=0;
is[current_horse]=0;
js[current_horse]=0;
res="good";
}
}
mc++;
if (mc==9) {res="bad";}
} while (!(res=="bad" || mc==9 )) ;
depth--;
return res;
}
public int [] move_horse(int i1 , int i , int j ) {
int [] result= new int [2];
result[0] = 0 ;
result[1] = 0 ;
int is=0;
int js=0;
System.out.println("Попытка "+ i1 +" из 8. проверим можно ли передвинуть с " +i+ " "+ j);
if (i1==1 && i-2>=1 && j-1>=1 && x[i-2][j-1]==0) {is=i-2 ; js=j-1; result[0] = is ;result[1] = js ;
}
if (i1==2 && i-1>=1 && j-2>=1 && x[i-1][j-2]==0) {is=i-1 ; js=j-2; result[0] = is ;result[1] = js ;
}
if (i1==3 && i+1<=8 && j-2>=1 && x[i+1][j-2]==0) {is=i+1 ; js=j-2; result[0] = is ;result[1] = js;
}
if (i1==4 && i+2<=8 && j-1>=1 && x[i+2][j-1]==0) {is=i+2 ; js=j-1; result[0] = is ;result[1] = js;
}
if (i1==5 && i+2<=8 && j+1<=8 && x[i+2][j+1]==0) {is=i+2 ; js=j+1; result[0] = is ;result[1] = js;
}
if (i1==6 && i+1<=8 && j+2<=8 && x[i+1][j+2]==0) {is=i+1 ; js=j+2; result[0] = is ;result[1] = js;
}
if (i1==7 && i-1>=1 && j+2<=8 && x[i-1][j+2]==0) {is=i-1 ; js=j+2; result[0] = is ;result[1] = js;
}
if (i1==8 && i-2>=1 && j+1<=8 && x[i-2][j+1]==0) {is=i-2 ; js=j+1; result[0] = is ;result[1] = js ;
}
return result;
}
public void print_field() {
int i1;
int j1;
for (i1 = 1; i1 <= 8; i1++) {
for (j1 = 1; j1 <= 8; j1++) {
if (x[i1][j1]>0) {System.out.print(x[i1][j1]+" ");}
if (x[i1][j1]<0) {System.out.print("B ");}
if (x[i1][j1]==0) {System.out.print("0 ");}
}
System.out.println();
}
System.out.println();
}
}
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
package horses;
public class main {
public static void main(String args[]) {
horse h = new horse();
h.try_horse(2);
}
}
