[源码]关于八皇后问题的解决（深度优先搜索）

LindiX

这东西可以稍微有点贪心法上去，加快速度。

shooting

这个应该是遍历吧，怎么个贪法？人家可是要所有解的～～一般只有用到最有解才有的贪吧？

JAY

让我想起了骑士周游...

knightgamezz

这个是找出所有解的程序，怎么用贪心？

冰渊

MS有种非递归算法 好象在 郑启华的《pascal程序设计（第二版)》清华大学出版社出版里有介绍，忘了怎么写了。。。

冰渊

其实是我学编程时的一道入门题

liuzhedash

引用第5楼szskx于2007-01-20 13:19发表的“”:
MS有种非递归算法 好象在 郑启华的《pascal程序设计（第二版)》清华大学出版社出版里有介绍，忘了怎么写了。。。

是回朔法吧，方法就是遍历每一种摆法，然后用递归打印结果，贪心找不到所有解。我还记得pascal源码，有人要吗？

knightgamezz

众所周知的八皇后问题就是在一个8*8的棋盘上放8个皇后，让她们不能互相攻击，求出所有满足条件的情况。

2. input: n
3. output: all answers
5. 以下是源码：
6. #define MAXN 16
7. int n;
8. int nsol,nprinted;
9. char row[MAXN];
10. char col[MAXN];      
11. char updiag[2*MAXN];
12. char downdiag[2*MAXN];
14. void solution()
15. {
16. int i;
17. for(i=0; i<n; i++)
18.   {
19.   if(i!= 0) printf(" ");
20.   printf("%d",row[i]+1);
21.   }
22. printf("\n");
23. }
25. void nway(i,lim)
26. {
27. int j;
28. if(i==n)
29. {
30.   nsol++;
31.   if (n>6&&row[0]<n/2) nsol++;
32.   if (nprinted++<3) solution();
33.   return;
34. }
35. for(j=0; j<lim; j++)
36. {
37.   if(!col[j]&&!updiag[i+j] && !downdiag[i-j+MAXN])
38.   {
39.   row[i] = j;
40.   col[j]++;
41.   updiag[i+j]++;
42.   downdiag[i-j+MAXN]++;
43.   nway(i+1,n);
44.   col[j]--;
45.   updiag[i+j]--;
46.   downdiag[i-j+MAXN]--;
47.   }
48. }
49. }
51. int main()
52. {
53. scanf("%d",&n);
54. nway(0,n>6?(n+1)/2:n);
55. printf("%d\n",nsol);
56. return(0);
57. }

复制代码

在游戏开发中，也许有时会用到这种算法（如：迷宫问题），希望对大家有帮助。