德杰尼斯五后問題求解方法

李 盤 林，　趙 銘 偉，　徐 喜 榮，　李 麗 雙，　李 伯 章

( 1.大連理工大學(xué) 電子信息與電氣工程學(xué)部, 遼寧 大連　116024；2. 滑鐵盧大學(xué) 計(jì)算機(jī)工程系， 加拿大 安大略　滑鐵盧 )

?

德杰尼斯五后問題求解方法

李 盤 林*1，趙 銘 偉1，徐 喜 榮1，李 麗 雙1，李 伯 章2

( 1.大連理工大學(xué) 電子信息與電氣工程學(xué)部, 遼寧 大連116024；2. 滑鐵盧大學(xué) 計(jì)算機(jī)工程系， 加拿大 安大略滑鐵盧 )

摘要：給出了棋盤坐標(biāo)表示，定義了皇后控制數(shù)或剩余控制數(shù)，以及皇后最佳(極佳)或剩余最佳(極佳)位置的概念．利用棋盤對稱性，通過有效的計(jì)算，先求出了五后問題的3個(gè)基礎(chǔ)解，進(jìn)而得到了全部24個(gè)解及其圖示，并首次給出了最少放置5個(gè)而不是4個(gè)皇后的證明，以及解的完備性證明．

關(guān)鍵詞：五后問題；皇后控制數(shù)或剩余控制數(shù)；皇后最佳(極佳)或剩余最佳(極佳)位置

0引言

在信息領(lǐng)域，八后問題、五后問題，了解它們的不乏其人．前者由高斯解決[1]，后者就不那么幸運(yùn)了．都說五后問題但其內(nèi)涵是不同的(http://cjc.iteye.com/blog/299173；http://wenku.baidu.com/view/c254e769a98271fe910ef965.html)．1862年，德杰尼斯[2](De Jaenisch)研究在8×8棋盤上最少放置幾個(gè)皇后，它們彼此互不攻擊，又能控制其他任意棋子．他給出7個(gè)皇后的解，而正確解是5個(gè)．為了不忘德杰尼斯的先期工作，將下面論題：在8×8棋盤上最少放置5個(gè)皇后，能否使5個(gè)皇后各自安全且又能吃掉棋盤上其余任意棋子(皇后占用的五格不同行、或不同列、或不同一對角線，且又能與棋盤上其余格同行、或同列、或同一對角線)稱為德杰尼斯五后問題[3]．本文給出上述論題的一種解法．

1求解前的說明

(1)8×8棋盤坐標(biāo)表示，即對由64個(gè)稱為格的小正方形構(gòu)成一個(gè)大正方形稱為棋盤的給出坐標(biāo)表示．大正方形的左下頂點(diǎn)為坐標(biāo)原點(diǎn)O；大正方形的底邊為坐標(biāo)x軸；大正方形的左邊為坐標(biāo)y軸．小正方形的邊長為坐標(biāo)軸的1個(gè)單位；小正方形即格S的右上頂點(diǎn)坐標(biāo)(i，j)作為S的標(biāo)記，記為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)為棋盤的中心點(diǎn)．a(chǎn)a與bb將棋盤劃分為4個(gè)區(qū)域R1、R2、R3和R4．上述說明如圖1所示．

(2)第1個(gè)皇后Q放在格Sij上，位于與Sij同行、同列和同一對角線上的所有格數(shù)，稱為皇后Q控制數(shù)[4]，記為n(Q|Sij)．使控制數(shù)最大的皇后Q所在格Si0j0是唯一的，稱Si0j0為皇后Q最佳位置[4]，記為Qi0j0，其控制數(shù)記為n(Qi0j0)；若不唯一，比如說Si1j1，Si2j2，…，稱這些格為皇后Q極佳位置，記為Qi1j1，Qi2j2，…；其控制數(shù)分別記為n(Qi1j1)，n(Qi2j2)，…．

類似地可定義第3個(gè)、第4個(gè)、…皇后剩余控制數(shù)、最佳(極佳)位置．

圖1　棋盤定義

2求解及證明

利用棋盤對稱性，欲求第1個(gè)皇后A最佳(極佳)位置，只需在區(qū)域R1內(nèi)計(jì)算位于cc上及其下面每個(gè)格的控制數(shù)，并求出最大者即可．經(jīng)過計(jì)算，可知皇后A最佳位置是格S44，皇后A最佳位置記為A44，n(A44)=28．

