八皇后问题与回溯法

spy

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <time.h>
   
4. #include <conio.h>
   
5. 
   
6. /* 此程序在vc6.0下编译运行是正确的，
   
7.     在vs2008上编译成功，但运行会出现stack overflow !
   
8.     高版本的编译器默认分配的的栈空间小一些，
   
9.     应该可以在编译器里设置默认分配的栈的大小的,
   
10.     如果不能设置的话可以将皇后个数减少。
    
11. */
    
12. 
    
13. //NUM大于8时, 频繁的递归调用会造成栈空间溢出
    
14. #define NUM 8  //8个皇后
    
15. 
    
16. void SolveQueen(char (*)[NUM], int, int);
    
17. int NotSafety(char (*)[NUM], int, int);
    
18. void MoveBack(char (*)[NUM], int, int);
    
19. void ShowQueen(char (*)[NUM]);
    
20. 
    
21. int cnt = 0;
    
22. clock_t start, finish;
    
23. 
    
24. void main()
    
25. {
    
26.         char chess[NUM][NUM];
    
27.         int i, j;
    
28.         for(i=0; i<NUM; i++)  //初始化棋盘
    
29.         {
    
30.                 for(j=0; j<NUM; j++)
    
31.                 {
    
32.                         chess[j] = '0';
    
33.                 }
    
34.         }
    
35.         start = clock();
    
36.         SolveQueen(chess, 0, 0);   //从(0,0)开始搜索
    
37. }
    
38. 
    
39. //NUM个皇后依次放置放到第0列到第NUM-1列的相应位置, 第j列上的皇后具体位置的确定需依次遍历第0行到第NUM-1行, 若第i行安全, 皇后位置chess(i,j)=1
    
40. void SolveQueen(char (*chess)[NUM], int i, int j)
    
41. {
    
42.         while(i<NUM)
    
43.         {
    
44.                 if( !NotSafety(chess, i, j) )  //当前位置安全
    
45.                 {
    
46.                         *(*(chess+i)+j) = '1';  //置棋盘元素chess(i,j)=1
    
47.                         if(j==NUM-1)  //找到一种方案
    
48.                         {
    
49.                                 ShowQueen(chess);  //将位置打印出来
    
50.                                 chess[j] = '0'; //清0, 准备搜索下一行
    
51.                         }
    
52.                         else
    
53.                         {
    
54.                                 SolveQueen(chess, 0, j+1);  //搜索下一列
    
55.                         }
    
56.                 }
    
57.                 i++;  //当前行不安全, 向下移动一行
    
58.         }
    
59.         if(i==NUM)  //当前列都不安全
    
60.         {
    
61.                 MoveBack(chess, 0, j-1);  //向前回溯一列
    
62.         }
    
63. }
    
64. 
    
65. //判断当前位置是否安全, 若不安全返回1, 否则返回0
    
66. int NotSafety(char (*chess)[NUM], int i, int j)
    
67. {
    
68.         //判断同一行是否安全
    
69.         int m, n;
    
70.         m = j-1;
    
71.         if(m>=0) //←
    
72.         {
    
73.                 while( m>=0 && chess[m--]!='1' );
    
74.                 if(chess[++m]=='1')
    
75.                 {
    
76.                         return 1;
    
77.                 }
    
78.         }
    
79. 
    
80.         //判断主对角线是否安全
    
81.         //左上方
    
82.         m = i-1;  //↑
    
83.         n = j-1;  //←
    
84.         if(m>=0 && n>=0)
    
85.         {
    
86.                 while(m>=0 && n>=0 && chess[m--][n--]!='1');
    
87.                 if(chess[++m][++n]=='1')
    
88.                 {
    
89.                         return 1;
    
90.                 }
    
91.         }
    
92. 
    
93.         //判断次对角线是否安全
    
94.         //左下方
    
95.         m = i+1;  //↓
    
96.         n = j-1;  //←
    
97.         if(m<NUM && n>=0)
    
98.         {
    
99.                 while(m<NUM && n>=0 && chess[m++][n--]!='1');
    
100.                 if(chess[--m][++n]=='1')
     
101.                 {
     
102.                         return 1;
     
103.                 }
     
104.         }
     
105.         return 0;
     
106. }
     
107. 
     
108. //回溯至前一列, 继续对该列未搜索的行进行搜索
     
109. void MoveBack(char (*chess)[NUM], int i, int j)
     
110. {
     
111.         while(chess[i++][j]!='1');  //找到之前搜索的行
     
112.         chess[--i][j] = '0';  //该行无效
     
113.         if(i==NUM-1 && j-1>=0)  //若该列的所有行都无效, 则继续回溯前一列; j-1>=0 表示当前列j=0 时就不能再向前回溯了, 因为回溯至0-1=-1列无意义
     
114.         {
     
115.                 MoveBack(chess, 0, j-1);
     
116.         }
     
117.         if(i==NUM-1 && j-1<0)  //若回溯到chess(NUM-1,0)则所有解法已全部遍历结束, 终止程序运行
     
118.         {
     
119.                 finish = clock();
     
120.                 printf("\n%d皇后问题的解共有%d个!\n",NUM, cnt);
     
121.                 printf("\n耗时%ldms\n", finish-start);
     
122.                 _getch();
     
123.                 exit(0);
     
124.         }
     
125.         SolveQueen(chess, i+1, j);  //搜索下一行
     
126. }
     
127. 
     
128. void ShowQueen(char (*chess)[NUM])
     
129. {
     
130.         int i, j;
     
131.         printf("\n第%d种方案 :  ", ++cnt);
     
132.         putchar('\n');
     
133.         for(i=0; i<NUM; i++)
     
134.         {
     
135.                 for(j=0; j<NUM; j++)
     
136.                 {
     
137.                         printf("%c ", *(*(chess+i)+j));
     
138.                 }
     
139.                 putchar('\n');
     
140.         }
     
141. }
     

复制代码

robinshie

{:1_1:}

Furk

刚看完这个视频

vank

感谢额 我看看学习学习

逆战时代

看看。。。。。。。。。。。

vanentu

LZ好人。。。。。。。。。

fuckyou

lz好人

溯月0503

好牛呀

逆战时代

顶、、、、、、、、、

小学期

sgoyi

秒速五厘米

问一下，我用vs2013运行的时候为什么会出现10个错误啊？

溯月0503

为什么运行会出现错误？？？？？？？？

秒速五厘米

溯月0503 发表于 2015-6-19 21:13
为什么运行会出现错误？？？？？？？？

你运行的时候有没有错误呢？

溯月0503

秒速五厘米 发表于 2015-6-20 22:23
你运行的时候有没有错误呢？

有呀   你运行了吗

秒速五厘米

溯月0503 发表于 2015-6-21 09:00
有呀   你运行了吗

我的错误不是截图了吗？你没看到？

溯月0503

秒速五厘米 发表于 2015-6-21 12:24
我的错误不是截图了吗？你没看到？

好吧   刚看到  我也是   解决了嘛？？？？？？？？？？？

秒速五厘米

菜鸟一个，解决不了！！！靠你了！

秒速五厘米

溯月0503 发表于 2015-6-22 09:59
好吧   刚看到  我也是   解决了嘛？？？？？？？？？？？

菜鸟一个，解决不了！！！靠你了！

溯月0503

:sad

565335545

溯月0503 发表于 2015-6-24 09:03

啥东西