德杰尼斯五后問題泛化研究

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

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

德杰尼斯五后問題泛化研究

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

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

在德杰尼斯五后問題求解方法基礎(chǔ)上，給出了2p×2p棋盤坐標(biāo)表示，定義了方環(huán)和馬步格，并利用皇后控制數(shù)或剩余控制數(shù)、皇后最佳(極佳)位置或剩余最佳(極佳)位置，以及棋盤對稱性，得到了德杰尼斯五后問題泛化求解定理和便于求解的簡化定理．

德杰尼斯五后問題；皇后控制數(shù)或剩余控制數(shù)；皇后最佳(極佳)或剩余最佳(極佳)位置；方環(huán)；馬步格

0 引 言

在德杰尼斯五后問題求解方法[1](下稱五后問題)一文的結(jié)語中，指出對于2p×2p(p=1，2，…)棋盤上最少放置多少皇后，使它們在不同行、不同列和不同對角線上且能吃掉(或稱管控)棋盤上其余任何棋子(下稱五后問題泛化論題)這一問題的求解途徑[2]，它可極大限度地克服以往人們用視察法求解[3]的盲目性．隨著p的增大，收效更加明顯．本文進(jìn)一步詳細(xì)地研究五后問題泛化論題．

1 求解前準(zhǔn)備

(1)2p×2p棋盤坐標(biāo)表示：完全類似于文獻(xiàn)[1]中的描述，見圖1．

(2)方環(huán)的定義：由格sp,p，sp+1,p，sp+1,p+1和sp,p+1組成p級方環(huán)；由格sp-1,p-1，sp,p-1，sp+1,p-1，sp+2,p-1，sp+2,p，sp+2,p+1，sp+2,p+2，sp+1,p+2，sp,p+2，sp-1,p+2，sp-1,p+1，sp-1,p組成p-1級方環(huán)…由格s1,1，s2,1，…，s2p,1，s2p,2，…，s2p,2p，…，s2,2p，s1,2p，…，s1,2組成1級方環(huán)(或稱邊界方環(huán))．由各級方環(huán)中的格所組成的集合，記為Rk，1≤k≤p，如Rp={sp,p，sp+1,p，sp+1,p+1，sp,p+1}．從方環(huán)定義可知，方環(huán)是對于某些格在棋盤中位置的一種形象描述．

n(Q|si,j)、n(Q|sk,l)設(shè)為皇后Q分別放置在si,j和sk,l上的皇后控制數(shù)，于是可給出下列定理：

定理2n(Q|si,j∈Rk)=6p-2k-4，k≤p．

定理3 若si,j，sk,l∈Rk，則n(Q|si,j)=n(Q|sk,l)，1≤k≤p．

定理4 若si,j∈Rm，sk,l∈Rn，m>n，則n(Q|si,j)>n(Q|sk,l)，1≤m，n≤p．

證明略．

定理4表明了皇后放置格離棋盤中心(p，p)越近，其皇后控制數(shù)越大．

圖1 2p×2p棋盤定義

令C={si,j|1≤i，j≤2p}，即C是棋盤上所有格的集合．

證明略．

設(shè)Si,j是與格si,j同行、同列和同對角線上所有格集合，則有下面定理：

2 核心定理

下面，為凸顯放置皇后Q的先后次序，令n(Q|si,j) 是第k個(gè)皇后Q放置在si,j上的剩余控制數(shù)(k≥2)．

設(shè)si0,j0=sp,p，其實(shí)Rp中任何元素均可作為第1個(gè)皇后Q最佳位置．

于是，

定理7 (五后問題泛化定理)

n(Q1)+n(Q2)+…+n(Qk)+…+n(Qm(p))= 2p×2p

(1)

證明 因?yàn)樵?p×2p棋盤上要求放置最少皇后，使它們在不同行、不同列和不同對角線上，并能管控(或吃掉)棋盤上除已放置皇后外的任何棋子，這可轉(zhuǎn)化為要求每放置一個(gè)皇后，使它管控(或吃掉)棋盤上盡可能多的棋子，并且對于滿足下式：

n(Q1)+n(Q2)+…+n(Ql)+…+n(Qmk)= 2p×2p

(1a)

或

n(Q|si0,j0)+n(Q|si1,j1)+…+n(Q|sil-1,jl-1)+…+n(Q|simk-1,jmk-1)=2p×2p

有多個(gè)(比如說q個(gè))長度不同的皇后最佳(極佳)位置序列以及由它們分別組成的集S1，S2，…，Sk，…，Sq，而

為方便計(jì)，每個(gè)位置序列稱為式(1a)的一個(gè)廣義解，相應(yīng)的集合基數(shù)，稱為廣義解長度．

：2(2p-1)3

2

p

-1

，便可確定

m

(

p

)．如果在求解中，發(fā)現(xiàn)尚有更小的

m

(

p

)，則只好改之．然而這種概率是很小的．

為求出所有廣義解，首先求出第一個(gè)廣義解，并以它為基礎(chǔ)求出其余廣義解．若第一個(gè)廣義解中有幾處皇后剩余極佳位置，對每一處中的每一個(gè)其他剩余極佳位置，都按第一個(gè)廣義解處理皇后剩余極佳位置那樣，求出一個(gè)新的廣義解．對于求出第二個(gè)廣義解，如同第一個(gè)廣義解那樣處理每個(gè)皇后剩余極佳位置，如此這般，便可求出所有廣義解．證畢．

