八皇后问题求助
  • 板块学术版
  • 楼主Pangding
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/2/10 23:22
  • 上次更新2023/10/24 01:11:59
查看原帖
八皇后问题求助
471585
Pangding楼主2023/2/10 23:22

这是我最开始的思路,非常的离谱和拉胯,但是希望有大神能够解决一下[感谢]

我的思路是按照ij双重循环的嵌套顺序来回溯,从而得出结论,但是最后只求解得出了一个解,以后的结果一直重复输出一种解法,像这样。

1
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
2
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
3
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)

最开始我以为是回溯出了问题,卡住了,但是后来经过调试后发现,这是因为我的思路中一个解的不同个皇后可能是在不同的k(第几个皇后)中放置的,所以答案都一样,但是经过不同的回溯,这样的话就有2×C(2,64)种可能性,具体可以看下面,就是各个步骤之间只颠倒了顺序

1
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
第7个皇后被放置在(85)
第8个皇后被放置在(77)
2
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
第7个皇后被放置在(64)
第8个皇后被放置在(85)
3
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
第7个皇后被放置在(85)
第8个皇后被放置在(64)
4
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
第7个皇后被放置在(64)
第8个皇后被放置在(77)

就卡在这里解决不了了,有没有大佬可以帮忙解决一下 知道问题所在,但是不会修改 源代码:

#include<bits/stdc++.h>
using namespace std;
int answer[9][9]; //储存答案 
int ans;//答案数量 
struct node {
    int x,y;
} node[9];//已经放置的皇后 
bool place(int x,int y,int k) {//判断是否能被放置 
    for(int i=1; i<=8; i++) {
        if(node[i].x==x||node[i].y==y||(abs(node[i].x-x)==abs(node[i].y-y))) {
            return false;
        }
    }
    if(k>=7)
    cout<<"第"<<k<<"个皇后被放置在("<<x<<","<<y<<")"<<endl;
    return true;
}
void dfs(int k) {
    if(k==9) {//输出 
        ans++;
        cout<<ans<<endl;
        for(int i=1; i<=8; i++) {
            for(int j=1; j<=8; j++) {
                if(answer[i][j])cout<<"("<<i<<","<<j<<") ";
            }
            cout<<endl;
        }
        return;
    }
    for(int i=1; i<=8; i++) {//双重循环放置 
        for(int j=1; j<=8; j++) {
            if(place(i,j,k)) {
                node[k].x=i;
                node[k].y=j;
                answer[i][j]=9;
                dfs(k+1);//递归 
                answer[i][j]=0;//回溯 
                node[k].x=11;//这里11,13是为了防止误判断某地不能放皇后(0,0)和(1,1)在同一条直线上 
                node[k].y=13;
            }
        }
    }
}
int main() {
    for(int i=1;i<=8;i++){
        node[i].x=11;node[i].y=13;//同上 
    }
    dfs(1);
    cout<<ans;
    return 0;
}
2023/2/10 23:22
加载中...