八皇后问题 问题求助

杨延平

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

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去查是否可以放，不可以放就直接跳过该格子。具体多少次计算我也不大会算。但这绝对不是穷举的方法。

附上我学过的代码。

#include <cstdio>
#include <cstdlib>
#include <cstring>

int row[8];
int tc,a,b,solc;


bool place (int r, int c){
        for (int prev=0;prev<c;prev++){
                if (row[prev]==r||(abs(prev-c)==abs(row[prev]-r)))return false;
        }
        return true;
}

void backtrack(int n){
        if (n==8){
                printf("第%d种\n",++solc);
                for (int j=0;j<8;j++){
                        for (int i=0;i<8;i++){
                                if (row[i]==j)printf ("1 ");
                                else printf("0 ");
                        }
                        printf("\n");
                }
                
        }
        
        for (int r=0;r<8;r++){
                if (place(r,n)){
                        row[n]=r;
                        backtrack(n+1);
                }
        }
        
}
int main()
{
                memset(row,0,sizeof(row));
                solc=0;
                backtrack(0);
        return 0;
}

wangerwanger

首先不是暴力枚举

cable5881

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

网络学习

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

cable5881

撒打算打算打算的