递归思想完成n皇后问题

已经很长时间不敲代码了，感觉自己越来与颓废，所以现在又想做回一名苦逼的程序员，开启自己的代码之路。

我是根据视频敲的，没有题目，先看个四皇后问题吧。

所谓4皇后问题就是求解如何在4×4的棋盘上无冲突的摆放4个皇后棋子。在国际象棋中，皇后的移动方式为横竖交叉的，因此在任意一个皇后所在位置的水平、竖直、以及45度斜线上都不能出现皇后的棋子，例子

要求编程求出符合要求的情况的个数

n皇后问题就是将4转化为变量n。

用递归的方法首先要找到递归出口，这里我设用k循环所有行N，当k=N时，循环结束。这里的k表示前0~k-1行已经放置好了，没毛病。

出口判断好了之后就是找判断条件，就是上文中红色字体。

具体代码如下：

#include <iostream> #include <cmath> using namespace std; int N; int queenPos[100]; void NQueen(int k); int main() { cin>>N; NQueen(0); return 0; } void NQueen(int k){ int i; if(k==N){ for(i=0;i<N;i++) cout<< queenPos[i]+1 << " "; cout<<endl; return; } for(i=0;i<N;i++){ int j; for(j=0;j<k;j++){ if(queenPos[j]==i||abs(queenPos[j]-i)==abs(k-j)){ break; } } if(j==k){ queenPos[k]=i; NQueen(k+1); } } }