关于N皇后问题的思考

N皇后问题

题目：输入整数n，要求n个国际象棋的皇后，摆在n*n的棋盘上，不能互相攻击，输出全部方案。 eg. Input: 4 OutPut: (1,2) (2,4) (3,1) (4,3) (1,3) (2,1) (3,4) (4,2)

介绍

初做此题，由于没有玩过国际象棋(chess)，很是尴尬，于是查了国际象棋的规则，详细内容如下： 以上超链接对应网站和下面的图片均来自维基百科

其中王后queen最为强大，横竖对角线均可以走，步长不限。 要使王后们不相互攻击，发生甄嬛传里面的那些事情，就要把这些女人们妥善安排，否则很容易出幺蛾子。

那么，如何写这个程序呢？

首先，我们人工模拟一下，以4 × imes × 4的方形矩阵为例，按理说应该是4个皇后。

步骤

首先从第一行第一列开始(假设左上角为第一行第一列)开始，从上到下，从左到右遍历。(1,1)处为第一个可行皇后，到第二行，发现(2,1)不行(同一列)，(2,2)不行(对角线)，先把这老女人放在(2,3)吧，不要生事。 却发现由于前面两个女人的骚操作，第三行已经再容不下别人，唉！太过分了，重新给第二行女子安排： 判断方法与上面类似，发现第四个小女子无法进入隔间，生死两茫茫，不思量，自难忘。

于是只能让首个入宫之女让步第二列，之后按照上述步骤，发现出现了一种可行方案：

思路已经很明确了：通过递归、枚举来遍历每一个格子，想办法让所有皇后相安无事，大家一起和睦相处。

代码

先奉上代码，采用C++(本人一直习惯采用英文注释，个人风格)

#include <iostream>
#include <cmath>
using namespace std;
int N;
int queenPos[100];//store the well-put queen, column
void NQueen(int k);//k, line
int main()
{
          
   
	cin>>N;
	NQueen(0);//put the queen from zero line
	return 0;
}
void NQueen(int k)//After finished 0~k-1 queens, then put k and after k queens 
{
          
   
	int i;//i,column
	if(k==N){
          
   //finished N queens
		for(i=0;i<N;i++)
				cout<<"("<<i+1<<","<<queenPos[i]+1<<") ";//column of line i queen
		cout<<endl;
		return;	
	}
	for(i=0;i<N;i++){
          
   //try every k_th line queen,i, column
		int j;//previous well-put j_th line queen
		for(j=0;j<k;j++){
          
   //0~k-1 line queens, j, line
		//compare with the well-put k queen and see whether conflict
			if(queenPos[j]==i||
				abs(queenPos[j]-i)//Delta_column of line k queen and line j queen
				==abs(k-j))//Delta_line of line k queen and line j queen
				break;//conflict, test next position
		}
		if(j==k){
          
   //present position i does not conflict
			queenPos[k]=i;//put queen k into column i
			NQueen(k+1);
		}
	}
}

说明

注释已经写得和详细了，这里念叨三下，关于这个NQueen()函数的三个部分：

1. 当所有N个皇后摆放好，依次输出
2. 从第i列(0-N)遍历，看第j行(0-k)，比较第k个皇后是否与前0-k-1个冲突(横竖对角线)
3. 若不冲突，将i赋给第k行对应的列，此为皇后位置

说明一下，如果没有找到符合条件的皇后，则退回改变i的值，就像我手绘的三张图(1,2->3)一样。

运行结果

如有错误，不吝指出。