推論1 若求得所有以sp,p為第1個(gè)皇后Q最佳位置的n(p)個(gè)不同基礎(chǔ)解，則本定理便有8n(p)個(gè)解．

推論

22(2p-1)3

注意，兩個(gè)不同基礎(chǔ)解，是指兩個(gè)基礎(chǔ)解中皇后最佳(極佳)位置或剩余最佳(極佳)位置所組成集合是不同的．

定理8

n(Q1)+n(Q2)+…+n(Qk)+…+n(Qim(p)-1,jm(p)-1)=2p×2p

或

n(Q|si0,j0)+n(Q|si1,j1)+…+n(Q|sik-1,jk-1)+…+n(Q|sim(p)-1,jm(p)-1)= 2p×2p

其中

可知放置第k個(gè)皇后在自由域Ck-1=Ck-2-Sik-2,jk-2中求出皇后剩余最佳(極佳)位置sik-1,jk-1，利用馬步格，這可轉(zhuǎn)化為

(1)若自由域Ck-1中含有已求出皇后剩余最佳(極佳)位置的馬步格，則可求得第k個(gè)皇后剩余最佳(極佳)位置sik-1,jk-1，即

(2)若自由域Ck-1中不存在已求出皇后剩余最佳(極佳)位置的馬步格，則可在自由域Ck-1中求出第k個(gè)皇后剩余最佳(極佳)位置sik-1,jk-1，即

注意：(1)中所求是從第2個(gè)開始的皇后剩余最佳(極佳)位置；(2)中所求是幾個(gè)最后皇后剩余最佳(極佳)位置．

需要指出的是，對于式(1a)求每個(gè)廣義解均以sp,p為第1個(gè)皇后最佳位置，而其余皇后剩余最佳(極佳)位置均在自由域C1，C2，…內(nèi)求其皇后剩余控制數(shù)最大為依據(jù)，這便有可能使選定皇后最佳(極佳)位置彼此在棋盤相距遠(yuǎn)而分散，求得皇后剩余控制數(shù)有的較大，有的很小，致使所求廣義解長度增大，不利達(dá)到基礎(chǔ)解要求，期望落空．若皇后最佳(極佳)位置在已選定皇后最佳(極佳)位置的馬步格進(jìn)行，由于這些馬步格相聚中心(p，p)周圍并逐漸向外展開，使得皇后剩余控制數(shù)變動(dòng)不大，有利于廣義解長度縮小而使所要求的基礎(chǔ)解可能性增大．因此，定理8是五后問題泛化定理的便于求解的簡化形式．

3 結(jié) 語

本文定理7和定理8是五后問題泛化研究的兩個(gè)重要結(jié)果，為在n×n網(wǎng)格上布置最少節(jié)點(diǎn)管控全局的優(yōu)化問題提供了一種有效方法，而且在防災(zāi)和安全領(lǐng)域及社會(huì)管理中得到了應(yīng)用，有著明顯的經(jīng)濟(jì)效益和社會(huì)效益．

[1] 李盤林,趙銘偉,徐喜榮,等. 德杰尼斯五后問題求解方法[J]. 大連理工大學(xué)學(xué)報(bào), 2016, 56(3):304-308.

LI Panlin, ZHAO Mingwei, XU Xirong,etal. Solution to De Jaenisch′s five queens problem[J]. Journal of Dalian University of Technology, 2016, 56(3):304-308. (in Chinese)

[2] 李盤林,李麗雙,趙銘偉,等. 離散數(shù)學(xué)[M]. 3版. 北京:高等教育出版社, 2016.

LI Panlin, LI Lishuang, ZHAO Mingwei,etal. Discrete Mathematics [M]. 3 rd ed. Beijing: Higher Education Press, 2016. (in Chinese)

[3] 李盤林,李立建,劉曉紅,等. 基于啟發(fā)性知識研究生院課表編排系統(tǒng)[J]. 計(jì)算機(jī)學(xué)報(bào), 1992, 15(11):876-889.

LI Panlin, LI Lijian, LIU Xiaohong,etal. A heuristic knowledge-based graduate school timetable scheduling system [J]. Chinese Journal of Computers, 1992, 15(11):876-889. (in Chinese)

Research on generalization of De Jaenisch′s five queens problem

LI Panlin*1, ZHAO Mingwei1, XU Xirong1, LI Lishuang1, LI Bozhang2

( 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 )

On the basis of the solution to De Jaenisch′s five queens problem, the coordinate representation of the 2p×2pchess board is introduced, and the square ring and lattice of the horse′s walking in Chinese chess are defined. Using the control number or the remaining control number of the queen, the optimum (heuristically) or the remaining optimum (heuristically) positions of the queen and chess board symmetry, De Jaenisch′s five queens problem generalization solution theorem and the simplified theorem convenient to solve are given.

De Jaenisch′s five queens problem; control number/ the remaining control number of the queen; the optimum (heuristically) or the remaining optimum (heuristically) positions of the queen; square ring; lattice of the horse′s walking in Chinese chess

1000-8608(2017)03-0327-04

2016-08-09；

2017-03-31．

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

李盤林*(1940-)，男，教授，E-mail:lipanlin@dlut.edu.cn；趙銘偉(1972-)，女，高級工程師，E-mail:zhaomw@dlut.edu.cn；徐喜榮(1967-)，女，副教授，E-mail:xirongxu@dlut.edu.cn；李麗雙(1967-)，女，教授，E-mail:lils@dlut.edu.cn.

O158

A

10.7511/dllgxb201703017