洛谷 P1219 [USACO1.5] 八皇后 Checker Challenge

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路参考 大佬?ybb756032937 的个人中心 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

首先 ，

1. N = 1 或 N >= 4 时有解：对于 N = 1 的情况，显然有解，因为只有一个皇后可以放在棋盘的任何位置。对于 N >= 4 的情况，也已被证明有解。例如，4 皇后问题和 8 皇后问题都是经典示例，它们都有多个解。

2. N = 2 和 N = 3 时无解：对于这两个小的 N 值，不可能放置皇后使它们互不攻击。在这两种情况下，皇后的数量太少，无法在避开彼此的攻击范围的同时占满每一行。

3. 所以数据范围保证n>=6,每行肯定可以放下一个皇后

思路 搜索+回溯?

对每一行的位置进行判断，如果符合放下皇后的条件，对该位置进行标记 a数组记录第i行的列号

然后将这个皇后列，两条对角线打上标记?

注意到 两条对角线的性质?

例如?

（1，1） （1，2）（1，3）

（2，1） （2，2）（2，3）

（3，1） （3，2）（3，3）

对于 2，2来说?

1 1 2 2 3 3这条对角线的特点是 每次i+1 ,j+1。所以它的i-j值是保持不变的

我们可以利用这个特点 来标记这条对角线 这样所有i-j为0的位置都不能放皇后

需要注意的是这里是减法 i-j可能为负数 我们需要+n来防止越界

加n这个行为会妨碍我们标记这条对角线吗 答案是不会?

举例 1，2 .? ? ?1-2=-1? 需要加n 1-2+3=2; //标记i-j+n=2

我们要标记的是 1，2 . 2，3这条线?

再看进行判断时?

if((!b[j])&&(!c[x+j])&&(!d[x-j+n]))

d[x-j+n]同样加上了偏移量n

2-3+3=2//与被标记线相同 所以不能放

再说另一条对角线?

1，3 .。2，2。3，1。

这条线的特点是i+j相同?

直接标记即可

再说说回溯?

如果当前这行放置成功 我们会 搜下一行的情况

搜索成功则继续搜 下一行搜索失败则会返回 然后将这一行的标记清除?

往下搜索这一行的可行解?

直至搜索成功?

#include<iostream>
using namespace std;
int n;
const int N=30;
int a[N],b[N],c[N],d[N];
int x=1;
int num=0;
void prinf(){
?? ?if(num<=2){
?? ??? ?for(int i=1;i<=n;i++)
?? ??? ?{
?? ??? ??? ?cout<<a[i]<<' ';
?? ??? ?}
?? ??? ?cout<<endl;
?? ?}
?? ?num++;
?? ?
}

void bfs(int x){
?? ?
?? ?if(x>n)
?? ?{
?? ??? ?prinf();
?? ??? ?return ;
?? ?}else
?? ?{
?? ??? ??? ?for(int j=1;j<=n;j++)
?? ??? ?{
?? ??? ??? ?if((!b[j])&&(!c[x+j])&&(!d[x-j+n])){
?? ??? ??? ??? ?a[x]=j;
?? ??? ??? ??? ?b[j]=1;
?? ??? ??? ??? ?c[x+j]=1;
?? ??? ??? ??? ?d[x-j+n]=1;
?? ??? ??? ??? ?bfs(x+1);
?? ??? ??? ??? ?b[j]=0;
?? ??? ??? ??? ?c[x+j]=0;
?? ??? ??? ??? ?d[x-j+n]=0;
?? ??? ??? ?}
?? ??? ?}
?? ?}
?? ?
}
int main(){
?? ?cin>>n;
?? ?bfs(1);
?? ?
?? ?cout<<num;
?? ?
?? ?return 0;
}