471,873 Members | 2,072 Online

# calculate the horse's movement

12
hi guys,
the problemm is that you have a horse on the chess board.You should write a function that calculate the horse's movement.I mean how many movement later you can go every point on the board.I wrote that program and wanted to share with you...
I am Turkish so I named functions in Turkish.So it can make the source misunderstable sorry for that

//---------------------------------------------------------------------------

Expand|Select|Wrap|Line Numbers
1. #include<stdio.h>
2. #include<conio.h>
3.
4. int control();
5. void test(int,int);
6. int secilecek(int , int );
7. int kucuk(int *);
8. void ekranabas();
9. int hamle=0;
10. typedef struct nokta
11. {
12. int a;
13. int b;
14. } nokta;
15. nokta olasi[8];
16. int x,y,gec,q,indis,temp;
17. int matris[8][8]={0};
18.
19. int main()
20. {
21. x=0;y=0;
22.
23. ekranabas();
24. printf("\n\n\t\tTo watch horse's movement please press any key\n\t\t The starting point is a1");
25. getch();
26. test(x,y);
27.
28. getch();
29. return 0;
30. }
31. //---------------------------------------------------------------------------
32. void test(int x,int y)
33. {
34. for(int v=0;v<8;v++)
35. {
36. olasi[v].a=8;
37. olasi[v].b=8;
38. }
39. if(x+1<8&&(x+1>-1)&&y+2<8&&y+2>-1&&(matris[x+1][y+2]==0))
40. {
41. olasi[0].a=x+1;
42. olasi[0].b=y+2;
43. }
44. if(x-1<8&&x-1>-1&&y+2<8&&y+2>-1&&(matris[x-1][y+2]==0))
45. {
46. olasi[1].a=x-1;
47. olasi[1].b=y+2;
48. }
49. if(x+1<8&&x+1>-1&&y-2<8&&y-2>-1&&(matris[x+1][y-2]==0))
50. {
51. olasi[2].a=x+1;
52. olasi[2].b=y-2;
53. }
54. if(x-1<8&&x-1>-1&&y-2<8&&y-2>-1&&(matris[x-1][y-2]==0))
55. {
56. olasi[3].a=x-1;
57. olasi[3].b=y-2;
58. }
59. if(x+2<8&&x+2>-1&&y-1<8&&y-1>-1&&(matris[x+2][y-1]==0))
60. {
61. olasi[4].a=x+2;
62. olasi[4].b=y-1;
63. }
64. if(x+2<8&&x+2>-1&&y+1<8&&y+1>-1&&(matris[x+2][y+1]==0))
65. {
66. olasi[5].a=x+2;
67. olasi[5].b=y+1;
68. }
69. if(x-2<8&&x-2>-1&&y-1<8&&y-1>-1&&(matris[x-2][y-1]==0))
70. {
71. olasi[6].a=x-2;
72. olasi[6].b=y-1;
73. }
74. if(x-2<8&&x-2>-1&&y+1<8&&y+1>-1&&(matris[x-2][y+1]==0))
75. {
76. olasi[7].a=x-2;
77. olasi[7].b=y+1;
78. }
79.
80. int tut[8];
81. for(int t=0;t<8;t++)
82. {
83. if((olasi[t].a!=8))
84. tut[t]=secilecek(olasi[t].a,olasi[t].b);
85. else
86. tut[t]=9;
87. }
88.
89. matris[x][y]=1;
90. temp=tut[0];
91. for(int t=0;t<8;t++)
92. if((temp>tut[t]||temp==tut[t])&&matris[olasi[t].a][olasi[t].b]==0)
93. temp=tut[t];
94. for(q=0;q<8;q++)
95. if(temp==tut[q])
96. break;
97. x=olasi[q].a;
98. y=olasi[q].b;
99.
100. ekranabas();
101. hamle++;
102.
103. for(int t=0;t<8;t++)
104. tut[t]=9;
105. if(!control())
106. return;
107. test(x,y);
108.
109. }
110.
111. int secilecek(int x, int y)
112. {
113.
114. int say=0;
115. if(x+1<8&&(x+1>-1)&&y+2<8&&y+2>-1&&(matris[x+1][y+2]==0))
116. say++;
117. if(x-1<8&&x-1>-1&&y+2<8&&y+2>-1&&(matris[x-1][y+2]==0))
118. say++;
119. if(x+1<8&&x+1>-1&&y-2<8&&y-2>-1&&(matris[x+1][y-2]==0))
120. say++;
121. if(x-1<8&&x-1>-1&&y-2<8&&y-2>-1&&(matris[x-1][y-2]==0))
122. say++;
123. if(x+2<8&&x+2>-1&&y-1<8&&y-1>-1&&(matris[x+2][y-1]==0))
124. say++;
125. if(x+2<8&&x+2>-1&&y+1<8&&y+1>-1&&(matris[x+2][y+1]==0))
126. say++;
127. if(x-2<8&&x-2>-1&&y-1<8&&y-1>-1&&(matris[x-2][y+1]==0))
128. say++;
129. if(x-2<8&&x-2>-1&&y+1<8&&y+1>-1&&(matris[x-2][y+1]==0))
130. say++;
131. return say;
132. }
133.
134. int kucuk(int *g)
135. {
136.
137. return y;
138. }
139.
140. void ekranabas()
141. {
142. clrscr();
143.
144. printf("\t\t\t   a  b  c  d  e  f  g  h\n");
145. for(int i=0;i<8;i++)
146. {printf("\t\t\t%d ",i+1);
147. for(int j=0;j<8;j++)
148. if((i+j)%2)
149. {
150. if(matris[i][j]==1)
151. printf("xx ");
152. else
153. printf("\xdb\xdb\xdb");
154. }
155. else
156. if(matris[i][j]==1)
157. printf("xx ");
158. else
159. printf("   ");
160. printf("\n");
161. }
162. printf("\n movement that made so far:%d",hamle);
163. for(double g=0;g<9999999;g++);
164.
165.
166. //getch();
167. return ;
168. }
169.
170. int control()
171. {
172. for (int i=0;i<8;i++)
173. for(int j=0;j<8;j++)
174. if(matris[i][j]==0)
175. return 1;
176. return 0;
177. }
Oct 19 '06 #1
1 4326
D_C
293 100+
A horse can only cover one square in one move, and there are 64 squares, you start on 1 initially, so at a minimum it can take 63 movements. You could do this problem recursively and search for a solution.

However, it may depend on the starting place too. If you just need to cover the entire board, it can be done. I suppose minimizing it would be the best answer.

Expand|Select|Wrap|Line Numbers
1. int solve(int chess_board[][], int last_col, int last_row, int count)
2. {
3.   if(count == 64)
4.   {
5.     // print the entire chess board;
6.     // stopping case
7.   }
8.   // up 2, left 1 case
9.   if((last_row > 1) && (last_col > 0))
10.   {
11.     if(chess_board[last_col-1][last_row-2] == 0) // not occupied
12.     {
13.       chess_board[last_col-1][last_row-2] = count;
14.       solve(&chess_board, last_col-1, last_row-2, count+1);
15.       chess_board[last_col-1][last_row-2] = 0;
16.     }
17.   }
18.   // similarly for the other seven possibilities
19. }
20.
21. int main()
22. {
23.   for each row (0 - 7)
24.   {
25.     for each col (0 - 7)
26.     {
27.       chess_board[col][row] = 1;
28.       solve(&chess_board, col, row, 1);
29.       chess_board[row][col] = 0;
30.     }
31.   }
32.   system("PAUSE");
33.   return EXIT_SUCCESS;
34. }
Oct 19 '06 #2