李 盘 林，　赵 铭 伟，　徐 喜 荣，　李 丽 双，　李 伯 章

( 1.大连理工大学 电子信息与电气工程学部, 辽宁 大连　116024；2. 滑铁卢大学 计算机工程系， 加拿大 安大略　滑铁卢 )



德杰尼斯五后问题求解方法

李 盘 林*1，赵 铭 伟1，徐 喜 荣1，李 丽 双1，李 伯 章2

( 1.大连理工大学 电子信息与电气工程学部, 辽宁 大连116024；2. 滑铁卢大学 计算机工程系， 加拿大 安大略滑铁卢 )

摘要：给出了棋盘坐标表示，定义了皇后控制数或剩余控制数，以及皇后最佳(极佳)或剩余最佳(极佳)位置的概念．利用棋盘对称性，通过有效的计算，先求出了五后问题的3个基础解，进而得到了全部24个解及其图示，并首次给出了最少放置5个而不是4个皇后的证明，以及解的完备性证明．

关键词：五后问题；皇后控制数或剩余控制数；皇后最佳(极佳)或剩余最佳(极佳)位置

0引言

在信息领域，八后问题、五后问题，了解它们的不乏其人．前者由高斯解决[1]，后者就不那么幸运了．都说五后问题但其内涵是不同的(http://cjc.iteye.com/blog/299173；http://wenku.baidu.com/view/c254e769a98271fe910ef965.html)．1862年，德杰尼斯[2](De Jaenisch)研究在8×8棋盘上最少放置几个皇后，它们彼此互不攻击，又能控制其他任意棋子．他给出7个皇后的解，而正确解是5个．为了不忘德杰尼斯的先期工作，将下面论题：在8×8棋盘上最少放置5个皇后，能否使5个皇后各自安全且又能吃掉棋盘上其余任意棋子(皇后占用的五格不同行、或不同列、或不同一对角线，且又能与棋盘上其余格同行、或同列、或同一对角线)称为德杰尼斯五后问题[3]．本文给出上述论题的一种解法．

1求解前的说明

(1)8×8棋盘坐标表示，即对由64个称为格的小正方形构成一个大正方形称为棋盘的给出坐标表示．大正方形的左下顶点为坐标原点O；大正方形的底边为坐标x轴；大正方形的左边为坐标y轴．小正方形的边长为坐标轴的1个单位；小正方形即格S的右上顶点坐标(i，j)作为S的标记，记为Si,j，简记为Sij．记(0，0)与(8，8)的连线为cc；记(0，8)与(8，0)的连线为dd；记(0，4)与(8，4)的连线为aa；记(4，0)与(4，8)的连线为bb．称(4，4)为棋盘的中心点．aa与bb将棋盘划分为4个区域R1、R2、R3和R4．上述说明如图1所示．

(2)第1个皇后Q放在格Sij上，位于与Sij同行、同列和同一对角线上的所有格数，称为皇后Q控制数[4]，记为n(Q|Sij)．使控制数最大的皇后Q所在格Si0j0是唯一的，称Si0j0为皇后Q最佳位置[4]，记为Qi0j0，其控制数记为n(Qi0j0)；若不唯一，比如说Si1j1，Si2j2，…，称这些格为皇后Q极佳位置，记为Qi1j1，Qi2j2，…；其控制数分别记为n(Qi1j1)，n(Qi2j2)，…．

类似地可定义第3个、第4个、…皇后剩余控制数、最佳(极佳)位置．

图1　棋盘定义

2求解及证明

利用棋盘对称性，欲求第1个皇后A最佳(极佳)位置，只需在区域R1内计算位于cc上及其下面每个格的控制数，并求出最大者即可．经过计算，可知皇后A最佳位置是格S44，皇后A最佳位置记为A44，n(A44)=28．

第2个皇后B剩余最佳(极佳)位置，除去与A44同行、同列和同一对角线所有格外，计算每个格的控制数且给出其最大者即可确定．经过计算，共得到6个皇后B极佳位置：S63、S65、S56、S36、S67和S76，分别记为B63、B65、B56、B36、B67和B76，其剩余控制数分别为n(B63)=16，n(B65)=16，n(B56)=16，n(B36)=16，n(B67)=16和n(B76)=16．

在确定A44、B63后，不难求出：

第3个皇后C剩余最佳位置是格S56，皇后C最佳位置记为C56，其剩余控制数是n(C56)=10．

第4个皇后D剩余最佳位置是格S37，皇后D最佳位置记为D37，其剩余控制数是n(D37)=7．

第5个皇后E剩余最佳位置是格S25，皇后E最佳位置记为E25，其剩余控制数是n(E25)=3．

不难看出，4个皇后是不能够控制棋盘的，因为

n(A44)+n(B63)+n(C56)+n(D37)=

28+16+10+7=61

这表明还有3个格不被上述4个皇后所控制．放置第5个皇后E后，得到了皇后E剩余最佳位置E25，n(E25)=3；于是

n(A44)+n(B63)+n(C56)+n(D37)+n(E25)=64

整个棋盘才完全被5个皇后所控制．

至此，得到了五后问题的第一个基础解，表示为A44B63C56D37E25，并证明了在8×8棋盘上最少放置5个皇后才能使5个皇后各自安全且又能吃掉棋盘上其余任意棋子．

类似地可求出五后问题的第二个基础解为A44B65C36D23E52，其中n(A44)=28，n(B65)=16，n(C36)=10，n(D23)=6，n(E52)=4以及第3个基础解为A44B56C37D18E25，其中n(A44)=28，n(B56)=16，n(C37)=9，n(D18)=6，n(E25)=5.

对于A44、B67或A44、B76和随其后所确定的3个剩余最佳位置，均不为所求解．而由A44、B36和随其后所确定的3个剩余最佳位置所得到的解与由A44、B65所确定的解相同．

将上面3个基础解，分别以cc、dd、aa、bb多次对折，或多次的对折和以棋盘中心点顺时针旋转90°，便可得到24个解及其图示，如图2～9所示．

最后需要指出的是解的完备性问题．在求解过程中，除因利用棋盘对称性才在局域内求得皇后A最佳位置，其余都是在全域内求得各皇后全部剩余最佳(极佳)位置，并对这些最佳(极佳)位置中的每一个，都分别地完成其求解全过程，直至确定它是解或不是解，可见所求解是完备的．

87654321 (8,8)D37C56E25A44B6312345678(a)解1:A44B63C56D37E2587654321 (8,8)E47D26A55C34B6312345678(b)解2:A55B63C34D26E4787654321 (8,8)D67C46E75A54B3312345678(c)解3:A54B33C46D67E75

图2　解1～3

87654321 (8,8)E57D76A45C64B3312345678(a)解4:A45B33C64D76E5787654321 (8,8)B36C65A44D73E5212345678(b)解5:A44B36C65D73E5287654321 (8,8)B36A55E74C43D6212345678(c)解6:A55B36C43D62E74

图3　解4～6

87654321 (8,8)B66A45E24C53D3212345678(a)解7:A45B66C53D32E2487654321 (8,8)B66C35A54D23E4212345678(b)解8:A54B66C35D23E4287654321 (8,8)C36B65A44D23E5212345678(c)解9:A44B65C36D23E52

图4　解7～9

87654321 (8,8)B56E25A44C63D3212345678(a)解10:A44B56C63D32E2587654321 (8,8)E57D26A45B64C3312345678(b)解11:A45B64C33D26E5787654321 (8,8)D37C66A45E24B5312345678(c)解12:A45B53C66D37E24

图5　解10～12

87654321 (8,8)D67C36A55E74B4312345678(a)解13:A55B43C36D67E7487654321 (8,8)E47D76A55B34C6312345678(b)解14:A55B34C63D76E4787654321 (8,8)C66B35A54D73E4212345678(c)解15:A54B35C66D73E42

图6　解13～15

87654321 (8,8)B46E75A54C33D6212345678(a)解16:A54B46C33D62E7587654321 (8,8)D18C37B56E25A4412345678(b)解17:A44B56C37D18E2587654321 (8,8)D18E47C26A55B3412345678(c)解18:A55B34C26D18E47

图7　解16～18

87654321 (8,8)D88E57C76A45B6412345678(a)解19:A45B64C76D88E5787654321 (8,8)D88C67B46E75A5412345678(b)解20:A54B46C67D88E7587654321 (8,8)A55E74B43C62D8112345678(c)解21:A55B43C62D81E74

图8　解19～21

87654321 (8,8)B65A44C73E52D8112345678(a)解22:A44B65C73D81E5287654321 (8,8)B35A54C23E42D1112345678(b)解23:A54B35C23D11E4287654321 (8,8)A45E24B53C32D1112345678(c)解24:A45B53C32D11E24

图9解22～24

Fig.9Solutions 22-24

3结语

对于本论题，使用逐步确定皇后最佳(极佳)或剩余最佳(极佳)位置求解五后问题是有效的、成功的．而且，对于类似本论题的2k×2k棋盘问题的求解给出了一种新途径，它极大限度地克服了以往人们用视察法求解本论题的盲目性．随着k的增大，收效更加明显．该成果在防灾和安全领域中、在社会管理中，对如何设计必要节点具有理论指导意义，从而凸显了经济效益和社会效益．

致谢：在论文完成中，得到了杨元生教授热情和有益的帮助，在此深表谢意！

参考文献：

[1] Brualdi R A. 组合数学导论[M]. 李盘林,等译. 武汉:华中理工大学出版社, 1982.

Brualdi R A. Introductory Combinatorics [M]. LI Pan-lin,etal., trans. Wuhan: Huazhong University of Science & Technology Press, 1982. (in Chinese)

[2]李明哲,金 俊,石端银. 图论及其算法[M]. 北京:机械工业出版社, 2010.

LI Ming-zhe, JIN Jun, SHI Duan-yin. Graph Theory and Its Algorithm [M]. Beijing: China Machine Press, 2010. (in Chinese)

[3]李盘林,李丽双,赵铭伟,等. 离散数学[M]. 3版. 北京:高等教育出版社, 2016.

LI Pan-lin, LI Li-shuang, ZHAO Ming-wei,etal. Discrete Mathematics [M]. 3rd ed. Beijing: High Education Press, 2016. (in Chinese)

[4]李盘林,李立健,刘晓红,等. 基于启发性知识研究生院课表编排系统[J]. 计算机学报, 1992, 15(11):876-889.

LI Pan-lin, LI Li-jian, LIU Xiao-hong,etal. A heuristic knowledge-based graduate school timetable scheduling system [J]. Chinese Journal of Computers, 1992, 15(11):876-889. (in Chinese)

Solution to De Jaenisch′s five queens problem

LIPan-lin*1,ZHAOMing-wei1,XUXi-rong1,LILi-shuang1,LIBo-zhang2

( 1.Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China；2.Department of Computer Engineering, University of Waterloo, Waterloo, ON, Canada )

Abstract：The coordinate representation of the chess board is given, the control number or the remaining control number of the queen, and the optimum (heuristical) or the remaining optimum (heuristical) positions of the queen are defined. Using the symmetrical properties of the chess board and through an efficient calculation, the three basic solutions are firstly found, and subsequently all 24 solutions shown in the following illustrations are found. This is the first time that a proof of the minimum number of queens required being five but not four is given, and a completeness proof of the solution has been given.

Key words：five-queen problem; control number / the remaining control number of the queen; optimum (heuristical) or the remaining optimum (heuristical) positions of the queen

中图分类号：O158

文献标识码：A

doi:10.7511/dllgxb201603013

作者简介:李盘林*(1940-)，男，教授，E-mail:lipanlin@dlut.edu.cn.

基金项目:国家自然科学基金资助项目(61170303).

收稿日期：2015-09-05；修回日期: 2016-04-01．

文章编号：1000-8608(2016)03-0304-05