骑士周游非完美版。。= =

由于马踏遍棋盘得记录下走过的路径, 并且在不同的时候能够返回到上一个选择节点, 重新选择新的路径, 在最初的几次编写中由于没能够排除之前已经选择的路径导致了死循环, 后来调试分析时才发现问题所在, 最后采用树形图辅助设计程序, 帮助理清了程序不同情况下应做的反应及逻辑顺序. 在每个节点处分配一个栈来储存尚未选择的路径, 供之后回溯时使用.

最后程序代码如下, 但是效率不是很高, 在SIZE 的值比较大时费时较多, 并且对内存的占用也比较厉害, 目前还没有有效的解决办法, 网上虽然有一种贪心算法, 但是那个算法并不完善, 对某些节点无法成功进行运算, 目前采用的是回溯算法, 稍加修改可以算出所有的路径.

PS：有更好的算法的话请指教～～。

试了一下发现将SIZE设为8时，输入“4 5”马上就能找到。。。= A =，其他的可能会很慢了

代码

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <conio.h>
  4 #include <crtdbg.h>
  5 
  6 
  7  #define STACK_INIT_SIZE 10
  8  #define STACKINCREASEMENT 50
  9 #define SIZE 8               //棋盘的大小
 10 
 11 
 12 int Board[SIZE][SIZE] = {0};
 13  
 14 struct step
 15 {
 16      int i;
 17      int j;
 18      struct stack *StepStack;
 19 };
 20  
 21 typedef struct step Step;
 22  
 23 struct stack
 24 {
 25      Step *base;
 26      Step *top;
 27      int stacksize;
 28 };
 29  
 30 typedef struct stack Stack;
 31  
 32 void InitStack(Stack *S)
 33 {
 34      S->base = (Step *)malloc(STACK_INIT_SIZE * sizeof(Step));
 35      S->top = S->base;
 36      S->stacksize = STACK_INIT_SIZE;
 37 }
 38  
 39 void InitStepStack(Step *e)
 40 {
 41      e->StepStack = (Stack *)malloc(sizeof(Stack));
 42      e->StepStack->base = (Step *)malloc(STACK_INIT_SIZE * sizeof(Step));
 43      e->StepStack->top = e->StepStack->base;
 44      e->StepStack->stacksize = STACK_INIT_SIZE;
 45 }
 46  
 47  
 48 void Push(Stack *S, Step e)
 49 {
 50      if (S->top - S->base >= S->stacksize)
 51      {
 52          S->base = (Step *)realloc(S->base, (S->stacksize + STACKINCREASEMENT) * sizeof(Step));
 53          S->top = S->base + S->stacksize;
 54          S->stacksize += STACKINCREASEMENT;
 55      }
 56      *S->top++ = e;
 57 }
 58  
 59 Step Pop(Stack *S)
 60 {
 61      Step e;
 62      e = *(--S->top);
 63      return e;
 64 }
 65  
 66 int Equal(Step a, Step b)
 67 {
 68      if (a.i == b.i && a.j == b.j)
 69          return 1;
 70      else
 71          return 0;
 72 }
 73  
 74 int InStack(Step e, Stack *S)
 75 {
 76      Step *p = S->base;
 77      while (p != S->top)
 78      {
 79          if (Equal(e, *p))
 80               return 1;
 81          p++;
 82      }
 83      return 0;
 84 }
 85  
 86 int EmptyStack(Stack *S)
 87 {
 88      if (S->base == S->top)
 89          return 1;
 90      else
 91          return 0;
 92 }
 93  
 94  
 95 void CreateStepStack(Step *e, Stack *S)
 96 {
 97      int i;
 98      InitStepStack(e);
 99     Step nextstep[8];
100      nextstep[0].i = e->i - 2;
101      nextstep[0].j = e->j + 1;
102      nextstep[1].i = e->i - 1;
103      nextstep[1].j = e->j + 2;
104      nextstep[2].i = e->i + 1;
105      nextstep[2].j = e->j + 2;
106      nextstep[3].i = e->i + 2;
107      nextstep[3].j = e->j + 1;
108      nextstep[4].i = e->i + 2;
109      nextstep[4].j = e->j - 1;
110      nextstep[5].i = e->i + 1;
111      nextstep[5].j = e->j - 2;
112      nextstep[6].i = e->i - 1;
113      nextstep[6].j = e->j - 2;
114      nextstep[7].i = e->i - 2;
115      nextstep[7].j = e->j - 1;
116     for (i = 0; i < 8; i++)
117      {
118          if (nextstep[i].i >= 0 &&
119               nextstep[i].i <= SIZE - 1 &&
120               nextstep[i].j >= 0 &&
121               nextstep[i].j <= SIZE - 1 &&
122               !(InStack(nextstep[i], S)))
123               Push(e->StepStack, nextstep[i]);
124      }
125  
126 }
127  
128 //对节点栈进行排序的一种创建StepStack方式，但是发现效率会更低，因此舍弃不用
129  
130 /*
131  
132 int index(int n[8])
133 {
134      int i, t = -1, min = 10;
135      for (i = 0; i < 8; i++)
136      {
137          if (n[i] != 10 && n[i] < min)
138          {
139               min = n[i];
140               t = i;
141          }
142      }
143      return t;
144 }
145  
146  
147 void CreateStepStack(Step *e, Stack *S)
148 {
149      int i, j, n[8] = {10, 10, 10, 10, 10, 10, 10, 10};
150      InitStepStack(e);
151     Step f, nextstep[8], nextnextstep[8];
152      nextstep[0].i = e->i - 2;
153      nextstep[0].j = e->j + 1;
154      nextstep[1].i = e->i - 1;
155      nextstep[1].j = e->j + 2;
156      nextstep[2].i = e->i + 1;
157      nextstep[2].j = e->j + 2;
158      nextstep[3].i = e->i + 2;
159      nextstep[3].j = e->j + 1;
160      nextstep[4].i = e->i + 2;
161      nextstep[4].j = e->j - 1;
162      nextstep[5].i = e->i + 1;
163      nextstep[5].j = e->j - 2;
164      nextstep[6].i = e->i - 1;
165      nextstep[6].j = e->j - 2;
166      nextstep[7].i = e->i - 2;
167      nextstep[7].j = e->j - 1;
168     for (i = 0; i < 8; i++)
169      {
170          if (nextstep[i].i >= 0 &&
171               nextstep[i].i <= SIZE - 1 &&
172               nextstep[i].j >= 0 &&
173               nextstep[i].j <= SIZE - 1 &&
174               !(InStack(nextstep[i], S)))
175          {
176               f = nextstep[i];
177               nextnextstep[0].i = f.i - 2;
178               nextnextstep[0].j = f.j + 1;
179               nextnextstep[1].i = f.i - 1;
180               nextnextstep[1].j = f.j + 2;
181               nextnextstep[2].i = f.i + 1;
182               nextnextstep[2].j = f.j + 2;
183               nextnextstep[3].i = f.i + 2;
184               nextnextstep[3].j = f.j + 1;
185               nextnextstep[4].i = f.i + 2;
186               nextnextstep[4].j = f.j - 1;
187               nextnextstep[5].i = f.i + 1;
188               nextnextstep[5].j = f.j - 2;
189               nextnextstep[6].i = f.i - 1;
190               nextnextstep[6].j = f.j - 2;
191               nextnextstep[7].i = f.i - 2;
192               nextnextstep[7].j = f.j - 1;
193               for (j = 0; j < 8; j++)
194               {
195                    if (nextnextstep[j].i >= 0 &&
196                        nextnextstep[j].i <= SIZE - 1 &&
197                        nextnextstep[j].j >= 0 &&
198                        nextnextstep[j].j <= SIZE - 1 &&
199                     !Equal(nextnextstep[j], nextstep[i]) &&
200                        !(InStack(nextnextstep[j], S)))
201                    {
202                        if (n[i] == 10)
203                             n[i] = 0;
204                        n[i]++;
205                    }
206               }
207               while (index(n) != -1)
208               {
209                    Push(e->StepStack, nextstep[index(n)]);
210                    n[index(n)] = 10;
211               }
212          }
213      }
214  
215 }
216  
217 */
218  
219  
220  
221 void main()
222 {
223      int t = 0, n, i, j;
224      Step e, f, *p;
225      Stack STACK, *S = &STACK;
226      printf("Input x and y with \"x y\" format  (0<=x<=7,0<=y<=7):\n");
227      scanf("%d %d", &e.i, &e.j);
228      InitStack(S);
229      Push(S, e);
230      while (S->top - S->base < SIZE * SIZE)
231      {
232          if (t == 0)
233               CreateStepStack(S->top - 1, S);
234          else
235               t = 0;
236  
237          if (!(EmptyStack((S->top - 1)->StepStack)))
238          {
239               f = Pop((S->top - 1)->StepStack);       
240               Push(S, f);
241          }
242          else
243          {
244               free((S->top - 1)->StepStack->base);
245               Pop(S);
246               if (EmptyStack(S))
247               {
248                    printf("Error");
249                    return;
250               }
251               t = 1;
252          }
253      }
254      n = 1;
255      p = S->base;
256      while (n <= SIZE * SIZE)
257      {
258          Board[p->i][p->j] = n;
259          n++;
260          p++;
261      }
262      n = 1;
263      for (j = 0; j < SIZE; j++)
264      {
265          for (i = 0; i < SIZE; i++)
266          {
267               printf("%3d", Board[j][i]);
268               if (i == SIZE - 1)
269                    printf("\n");
270          }
271      }
272      getch();
273  
274 }

骑士周游 非完美版。。= =

骑士周游非完美版。。= =