n皇后问题

我们首先从第一行开始放，然后对第一个皇后所在的这一行和这一列进行标记，再对四个角的地方进行标记，标记的就是接下来不能放的位置

#include <iostream>
using namespace std;
const int N=15;
int ans=0;
int vis[N][N];//开一个棋盘数组，用来进行标记
int n;
void dfs(int dep)//dep表示行
{
  if(dep==n+1)//当超过n时，也就是完成一次从第一行到最后一行的方案，ans++；
  {
    ans++;
    return;//退出，进入恢复现场，开始下一轮
  }
  for(int i=1;i<=n;i++)//开始遍历列，从第一列开始也就是vis[1][1],，然后是vis[1][2];
  {
    if(vis[dep][i])continue;//如果是标记过的，就跳过
    for(int _i=1;_i<=n;_i++)vis[_i][i]++;//对所在的列进行标记，不用标记所在的行，因为下一次从 
    下一行开始放
    //接下来对四个角所在的直线上的地方进行标记
    for(int _i=dep,_j=i;_i>=1&&_j>=1;_i--,_j--)vis[_i][_j]++;//左上角
    for(int _i=dep,_j=i;_i>=1&&_j<=n;_i--,_j++)vis[_i][_j]++;//右上角
    for(int _i=dep,_j=i;_i<=n&&_j>=1;_i++,_j--)vis[_i][_j]++;//左下角
    for(int _i=dep,_j=i;_i<=n&&_j<=n;_i++,_j++)vis[_i][_j]++;//右下角
    
    dfs(dep+1);//标记完后进入下一行
    
    //这后面的是恢复现场，也就是从第一行遍历到最后一行结束后对n*n的棋盘进行恢复，去掉标记
    //然后从第一行的第二列开始进行下一轮的遍历
    for(int _i=1;_i<=n;_i++)vis[_i][i]--;
    for(int _i=dep,_j=i;_i>=1&&_j>=1;_i--,_j--)vis[_i][_j]--;
    for(int _i=dep,_j=i;_i>=1&&_j<=n;_i--,_j++)vis[_i][_j]--;
    for(int _i=dep,_j=i;_i<=n&&_j>=1;_i++,_j--)vis[_i][_j]--;
    for(int _i=dep,_j=i;_i<=n&&_j<=n;_i++,_j++)vis[_i][_j]--;
  }
}
int main()
{
  cin>>n;
  dfs(1);//从1开始
  cout<<ans;
  return 0;
}