奇數(shù)網(wǎng)格(或棋盤(pán))德杰尼斯問(wèn)題解法

李 盤(pán) 林， 趙 銘 偉， 徐 喜 榮， 李 麗 雙， 李 伯 章

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

0 引 言

鑒于五后問(wèn)題的由來(lái)，作者在文獻(xiàn)[1]中將它稱(chēng)為德杰尼斯五后問(wèn)題，并先后進(jìn)行了德杰尼斯五后問(wèn)題解法[2]和德杰尼斯五后問(wèn)題泛化研究[3]．文獻(xiàn)[3]是將文獻(xiàn)[2]的論域8×8網(wǎng)格(或棋盤(pán))推廣到2p×2p網(wǎng)格(或棋盤(pán))(p=1，2，…)上．

若對(duì)任意偶數(shù)e，稱(chēng)e×e網(wǎng)格(或棋盤(pán))為偶數(shù)網(wǎng)格(或棋盤(pán))，用數(shù)學(xué)語(yǔ)言可表為2p×2p網(wǎng)格(或棋盤(pán))(p=1，2，…)；若對(duì)任意奇數(shù)o，稱(chēng)o×o網(wǎng)格(或棋盤(pán))為奇數(shù)網(wǎng)格(或棋盤(pán))，用數(shù)學(xué)語(yǔ)言可表為(2p+1)×(2p+1)網(wǎng)格(或棋盤(pán))(p=1，2，…，p=0為平凡情形)．于是，文獻(xiàn)[3]題目又可表述為偶數(shù)網(wǎng)格(或棋盤(pán))德杰尼斯問(wèn)題解法．雖然只有一字之差，但是兩者解決問(wèn)題的方法還是有所區(qū)別的．將本文與文獻(xiàn)[3]合并起來(lái)，便得到一個(gè)新論題：對(duì)任意自然數(shù)n，n×n網(wǎng)格(或棋盤(pán))德杰尼斯問(wèn)題解法．可見(jiàn)，本文和文獻(xiàn)[3]對(duì)這一論題的完成是不可或缺的．

1 求解前的準(zhǔn)備

奇數(shù)網(wǎng)格(或棋盤(pán))坐標(biāo)表示如圖1所示．

圖1 (2p+1)×(2p+1)網(wǎng)格坐標(biāo)圖示Fig.1 Coordinate illustration of (2p+1)×(2p+1) grid

從圖1可知，該圖形是關(guān)于直線aa、bb、dd和gg對(duì)稱(chēng)的，它們相交于c，其坐標(biāo)為(p+1/2，p+1/2)，以c為中心的格，稱(chēng)為中心格，表示為sp+1，p+1．可見(jiàn)，本文格仍沿用文獻(xiàn)[2]或文獻(xiàn)[3]的表示方式，即用格的右上角頂坐標(biāo)來(lái)表示．為方便計(jì)，si，j簡(jiǎn)記為sij．

定義1S={sij|1≤i，j≤2p+1}，即用S表示(2p+1)×(2p+1)網(wǎng)格中的所有格集合．(文獻(xiàn)[2]中是用C表示的)

定義2位于直線dd和bb上及其它們相交域(夾角≤90°)內(nèi)的所有格，稱(chēng)為解首格集，表示為

Sf={sij|j≤i≤p+1，1≤j≤p+1}

與文獻(xiàn)[1]、[2]中相同的定義，在此不再贅述．

又令Sfr={sij|sp-r+2p-r+2，sp-r+3p-r+2，…，sp+1p-r+2}為Sf中從中心點(diǎn)c向下第r列中格的集合，則有下面定理：

定理1Sf=Sf1∪Sf2∪…∪Sfp+1，且Sij=r，1≤r≤p+1．

定理2對(duì)任意sij∈Sf，j≤i≤p+1，1≤j≤p+1，則

6p+2j-1≤n(sij)≤8p+1

定理1和定理2的驗(yàn)證留給讀者完成．

2 解 法

首先選取si1j1∈Sf，使n(si1j1)為最大，作為第一個(gè)廣義解的首格，由定理2知，si1j1≠sp+1p+1，即si1j1∈Sf1．接著選取si1j1的馬步格，其集合表為H1．若H1∩(S-si1j1)≠，則將H1∩(S-si1j1)中格按剩余控制數(shù)排序，擇取最大(或極大，這時(shí)不止一個(gè)格，下同)者作為第一個(gè)廣義解的第2格si2j2；若H1∩(S-si1j1)=，則將(S-si1j1)中格按剩余控制數(shù)排序，擇其最大(或極大)者作為第一個(gè)廣義解的第2格si2j2．繼而，選取{si1j1，si2j2}的馬步格，其集合表為H2．若H2∩(S-si1j1-si2j2)≠，則將H2∩(S-si1j1-si2j2)中格按剩余控制數(shù)排序，擇取最大(或極大)者作為第一個(gè)廣義解的第3格si3j3；若H2∩(S-si1j1-si2j2)=，則將(S-si1j1-si2j2)中格按剩余控制數(shù)排序，擇其最大(或極大)者作為第一個(gè)廣義解的第3格si3j3．依此類(lèi)推，求出第一個(gè)廣義解的第4格si4j4，…，第k-1格sik-1jk-1．于是選取{si1j1，si2j2，…，sik-1jk-1}的馬步格，其集合表為Hk-1．若Hk-1∩(S-si1j1-si2j2-…-sik-1jk-1)≠，將Hk-1∩(S-si1j1-si2j2-…-sik-1jk-1)中格按剩余控制數(shù)排序，擇取最大(或極大)者作為第一個(gè)廣義解的第k格sikjk；若Hk-1∩(S-si1j1-si2j2-…-sik-1jk-1)=，則將(S-si1j1-si2j2-…-sik-1jk-1)中格按剩余控制數(shù)排序，擇其最大(或極大)者作為第一個(gè)廣義解的第k格sikjk．

