【递归】N皇后问题

题目描述：

在n×n 格的棋盘上放置彼此不受攻击的n 个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2 个皇后不放在同一行或同一列或同一斜线上。

设计一个解 n 后问题的队列式分支限界法。计算在n*n个方格上放置彼此不受攻击的n个皇后的一个放置方案。

输入格式：

1 个正整数n

输出格式:

输出计算出的彼此不受攻击的n个皇后的一个放置方案。

输人样例：

5

输出样例

1 3 5 2 4

解题思路：

记录下已经摆放完成的n-1个皇后的列序号，对比当前的列序号、行号、斜对角（处于同一斜对角线的两个皇后的列序号和行号的差一样）的是否一致，如果一致不能摆放。直到最后一个摆放完成即可。

AC代码：

#include<iostream>
#include<cmath>
using namespace std;
int n;//输入数据 
int option[100];//保存每一个皇后所在的列号 
int flag=0;
void putQueen(int k){
	if(k==n&&!flag){
		for(int i=0;i<n;++i)
			cout<<option[i]+1<<" ";
		cout<<endl;
		flag++;
	}
	for(int i=0;i<n;++i){
		int j;
		for(j=0;j<k;++j){//和已经摆放好的k个皇后进行比较 
			if(i==option[j] || abs(k-j)==abs(i-option[j])){
				break;
			} 
		}
		if(j==k){
			option[k]=i;
			putQueen(k+1);
		}
	}
	return;
}
int main() {
	cin>>n;
	putQueen(0);
	return 0;
}