n皇后问题-笔记

即在一个n×n的棋盘上摆放n个皇后，使其中任意两个皇后都在不同行同列，也不在一条斜线上。请求出它所有的摆法。（一行一种摆法）
这里我们用的是回溯法
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
优点：程序结构明确，可读性强，易于理解，而且通过减少不必要的重复提高运行效率。
缺点：但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯法，因为它花费的时间比较长。
从n×n的棋盘的第一格开始遍历放第一个皇后，然后在不冲突已经摆放好的皇后的情况下放下一行皇后，一旦冲突就终止，最后将满足放下n个皇后的摆法输出。总体上就是遍历加break。
代码如下：

#include<iostream>
#include<cmath>
using namespace std;
int N;
int queenPos[50];
void NQueen(int k)
{
	int i;
	if( k == N ){//在0~k-行皇后已经摆好的情况下，摆第k行及其后面的皇后 
		for(i=0;i<N;i++)
		    cout<<i+1<<"行"<<queenPos[i]+1<<"列 ";
		cout<<endl;
		return ;
	}
	// 逐个尝试第k个皇后的位置
	for(i=0;i<N;i++){ //列
		int j;
		for(j=0;j<k;j++){//行
			//和已经摆好的k个皇后的位置相比，看是否冲突 
			if( queenPos[j] == i||
			       abs(queenPos[j]-i) == abs(k-j)){//同列或在对角线处 
			       	break;//冲突。则试下一个位置 
			       }
			} 
				if(j == k){//当前的位置i不冲突 
				queenPos[k]=i;//将第k个皇后摆放在位置 i 
				NQueen(k+1);
		}
	} 
}

int main()
{
	cout<<"How many queen?" <<endl;
	cin>>N;
	NQueen(0);
	return 0;
}