需要指出的是：

(1)在求廣義解的第h格sihjh(h≥2)時(shí)，若n(sihjh) 為極大時(shí)，則有多個(gè)格，其剩余控制數(shù)與n(sihjh) 相同，不妨令n(sx1y1)=n(sx2y2)=…=n(siuju)，其中sx1y1=s′x1y1，以及sxvyv(2≤v≤u)為第一個(gè)廣義解的第h格．選出{si1j1，si2j2，…，sin-1jn-1，sxvyv}(2≤v≤u)的馬步格，其集合表為Hv．若(Hv-{sx1y1}-…-{sxv-1yv-1})∩(S-si1j1-…-sin-1jn-1-sxvyv)中格按剩余控制數(shù)排序，擇其最大(或極大)者作為第一個(gè)廣義解的第h+1格sih+1jh+1；否則將(S-si1j1-…-sin-1jn-1-sxvyv)中格按剩余控制數(shù)排序，擇其最大(或極大)者作為第一個(gè)廣義解的第h+1格sih+1jh+1．如此這般，便可依次求出以sx2y2，sx3y3，…，sxuyu為第h格的廣義解．

(2)要求出以Sf中的每一個(gè)格為首格的基礎(chǔ)解，即按Sf中子集次序Sf1，Sf2，…，Sfp+1求出它們中每一格為首格的基礎(chǔ)解．

定義3若

則稱(chēng){siljl|1≤l≤k}為所求的第一個(gè)廣義解，其廣義解中格的個(gè)數(shù)，稱(chēng)為該廣義解的基數(shù)或長(zhǎng)度．

類(lèi)似求第一個(gè)廣義解那樣，求第二個(gè)廣義解．第二個(gè)廣義解的首格，可以是si1j1即sp+1p+1，但也可能不是sp+1p+1，而是Sfr中的其他格(r≥2)．這與p的取值有關(guān)．取上述二廣義解的基數(shù)或長(zhǎng)度小者，稱(chēng)為問(wèn)題候選基礎(chǔ)解；若上述二廣義解的基數(shù)或長(zhǎng)度相同，則它們便都是問(wèn)題候選基礎(chǔ)解．而候選基礎(chǔ)解中格的個(gè)數(shù)，稱(chēng)為候選基礎(chǔ)解的基數(shù)或長(zhǎng)度．

在求解過(guò)程中，若當(dāng)前廣義解，其基數(shù)或長(zhǎng)度比以前候選基礎(chǔ)解的基數(shù)或長(zhǎng)度小，則取當(dāng)前廣義解為該問(wèn)題的候選基礎(chǔ)解．仿上，求出后面的候選基礎(chǔ)解．由此可知，在整個(gè)求解過(guò)程中，存在候選基礎(chǔ)解的基數(shù)或長(zhǎng)度不再是變小的一些解，稱(chēng)這些(或這個(gè))解為問(wèn)題的基礎(chǔ)解．基礎(chǔ)解中格的個(gè)數(shù)，稱(chēng)為基礎(chǔ)解的基數(shù)或長(zhǎng)度．

根據(jù)奇數(shù)網(wǎng)格(或棋盤(pán))圖形對(duì)稱(chēng)性，可得下面定理：

定理3對(duì)任給定奇數(shù)o(o≥5)，若求出o×o網(wǎng)格(或棋盤(pán))德杰尼斯問(wèn)題的no個(gè)不同基礎(chǔ)解，則它將有4×no個(gè)不同解．

為便于理解問(wèn)題的解法，下面給出了圖2～4，分別是3×3網(wǎng)格、5×5網(wǎng)格和7×7網(wǎng)格德杰尼斯問(wèn)題的1個(gè)、3個(gè)和24個(gè)基礎(chǔ)解．

3 結(jié) 語(yǔ)

本文完成了奇數(shù)網(wǎng)格(或棋盤(pán))德杰尼斯問(wèn)題解法，它與文獻(xiàn)[2]共同給出了對(duì)任意自然數(shù)n，n×n網(wǎng)格(或棋盤(pán))德杰尼斯問(wèn)題求解．這不僅具有一定的理論價(jià)值，而且在防災(zāi)減災(zāi)和安全領(lǐng)域中前景利好．

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

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

[2]李盤(pán)林,趙銘偉,徐喜榮,等. 德杰尼斯五后問(wèn)題求解方法[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].JournalofDalianUniversityofTechnology, 2016,56(3):304-308. (in Chinese)

[3]李盤(pán)林,趙銘偉,徐喜榮,等. 德杰尼斯五后問(wèn)題泛化研究[J]. 大連理工大學(xué)學(xué)報(bào), 2017,57(3):327-330.

LI Panlin, ZHAO Mingwei, XU Xirong,etal. Research on generalization of De Jaenisch′s five queens problem [J].JournalofDalianUniversityofTechnology, 2017,57(3):327-330. (in Chinese)