第2個(gè)皇后B剩余最佳(極佳)位置，除去與A44同行、同列和同一對角線所有格外，計(jì)算每個(gè)格的控制數(shù)且給出其最大者即可確定．經(jīng)過計(jì)算，共得到6個(gè)皇后B極佳位置：S63、S65、S56、S36、S67和S76，分別記為B63、B65、B56、B36、B67和B76，其剩余控制數(shù)分別為n(B63)=16，n(B65)=16，n(B56)=16，n(B36)=16，n(B67)=16和n(B76)=16．

在確定A44、B63后，不難求出：

第3個(gè)皇后C剩余最佳位置是格S56，皇后C最佳位置記為C56，其剩余控制數(shù)是n(C56)=10．

第4個(gè)皇后D剩余最佳位置是格S37，皇后D最佳位置記為D37，其剩余控制數(shù)是n(D37)=7．

第5個(gè)皇后E剩余最佳位置是格S25，皇后E最佳位置記為E25，其剩余控制數(shù)是n(E25)=3．

不難看出，4個(gè)皇后是不能夠控制棋盤的，因?yàn)?/p>

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

28+16+10+7=61

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

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

整個(gè)棋盤才完全被5個(gè)皇后所控制．

至此，得到了五后問題的第一個(gè)基礎(chǔ)解，表示為A44B63C56D37E25，并證明了在8×8棋盤上最少放置5個(gè)皇后才能使5個(gè)皇后各自安全且又能吃掉棋盤上其余任意棋子．

類似地可求出五后問題的第二個(gè)基礎(chǔ)解為A44B65C36D23E52，其中n(A44)=28，n(B65)=16，n(C36)=10，n(D23)=6，n(E52)=4以及第3個(gè)基礎(chǔ)解為A44B56C37D18E25，其中n(A44)=28，n(B56)=16，n(C37)=9，n(D18)=6，n(E25)=5.

對于A44、B67或A44、B76和隨其后所確定的3個(gè)剩余最佳位置，均不為所求解．而由A44、B36和隨其后所確定的3個(gè)剩余最佳位置所得到的解與由A44、B65所確定的解相同．

將上面3個(gè)基礎(chǔ)解，分別以cc、dd、aa、bb多次對折，或多次的對折和以棋盤中心點(diǎn)順時(shí)針旋轉(zhuǎn)90°，便可得到24個(gè)解及其圖示，如圖2～9所示．

最后需要指出的是解的完備性問題．在求解過程中，除因利用棋盤對稱性才在局域內(nèi)求得皇后A最佳位置，其余都是在全域內(nèi)求得各皇后全部剩余最佳(極佳)位置，并對這些最佳(極佳)位置中的每一個(gè)，都分別地完成其求解全過程，直至確定它是解或不是解，可見所求解是完備的．

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結(jié)語

對于本論題，使用逐步確定皇后最佳(極佳)或剩余最佳(極佳)位置求解五后問題是有效的、成功的．而且，對于類似本論題的2k×2k棋盤問題的求解給出了一種新途徑，它極大限度地克服了以往人們用視察法求解本論題的盲目性．隨著k的增大，收效更加明顯．該成果在防災(zāi)和安全領(lǐng)域中、在社會管理中，對如何設(shè)計(jì)必要節(jié)點(diǎn)具有理論指導(dǎo)意義，從而凸顯了經(jīng)濟(jì)效益和社會效益．

致謝：在論文完成中，得到了楊元生教授熱情和有益的幫助，在此深表謝意！

參考文獻(xiàn)：

[1] Brualdi R A. 組合數(shù)學(xué)導(dǎo)論[M]. 李盤林,等譯. 武漢:華中理工大學(xué)出版社, 1982.

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

[2]李明哲,金 俊,石端銀. 圖論及其算法[M]. 北京:機(jī)械工業(yè)出版社, 2010.

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

[3]李盤林,李麗雙,趙銘偉,等. 離散數(shù)學(xué)[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]李盤林,李立健,劉曉紅,等. 基于啟發(fā)性知識研究生院課表編排系統(tǒng)[J]. 計(jì)算機(jī)學(xué)報(bào), 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

文獻(xiàn)標(biāo)識碼：A

doi:10.7511/dllgxb201603013

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

基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61170303).

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

文章編號：1000-8608(2016)03-0304-05