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.