N皇后問題的一種特殊解

張澤宇

摘 要：本文將大于3的自然數分成5個部分，對每一部分的N給出了構造N皇后問題特解的一種模式，并對每一種模式都給出了描述公式，以方便計算機上的編程實現。

關鍵詞：8皇后；特解；N皇后

一、引言

8皇后問題是數學家Gauss在1850年提出來的。人們使用回溯的方法在計算機上求出了該問題的全部92種解。

N皇后問題是從8皇后問題引申而來的。8皇后問題要求在國際象棋88的棋盤上放置8個皇后，使得任意兩皇后都不能吃掉對方，即她們都不在同一行、同一列、同一對角線上。N皇后問題時將棋盤擴展至N×N（N>3），在其上放置N個皇后，使得任意兩皇后都不能吃掉對方。

文獻[1]中將N>3分成7個部分，對于每一部分的N給出了N皇后問題的一種解。而在文獻[2]中將N>3分成了5個部分，對每一部分也給出了N皇后問題的一種解。

本文將N>3分成了與文獻[2]不同的5個部分，對于每個部分使用不同的模式來構造特解，并給出了每種模式下皇后的擺放位置公式。

二、N皇后問題的特解

這里給出N皇后問題特解的5種模式，每種模式都有其不同的適應范圍，這些模式適應范圍的并集就覆蓋了所有N皇后問題的特解。

1.Method 1

這種模式中，每個皇后的位置描述為：

a[i]=2i i≤n/2

2i-n-1 i>n/2

其中，a[i]表示第i行上的皇后所在的列；行和列編號均從1開始。

2.Method 2

這種模式中，每個皇后的位置描述為：

a[i]=2i i≤n/2

2i-n+1 i>n/2且i-n/2=1mod2

2i-n-3 i>n/2且i-n/2=0mod2

其中，a[i]表示第i行上的皇后所在的列；行和列編號均從1開始。

3.Method 3

這種模式中，每個皇后的位置描述為：

a[i]=n-1 i=1

2i-2 i>1且i≤n/2+1

2i-n-1 i>n/2+1且i-n/2-1=1mod2

2i-n-5 i>n/2+1且i-n/2-1=0mod2

其中，a[i]表示第i行上的皇后所在的列；行和列編號均從1開始。

4.Method 4

這種模式中，每個皇后的位置描述為：

a[i]=n-1 i=1

n-3 i=2

2i-5 i>2且i≤n/2+2

2i-n-3 i>n/2+2且i-n/2-2=1mod2

2i-n-7 i>n/2+2且i-n/2-2=0mod2

其中，a[i]表示第i行上的皇后所在的列；行和列編號均從1開始。

5.Method 5

這種模式中，每個皇后的位置描述為：

a[i]=2i+1 i≤（n-1）/2

2i-n+3 i>（n-1）/2且i-（n-1）/2=1mod2且i≠n-1

2i-n-1 i>（n-1）/2且i-（n-1）/2=0mod2

1 i=n-1

其中，a[i]表示第i行上的皇后所在的列；行和列編號均從1開始。

對于n皇后問題（n>3），其特解如下：

n=6i-2 method1

6i-1 method1

6i method1

6i+1 method1

12i-4 method2 i∈N

12i+2 method3

12i-3 method4

12i+3 method5

其中，N代表自然數。

這里將所有可能的n分成8個集合，每個集合采用以上5種模式中的一種來構造特解。

三、結論

本文給出了n皇后問題在n所有可能取值范圍內的特解，給出了構造特解所用的5種模式，并給出了每種模式下皇后的擺放位置公式，方便計算機的編程實現。

參考文獻：

[1]Falkowski BJ， Schmitz L.A Note on the QueensProblem. Inform Process Lett[J].1986，23（1）：39-46.

[2]鄔家邦.N皇后問題的一種解[J].華中理工大學學報，1994（22）：195-198.