八皇后


题意：就是说在n*n的方格中摆放n个皇后，保证方格中每一行、每一列、两条对角线以及与对角线平行区域有且只有一个皇后。对于所有的方案按字典序排序（如果不理解看题目解释），输出前3个方案然后再输出总方案数。
解题思路:（前言）一般对于这种类似于迷宫而且数据大小比较小的题目，我们可以采用dfs的方法。
抛开一切方法，我们用数学思维来考虑这个问题。首先，我们可以假想一个6 * 6的方格。（1,1）（方格的第一行第一列）放一个皇后，然后把与（1,1）位置冲突的位置标记1次。（冲突的位置就是每一行、每一列以及两条斜线）标记完之后，我们就看一下第二行，（2,1）与（2,2）的位置已经被标记1次然而（2,3）位置没有被标记，所以我们就标记（2,3）这个位置，然后把与（2,3）位置冲突的位置再标记1次（标记次数+1）。---->>>这个是不是与递归很像呢？是的这个过程就是dfs的深搜，但是还没有分析回逆与深搜结束。我们先看一下回逆过程，假如我们搜素（i,j）的时候，发现i+1的每一个位置都被标记过，这时候我们就要先把（i,j）位置冲突的位置标记数-1（对于标计数为0的，我们就不需要减去1，这是因为这个这个位置只是受（i,j）的影响），这个过程就是回逆。深搜结束是当搜到第n行的时候有值。
细节之处：字典排序输出（可以利用dfs(1,1),dfs(1,2)…dfs(1,n))

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,ans=0,b[15],vis[15][15];//ans记录方案数 b数组记录的是每一行的列数 vis数组记录的是标记数目（特殊位置）
void dfs(int row,int line){
if(row==n){
        b[n]=line;
    ans++;
    if(ans<=3){
        for(int j=1;j<=n;j++)
            printf("%d%c",b[j],j!=n?' ':'\n');
    }//dfs深搜结束
    return ;
}
b[row]=line;//记录当前行所标记的列数
for(int j=1;row+j<=n&&line+j<=n;j++)
    vis[row+j][line+j]++;
for(int j=1;row+j<=n&&line-j>=1;j++)
    vis[row+j][line-j]++;
for(int i=1;row+i<=n;i++)
    vis[row+i][line]++;
//做特殊位置标记
for(int j=1;j<=n;j++){
    if(vis[row+1][j]==0){
        dfs(row+1,j);
    }
}
for(int j=1;row+j<=n&&line+j<=n;j++)
{
    if(vis[row+j][line+j]>0)
    vis[row+j][line+j]--;
}
for(int j=1;row+j<=n&&line-j>=1;j++){
    if(vis[row+j][line-j]>0)
    vis[row+j][line-j]--;
}
for(int i=1;row+i<=n;i++){
        if(vis[row+i][line]>0)
    vis[row+i][line]--;
}//回逆
return ;
}
int main()
{
    int j=1;
    scanf("%d",&n);
    for(;j<=n;j++)
    dfs(1,j);//字典排序
    printf("%d\n",ans);
    return 0;
}

反思：对于dfs的题目我们可以先自己模拟一下过程，看是不是有过程重复，然后看有没有回逆过程。如果有的话，我们就可以使用dfs.