问题描述

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。

问题思路解析

N皇后视频讲解

代码

//#define _CRT_SECURE_NO_DEPRECATE
//#include<bits/stdc++.h>
#include<iostream>

#include<algorithm>
#include<functional>
#include<numeric>
#include<iomanip>

#include<string>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<list>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define IOS ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const long long maxn=1e7+5;
const long long minn=1e2+5;
#define PI acos(-1)
int a[minn];//a[i]表示第i行上的皇后放于a[i]列上，例如：a[3]=7；表示第三行的皇后位于第7列上。
int n;
int ans=0;
bool check(int row,int col){ //判断第row行的皇后能不能放在第col列
	for(int i=1;i<=row;++i){ //从第一行开始判断，一直判断到当前行。后面的行不需要判断，因为每一行就只放一个皇后，后面的行还没有开始放。
		if(a[i]==col) return false; //如果第i行就已经占了col列，表示不能放在col列
		if(i+a[i]==row+col) return false;//如果行和列的之和相等，即在平行与副对角线的斜线上。
		if(i-a[i]==row-col) return false;//如果行和列的之差相等，即在平行与主对角线的斜线上。
	}
	return true;
}
void dfs(int row){ //表示第i行的皇后放于何处
	if(row==n+1) { //当行数超过了所给行，表示有一种解。
		ans++;
		return ;
	}
	for(int i=1;i<=n;++i){
		if(check(row,i)){ //看row行的皇后能不能放在第i列
			a[row]=i;
			dfs(row+1);
			a[row]=0; //回溯
		}
	}
}
void solve(){
	while(cin>>n&&n){
		ans=0;
		dfs(1);
		cout<<ans<<endl;
	}
}
int main(){
	IOS;
	solve();
	return 0;
}