洛谷P1219 [USACO1.5]八皇后 Checker Challenge（回溯深搜）

题目链接：https://www.luogu.com.cn/problem/P1219；

n皇后问题我们前面已经讲过，这个题在原来的基础上要求输出前三个解的具体放置方法，所以稍稍会有些不同

这里采用的是回溯标记法，即用数组来储存解的同时，标记已经求解过的数组，然后回溯清0，重新来过。

比较深刻的解释就是：

为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回上一步重新选择条件，继续向前探索，如此反复进行，直至得到解或证明无解。

Ta的特点如下：

1.可以在借助系统栈储存状态

2.空间为O(深度)

3.可以剪枝

4.比较容易实现

5.不易判重

这个就是我们在这道题中的主要思路。如果在准备放置皇后的时候发现，这一行都没有合适的位置，那么我们就“报错”：退回上一状态，重新来过。

为了让皇后们可以吃“后悔药”，我们就必须给她们留下后路——曾经打过标记的地方都撤销掉，让她们有路可回。

tip：

对于左对角线来讲横纵坐标的和是一定的，而右对焦线的行列之差是一定的，但是为了确保行列之差是个正数，我们需要在加上一个n以保证恒正。

另外，数组最好开大一点

参考代码及注意事项如下：

 1 #include
 2 using namespace std;
 3 int n,ans=0;
 4 int row[1500];//表示第i行第j列 放皇后
 5 int col[1500];//储存列
 6 int l[1500];//储存左对焦线，表示left
 7 int r[1500];//储存右对焦线，表示right 
 8 void print()
 9 {
10     ans++;
11  if(ans<=3)
12  {
13      for(int i=1;i<=n;i++)
14      cout<" ";
15      cout<<endl;
16  }//输出前三组解
17 }
18 void dfs(int i)
19 {
20  if(i>n)
21  {
22      print();
23      return ;
24  }
25  for(int j=1;j<=n;j++)
26  {
27      if(col[j]==0&&l[i+j]==0&&r[i-j+n]==0)//未被标记的 
28      {
29          row[i]=j;//放皇后 
30          col[j]=1;//标记 
31          l[j+i]=1;
32          r[i-j+n]=1;//以上是“占领”操作
33          dfs(i+1);//下一行
34          col[j]=0;//以下是回溯操作
35          l[j+i]=0;
36          r[i-j+n]=0;
37      }
38  }
39 }
40 int main ()
41 {
42      cin>>n;
43      dfs(1);//开始
44      cout<//结束
45      return 0;//告成！
46 }

除此之外，我还在网上了解到一个手动开o2优化的方法：#pragma GCC optimize(2)，o3也是同这个方法差不多。

但是竞赛主办方如果没开就不要写了，容易造成错误。

另外，从今天开始每日一题加强训练并且复习一到三篇博客，要真真正正为自己的acm，蓝桥杯备赛，更是为自己的前途和理想备战了。

写在最后：也许生活没有你想象的这么美好，但请相信，诗会有的，远方也会有的，而你现在所要做的，就是好好努力，好好学习，为了自己的梦想，奔向远方，加油加油！