奇數網格(或棋盤)德杰尼斯問題解法

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

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

0 引 言

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

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

1 求解前的準備

奇數網格(或棋盤)坐標表示如圖1所示．

圖1 (2p+1)×(2p+1)網格坐標圖示Fig.1 Coordinate illustration of (2p+1)×(2p+1) grid

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

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

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

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

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

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

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

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

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

定理1和定理2的驗證留給讀者完成．

2 解 法

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

需要指出的是：

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

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

定義3若

則稱{siljl|1≤l≤k}為所求的第一個廣義解，其廣義解中格的個數，稱為該廣義解的基數或長度．

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

在求解過程中，若當前廣義解，其基數或長度比以前候選基礎解的基數或長度小，則取當前廣義解為該問題的候選基礎解．仿上，求出后面的候選基礎解．由此可知，在整個求解過程中，存在候選基礎解的基數或長度不再是變小的一些解，稱這些(或這個)解為問題的基礎解．基礎解中格的個數，稱為基礎解的基數或長度．

根據奇數網格(或棋盤)圖形對稱性，可得下面定理：

定理3對任給定奇數o(o≥5)，若求出o×o網格(或棋盤)德杰尼斯問題的no個不同基礎解，則它將有4×no個不同解．

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

3 結 語

本文完成了奇數網格(或棋盤)德杰尼斯問題解法，它與文獻[2]共同給出了對任意自然數n，n×n網格(或棋盤)德杰尼斯問題求解．這不僅具有一定的理論價值，而且在防災減災和安全領域中前景利好．

[1] 李盤林,李麗雙,趙銘偉,等. 離散數學[M]. 3版. 北京:高等教育出版社, 2016.

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

[2]李盤林,趙銘偉,徐喜榮,等. 德杰尼斯五后問題求解方法[J], 大連理工大學學報, 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]李盤林,趙銘偉,徐喜榮,等. 德杰尼斯五后問題泛化研究[J]. 大連理工大學學報, 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)