回溯法之n皇后有关问题
回溯法之n皇后问题
#include<iostream>
#include<string.h>
#include<string>
#define N 20
using namespace std;
bool vis[3][N];
int sum,a[10];
int n;
void dfs(int cur)
{
if(cur==n){sum++;return;}
for(int i=0;i<n;++i)
if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+n])
{
a[cur]=i;
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=true;
dfs(cur+1);
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+n]=false;
}
}
int main()
{
while(cin>>n)
{
memset(vis,false,sizeof(vis));
sum=0;
dfs(0);
cout<<sum<<endl;
}return 0;
}