这是我最开始的思路,非常的离谱和拉胯,但是希望有大神能够解决一下[感谢]
我的思路是按照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个皇后被放置在(8,5)
第8个皇后被放置在(7,7)
2
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
第7个皇后被放置在(6,4)
第8个皇后被放置在(8,5)
3
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
第7个皇后被放置在(8,5)
第8个皇后被放置在(6,4)
4
(1,2)
(2,6)
(3,8)
(4,3)
(5,1)
(6,4)
(7,7)
(8,5)
第7个皇后被放置在(6,4)
第8个皇后被放置在(7,7)
就卡在这里解决不了了,有没有大佬可以帮忙解决一下 知道问题所在,但是不会修改 源代码:
#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;
}