N皇後演算法

最近正在學習回溯法，遇到的第一個問題就是n皇後問題，問題如下：

要求在一個n×n的棋盤上放置n個皇後，使得任意兩個皇後不在同一行或同一列或同一斜線上。

直接上代碼：

#include<iostream>
#include<math.h>
using namespace std;
void NQueen(int, int, int*);

int main()
{
	int x[4] = { -1, -1, -1, -1 }; //4 * 4的棋盤測試
	NQueen(0, 4, x);
	return 0;
}

bool Place(int k, int i, int* x) //用來判斷皇後是否在同一列或者同一斜線，k表示當前行號，i記錄當前的列號，x記錄了當前棋盤信息
{
	for (int j = 0; j < k; j++)
	{
		if ((x[j] == i) || abs(x[j] - i) == abs(j - k))
			return false;
	}
	return true;
}

void NQueen(int k, int n, int* x)
{
	for (int i = 0; i < n; i++) //遍歷當前遞歸到行的所有列號
	{
		if(Place(k, i, x)) //判斷當前位置是否可行
		{
			x[k] = i;
			if (k == n - 1) //如果到了最後一行，說明是一個可行解，輸出
			{
				for (int j = 0; j < n; j++)
				{
					cout << x[j] << " ";
				}
				cout << endl;
			}
			else //深度優先進入下一層遞歸
			{
				NQueen(k + 1, n, x);
			}
		}
	}
	return;
}