递归——N皇后

用递归替代多重循环

什么是N皇后：

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

#include <iostream>
#include <cmath>
using namespace std;
int N;
int queenPos[100];//记录每一横行中，皇后所放的列位置
void NQueen(int k);
 
int main( )
{
	cin >> N;
	NQueen(0);//从数组起始位置开始，进行递归求解
}
 
void NQueen(int k)
{
	if (k == N)
	{
		for (int i = 0; i < N; i++)
			cout << queenPos[i] + 1 << " ";
		cout << endl;
	}
	else
	{
		for (int i = 0; i < N; i++)//当前行遍历所有列的皇后位置是否可行,i+1位列位置
		{
			int j;
			for (j = 0; j < k; j++)//与已排列好的皇后的位置进行对比,k为已排列好的数
			{
				if (queenPos[j] == i || abs(queenPos[j] - i) == abs(k - j))
					break;//如果当前皇后所放置的位置与已知皇后的位置发生冲突，则跳出循环
			}
			if (j == k)
			{
				queenPos[k] = i;
				NQueen(k + 1);//正向递归求解k+1
			}
		}
	}
}