八皇后问题 问题求助

杨延平

刚刚看了小甲鱼老师的视频 不懂  打算代码敲下来调试再理解理解  争取理解递归  现在有个问题求各位大神解决

1：递归解八皇后问题就是暴力枚举每一种结果看合适不合适吗？
2： 如果第一个问题是显然的，，为什么对于所有的行都枚举了（代码10处）  但在主函数只调用了一次EightQueen(0,8,chess);
而不是  调用8次呢

1.        if (8 == row){
2.        输出棋盘
3.        }
4.        else{
5.                //判断这个位置是否有危险
6.                //如果没有危险
7.                        for (j = 0; j < n; j++){
8.                                if (notDanger(row,j,chess2)){
9.                                标记为皇后的位置为1
10.                                        EightQueen(row + 1, n, chess2);//这里对于row+1  行的所有列进行了枚举
11.                        }
12.                }        
13.        }
14.}

再次看了一遍代码  发现是我自己二逼了  我这么问也证明我懂了这个整体的思想
马上自己敲一遍  且桥且珍惜

simple123

这个必须要看看那啊

杨延平

其实在第七行就是在判断  棋盘中第一行的每个字是否安全  然后如果安全 则开始一条以第一行某个列的一种可能 然后再递归第二行  同样  递归的每个节点都先8个节点访问 然后再递归   最后每个节点都遍历到了
把8^8种结果都尝试了一遍   然后筛选出92种

rockerz

回溯只需要用8!次来解。。。4万次计算而已。。

8^8可是1千600多万种结果。。这是穷举的方法。。不是递归
递归和穷举有区别。这个在放皇后之前有用notDanger去查是否可以放，不可以放就直接跳过该格子。具体多少次计算我也不大会算。但这绝对不是穷举的方法。

附上我学过的代码。

1. 
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. #include <cstring>
   
5. 
   
6. int row[8];
   
7. int tc,a,b,solc;
   
8. 
   
9. 
   
10. bool place (int r, int c){
    
11.         for (int prev=0;prev<c;prev++){
    
12.                 if (row[prev]==r||(abs(prev-c)==abs(row[prev]-r)))return false;
    
13.         }
    
14.         return true;
    
15. }
    
16. 
    
17. void backtrack(int n){
    
18.         if (n==8){
    
19.                 printf("第%d种\n",++solc);
    
20.                 for (int j=0;j<8;j++){
    
21.                         for (int i=0;i<8;i++){
    
22.                                 if (row[i]==j)printf ("1 ");
    
23.                                 else printf("0 ");
    
24.                         }
    
25.                         printf("\n");
    
26.                 }
    
27.                
    
28.         }
    
29.        
    
30.         for (int r=0;r<8;r++){
    
31.                 if (place(r,n)){
    
32.                         row[n]=r;
    
33.                         backtrack(n+1);
    
34.                 }
    
35.         }
    
36.        
    
37. }
    
38. int main()
    
39. {
    
40.                 memset(row,0,sizeof(row));
    
41.                 solc=0;
    
42.                 backtrack(0);
    
43.         return 0;
    
44. }
    

复制代码

wangerwanger

首先不是暴力枚举

cable5881

确实是值得思考的一个问题！

网络学习

确实是值得思考的一个问题！

cable5881

撒打算打算打算的