N皇后问题

N皇后问题是给定一个N*N的棋盘，要将N个棋子放入这个棋盘中，但要规定每个皇后不能放在同一行，同一列，也不能放在同一对角线上，问总共有多少中放法。
对于N皇后问题，我们大多数采用的是DFS+剪枝求解。
思路如下：
1）考虑一个棋子能否放在(i,j),那么第i行，第j列不能放有其他棋子容易判断的，而对角线怎么判断呢，设某个点(r,c)放有一个棋子，那么只要|i-r| != |j-c|就行。
2）我们定义一个数组a，a[i] = j表示第i行的第j列放了一个皇后。
3）我们从第一行往最后一行放，对于每一行的点，我们去判断这个是否能放，注意一定是判断前面已经放过皇后的行。如果不能放，那么判断这一行的下一个点，如果能放，那么就继续下一行（这里应该就是一个剪枝），知道所有行全部判断完为止。
具体实现代码如下：

#include <bits/stdc++.h>

using namespace std;

int a[10] = {
   0};
int ans = 0,n;
bool check(int r,int c){
   
	for(int i = 0; i < r; i++){
   
		if(a[i] == c || abs(a[i] - c) == abs(i - r))
		    return false;
	}
	return true;
}

void dfs(int r){
   
	if(r == n){
   
		ans++;
		return;
	}
	for(int i = 0; i < n; i++){
   
		if(check(r,i)){
   
			a[r] = i;
			dfs(r + 1);
		}
	}
}

int main(){
   
	cin >> n;
    dfs(0);
	cout << ans;	
	return 0;
}