八皇后问题 问题求助
本帖最后由 杨延平 于 2014-4-17 20:43 编辑刚刚看了小甲鱼老师的视频 不懂打算代码敲下来调试再理解理解争取理解递归现在有个问题求各位大神解决
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.}
再次看了一遍代码发现是我自己二逼了我这么问也证明我懂了这个整体的思想
马上自己敲一遍且桥且珍惜
这个必须要看看那啊 其实在第七行就是在判断棋盘中第一行的每个字是否安全然后如果安全 则开始一条以第一行某个列的一种可能 然后再递归第二行同样递归的每个节点都先8个节点访问 然后再递归 最后每个节点都遍历到了
把8^8种结果都尝试了一遍 然后筛选出92种 回溯只需要用8!次来解。。。4万次计算而已。。
8^8可是1千600多万种结果。。这是穷举的方法。。不是递归
递归和穷举有区别。这个在放皇后之前有用notDanger去查是否可以放，不可以放就直接跳过该格子。具体多少次计算我也不大会算。但这绝对不是穷举的方法。
附上我学过的代码。
#include <cstdio>
#include <cstdlib>
#include <cstring>
int row;
int tc,a,b,solc;
bool place (int r, int c){
for (int prev=0;prev<c;prev++){
if (row==r||(abs(prev-c)==abs(row-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==j)printf ("1 ");
else printf("0 ");
}
printf("\n");
}
}
for (int r=0;r<8;r++){
if (place(r,n)){
row=r;
backtrack(n+1);
}
}
}
int main()
{
memset(row,0,sizeof(row));
solc=0;
backtrack(0);
return 0;
}
首先不是暴力枚举 确实是值得思考的一个问题！ 确实是值得思考的一个问题！ 撒打算打算打算的
页:
[1]