N皇后問(wèn)題的一種特殊解

張澤宇

摘 要：本文將大于3的自然數(shù)分成5個(gè)部分，對(duì)每一部分的N給出了構(gòu)造N皇后問(wèn)題特解的一種模式，并對(duì)每一種模式都給出了描述公式，以方便計(jì)算機(jī)上的編程實(shí)現(xiàn)。

關(guān)鍵詞：8皇后；特解；N皇后

一、引言

8皇后問(wèn)題是數(shù)學(xué)家Gauss在1850年提出來(lái)的。人們使用回溯的方法在計(jì)算機(jī)上求出了該問(wèn)題的全部92種解。

N皇后問(wèn)題是從8皇后問(wèn)題引申而來(lái)的。8皇后問(wèn)題要求在國(guó)際象棋88的棋盤(pán)上放置8個(gè)皇后，使得任意兩皇后都不能吃掉對(duì)方，即她們都不在同一行、同一列、同一對(duì)角線上。N皇后問(wèn)題時(shí)將棋盤(pán)擴(kuò)展至N×N（N>3），在其上放置N個(gè)皇后，使得任意兩皇后都不能吃掉對(duì)方。

文獻(xiàn)[1]中將N>3分成7個(gè)部分，對(duì)于每一部分的N給出了N皇后問(wèn)題的一種解。而在文獻(xiàn)[2]中將N>3分成了5個(gè)部分，對(duì)每一部分也給出了N皇后問(wèn)題的一種解。

本文將N>3分成了與文獻(xiàn)[2]不同的5個(gè)部分，對(duì)于每個(gè)部分使用不同的模式來(lái)構(gòu)造特解，并給出了每種模式下皇后的擺放位置公式。

二、N皇后問(wèn)題的特解

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

1.Method 1

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

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

2i-n-1 i>n/2

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

2.Method 2

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

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行上的皇后所在的列；行和列編號(hào)均從1開(kāi)始。

3.Method 3

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

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行上的皇后所在的列；行和列編號(hào)均從1開(kāi)始。

4.Method 4

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

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行上的皇后所在的列；行和列編號(hào)均從1開(kāi)始。

5.Method 5

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

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行上的皇后所在的列；行和列編號(hào)均從1開(kāi)始。

對(duì)于n皇后問(wè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代表自然數(shù)。

這里將所有可能的n分成8個(gè)集合，每個(gè)集合采用以上5種模式中的一種來(lái)構(gòu)造特解。

三、結(jié)論

本文給出了n皇后問(wèn)題在n所有可能取值范圍內(nèi)的特解，給出了構(gòu)造特解所用的5種模式，并給出了每種模式下皇后的擺放位置公式，方便計(jì)算機(jī)的編程實(shí)現(xiàn)。

參考文獻(xiàn)：

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

[2]鄔家邦.N皇后問(wèn)題的一種解[J].華中理工大學(xué)學(xué)報(bào)，1994（22）：195-198.