N皇後問題（八皇後問題）

八皇後問題，是一個古老而著名的問題，是回溯算法的典型案例。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

在這裡我們解決的是N皇後問題，即在一個n*n的棋盤上，擺放n個皇後，使之不互相攻擊。問有幾種擺放方法（不考慮棋盤的對稱性）：

對于8皇後問題，我們可以通過8重循環的回溯算法解決，但是對于N皇後，我們無法預知N的值，是以不能使用這種方法。

但是可以使用遞歸實作循環：每一次遞歸解決一行的皇後擺放位置，使之不與前幾行沖突，之後再遞歸調用自身确定下一行的位置。

代碼如下（C++）：

#include <iostream>
using namespace std;

int N;                    //N個皇後
int queen_pos[100];       //每個皇後的位置，目前最大範圍是100
int num = 0;              //統計最終擺放位置方案的個數
void queen(int k);        //遞歸函數

int main()
{
	cin >> N;  //輸入N
      	queen(0); //從第0行開始擺放
	cout << num << endl;    
	system("pause");
	return 0;
}

/*
@brief：遞歸實作每一行皇後的擺放位置
@parameter：K：從第K行開始擺放
*/
void queen(int k)		
{
	if (k==N)        //擺滿N行輸出                                  
	{
		for (int i = 0; i < N; i++)
		{
			cout << queen_pos[i] + 1<<" ";  //列數+1，因為棋盤從第一列開始
		}
		cout << endl;
		num++;         //統計量+1
	}
	for (int i = 0; i < N; i++）     //枚舉皇後所在的列數	
	{
		int j = 0;
		for (; j < k; j++ ）      //是否與前幾行沖突
		{
                        //與前幾行同列 || 與前幾行在同一對角線上，則沖突
			if (queen_pos[j] == i || (abs(queen_pos[j] - i) == k - j))
				break;              //如果沖突，跳出，否定這個位置
		}
		if (j==k)           //如果不沖突
		{
			queen_pos[k] = i;      //确定這一行皇後的位置
			queen(k+1);            //遞歸進入下一行
		}
	}
}
           

以下為用程式求出的所有8皇後的解（92種）：

1 5 8 6 3 7 2 4

1 6 8 3 7 4 2 5

1 7 4 6 8 2 5 3

1 7 5 8 2 4 6 3

2 4 6 8 3 1 7 5

2 5 7 1 3 8 6 4

2 5 7 4 1 8 6 3

2 6 1 7 4 8 3 5

2 6 8 3 1 4 7 5

2 7 3 6 8 5 1 4

2 7 5 8 1 4 6 3

2 8 6 1 3 5 7 4

3 1 7 5 8 2 4 6

3 5 2 8 1 7 4 6

3 5 2 8 6 4 7 1

3 5 7 1 4 2 8 6

3 5 8 4 1 7 2 6

3 6 2 5 8 1 7 4

3 6 2 7 1 4 8 5

3 6 2 7 5 1 8 4

3 6 4 1 8 5 7 2

3 6 4 2 8 5 7 1

3 6 8 1 4 7 5 2

3 6 8 1 5 7 2 4

3 6 8 2 4 1 7 5

3 7 2 8 5 1 4 6

3 7 2 8 6 4 1 5

3 8 4 7 1 6 2 5

4 1 5 8 2 7 3 6

4 1 5 8 6 3 7 2

4 2 5 8 6 1 3 7

4 2 7 3 6 8 1 5

4 2 7 3 6 8 5 1

4 2 7 5 1 8 6 3

4 2 8 5 7 1 3 6

4 2 8 6 1 3 5 7

4 6 1 5 2 8 3 7

4 6 8 2 7 1 3 5

4 6 8 3 1 7 5 2

4 7 1 8 5 2 6 3

4 7 3 8 2 5 1 6

4 7 5 2 6 1 3 8

4 7 5 3 1 6 8 2

4 8 1 3 6 2 7 5

4 8 1 5 7 2 6 3

4 8 5 3 1 7 2 6

5 1 4 6 8 2 7 3

5 1 8 4 2 7 3 6

5 1 8 6 3 7 2 4

5 2 4 6 8 3 1 7

5 2 4 7 3 8 6 1

5 2 6 1 7 4 8 3

5 2 8 1 4 7 3 6

5 3 1 6 8 2 4 7

5 3 1 7 2 8 6 4

5 3 8 4 7 1 6 2

5 7 1 3 8 6 4 2

5 7 1 4 2 8 6 3

5 7 2 4 8 1 3 6

5 7 2 6 3 1 4 8

5 7 2 6 3 1 8 4

5 7 4 1 3 8 6 2

5 8 4 1 3 6 2 7

5 8 4 1 7 2 6 3

6 1 5 2 8 3 7 4

6 2 7 1 3 5 8 4

6 2 7 1 4 8 5 3

6 3 1 7 5 8 2 4

6 3 1 8 4 2 7 5

6 3 1 8 5 2 4 7

6 3 5 7 1 4 2 8

6 3 5 8 1 4 2 7

6 3 7 2 4 8 1 5

6 3 7 2 8 5 1 4

6 3 7 4 1 8 2 5

6 4 1 5 8 2 7 3

6 4 2 8 5 7 1 3

6 4 7 1 3 5 2 8

6 4 7 1 8 2 5 3

6 8 2 4 1 7 5 3

7 1 3 8 6 4 2 5

7 2 4 1 8 5 3 6

7 2 6 3 1 4 8 5

7 3 1 6 8 5 2 4

7 3 8 2 5 1 6 4

7 4 2 5 8 1 3 6

7 4 2 8 6 1 3 5

7 5 3 1 6 8 2 4

8 2 4 1 7 5 3 6

8 2 5 3 1 7 4 6

8 3 1 6 2 5 7 4

8 4 1 3 6 2 7 5