八皇后

1.简介

如题所示，这是一个类似于枚举的过程：每一行每一行地进行尝试，如果没有皇后能侵犯到自己， 就放置该棋子，同时占据她所能占据的所有领地。最后，在每一行上都各有一个皇后时，就输出答案

2.方法

在这道题中，主要使用的是深搜(DFS)和回溯

回溯：借用以下神子杏大佬的批批替

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

Ta的特点如下：

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

2.空间为O(深度)

3.可以剪枝

4.比较容易实现

5.不易判重

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

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

下面，说下具体的实现方法。

1.地图设置

在这道题当中，我们不采取一般的建图（姑且先用下这个词）方式——建一个二维数组。因为这样的话，我们需要更多的循环来支持占领操作。

我们分别为行、列、左斜线（/)、右斜线(\ ) 单独建立数组。

这样做的好处非常明显：在进行占据操作的时候，只需要在相对应的行、列、左斜、右斜打上标记就行，不需要在每一块都用循环进行操作，节省很多时间

类似这种建图方式的题还有这道，自己尝试一下吧！

行和列的表示都非常简单，只需要在对应格子标记即可，我们来看一下左斜右斜的表示方式

如图：

对于第二行的那个皇后来说，她的右斜线上的点，（1，3），（3，5），（4，6），我们可以看出，它的y-x是个定值2，但是看第四行的皇后的右斜线上的点（5，2），它的y-x是个负定值，而数组是不能存在负数下标的，那怎么办。

把数组向右平移几个单位(在这里平移n就够)

因为右斜线上所有数都向右平移了n，所以总的数组中的关系不变。

同理我们看左斜线上的点，我们发现它们的x+y是个定值（自己找找看） 因为这是个加法，不会出现负数的情况，所以我们不需要在末尾加上n

所以，我们在写的时候可以这样

   ls[i+j]=1;rs[i-j+n]=1

以上就是些基本操作，下面加入代码（我的代码里的左斜和右斜好像写反了）

#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int a[105],ls[105],rs[105],kkk[105];//a:lie,ls:left scope,rs:right scope（原谅我的工地英语），kkk是行（kkksc03不要打我[滑稽]）
void print()
{
    if(ans<=2)
    {
        for(int i=1;i<=n;i++)
        cout<<kkk[i]<<" ";
        cout<<endl;
    }//输出前三组解
    ans++;
}
void dfs(int k)//深搜
{
    if(k>n)
    {
        print();
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!a[i]&&!ls[i+k]&&!rs[i-k+n])
        {
            kkk[k]=i;
            a[i]=1;
            ls[k+i]=1;
            rs[i-k+n]=1;//以上是“占领”操作
            dfs(k+1);//这个是深搜下一行
            a[i]=0;//以下是回溯操作
            ls[k+i]=0;
            rs[i-k+n]=0;
        }
    }
}
int main ()
{
    cin>>n;
    dfs(1);//开始
    cout<<ans<<endl;//结束
    return 0;//大工告成！
}