基于0-1規劃的五連珠問題求解

吳亞東，肖華勇

?

基于0-1規劃的五連珠問題求解

吳亞東，肖華勇

（西北工業大學 理學院，陜西 西安 710129）

五連珠問題是五子棋中抽象出來的問題，通過建立0-1規劃模型，求解得出一維、二維以及三維情況下五子連珠問題的可行解。類比晶體學中晶體的成核與生長過程，建立了晶胞構成模型。相比單純的0-1規劃模型，晶胞構成模型有運算規模小、運行速度快等優點。拓展至高維度情況下的連珠問題，討論不同維數規劃模型的約束類型的個數。該模型對于N子連珠問題以及八皇后的求解有一定的借鑒意義。

五子連珠；晶胞構成；0-1規劃；N維約束

五子連珠問題是基于五子棋演變而來，規則為在一個棋盤中的每個小方格子的中心點各放一個棋子，如果兩個棋子所在的小方格有公共邊或公共頂點，那么則稱這兩個棋子相連。

針對五連珠問題的規則要求，我們建立了0-1規劃模型，通過Lingo軟件編程得到了在一維、二維以及三維空間下的可行解[1]。借鑒晶體學中晶體生長與晶胞構成，建立了晶胞構成模型求解連珠問題，討論了在N維空間下的五子連珠問題的約束類型數目。

1 0-1規劃模型建立

1.1 二維一般問題

以6×7的長方形棋盤為例，對前5列，每行至少需要去掉1個棋子，則前5列至少需要去掉6個棋子。對后兩列，每列至少需要去掉1個棋子，因此后兩列至少需要去掉2個棋子。則總的至少需要去掉8個棋子。如圖1所示。

圖2是一種去掉8個棋子而能滿足條件的方式。

圖1 6×7長方形棋盤

圖2 6×7情況的一種解法

1.2 二維一般模型

對×的五連珠問題，建0-1決策變量[2-4]，設

去掉棋子數最少的目標函數設為：

每行連續5個格子中至少要去掉一個棋子，則有：

每列連續5個格子中至少要去掉一個棋子，則有：

每條反斜線上連續5個格子中至少要去掉一個棋子，則有：

每條正斜線上連續5個格子中至少要去掉一個棋子，則有：

因此總的線性規劃模型為：

約束總數：

當=13，=17時，=556，其約束條件如下：

13×17的棋盤需要44個棋子。

圖3 13×17棋盤情況一種解法

1.3 三維一般模型

對××的五連珠問題，建0-1決策變量，設

去掉棋子數最少的目標函數為：

三個方向分別稱為、及軸方向。

圖4 4條空間對角線方向示意圖

（1）只變一個方向的約束：

（2）變兩個方向的約束：

（3）變三個方向的約束

總共約束有3+6+4=13類。

約束總數：

線性規劃模型為：

對于6×7×6棋盤，求解結果為64。

2 晶體生長模型建立

建立的0-1規劃模型，可以求解小規模低維度的問題，但對于高維度大規模的棋盤，其求解速度有待提高。為此我們引入晶體學中晶胞的概念以簡化問題。

晶胞：構成晶體的最基本的幾何單元，是能完整反映晶體內部原子或離子在三維空間分布之化學結構特征的平行六面體最小單元[5]。

2.1 一維晶胞模型

當我們將二維問題降維到一維問題（以=13為例）時，其一般的結果如圖5所示。

圖5 一維一般問題

從圖5可以發現，黑棋子總是每隔4個就出現一次，同理，5連續的5個棋子可以看做是一個循環單元，如果恰巧就是5的整數倍，那么只是循環單元在反復地、完整地出現，這與晶胞的概念類似。將連續的5個棋子視為“一維晶胞”，一維棋盤的增長、擴張就類似晶體由晶核生長為晶體的過程。可以將問題簡化如下：首先求解出一個有效的晶胞，然后讓其“生長”為邊長是5的整數倍的棋盤，最后根據給定的棋盤大小從中統計出最少的棋子的排列方式。例如，對于邊長為13的棋盤來講，先求解邊長為5棋盤，再將其平移復制2個成為邊長為15的棋盤，統計連續13個格子中黑子的數目，即可找到最少黑子的邊長為13的棋盤分布，此為一個可行解。避免了直接求解大規模棋盤就可以得到可行解，而且還可能得到多個可行解。

2.2 二維晶胞模型

二維13×17棋盤的一種解如圖6所示。

可以發現類二維棋盤中的二維晶胞（圖6中虛線內部分），其大小為5×5。求解二維晶胞的思路可以用圖7-圖9示意。

一張二維平面，將其上下連接在一起，左右也連接在一起，兩個斜對角線也連接在一起，見圖7。由平面變成圓筒，再變為圓環，見圖8。在每一個點處的橫向、縱向、斜向都滿足五連珠條件，則可得到原平面的二維晶胞，見圖9。

圖7 有效晶胞的約束方式

圖8 二維有效晶胞約束示意圖

圖9 二維有效晶胞

有了二維晶胞以后，對其進行平移復制為20×25的二維棋盤，從中統計出以13、17為邊長的長方形棋盤內最少的黑子數目（44個），得到圖10中的2種完全不同的解，其中的一種在之前未求解出。若對其進行對稱、旋轉變換可得到更多的可行解。