棋盤多項(xiàng)式的一種改進(jìn)思路

摘要：棋盤多項(xiàng)式是在分析解決棋類問題過程中所產(chǎn)生的一種排列組合分析方法，由于它對(duì)棋子的排列規(guī)則有較嚴(yán)格的約束，從而導(dǎo)致很多類似于棋盤排列的問題難以直接應(yīng)用這種棋盤多項(xiàng)式分析方法，因此文章對(duì)棋盤多項(xiàng)式做出了改進(jìn)，使之能夠?yàn)楦嗯帕薪M合問題提供一種分析思路。

關(guān)鍵詞：棋盤多項(xiàng)式；正則擺放；行擺放；列擺放

一、引言

棋盤多項(xiàng)式是在分析棋盤內(nèi)棋子分布方案的過程中提出的一種方法，它不僅給棋盤上的棋子分布問題提供了較好的分析工具，而且也為其他很多排列組合問題提供了一種較為有用的分析方法。

定義1：一個(gè)n*n個(gè)方格組成的圖形去掉其中某些方格，稱為一個(gè)棋盤，用C表示，如圖1、圖2、圖3、圖4所示棋盤。

在棋盤中擺放棋子（去掉的格不能擺放），如果每行每列最多擺一個(gè)棋子，則這種擺放稱為正則擺放，如圖1所示。棋盤多項(xiàng)式就是描述這種正則擺放方案數(shù)的一種方法。

定義2：對(duì)于一個(gè)棋盤C而言，其棋盤多項(xiàng)式表示為R（C），則有：

R（C）= r0（C）+r1（C）x+r2（C）x2+...+ri（C）xi+...

其中ri（C）表示i個(gè)棋子擺放在棋盤C上有多少種擺法，并且規(guī)定：r0（C）=1；當(dāng)C為空棋盤時(shí)，R（C）=R（）=1；

定義3：在棋盤C中任取一個(gè)格，將這個(gè)格去掉，得到的棋盤記作CP，把這個(gè)格所在的行和列都去掉得到的棋盤記作CI。則棋盤多項(xiàng)式具有如下性質(zhì)：

rk（C）=rk-1（CI）+rk（CP）；

R（C）=xR（CI）+R（CP）；

如果C可以分裂成C1，C2，則R（C）＝R（C1）*R（C2）。

性質(zhì)（3）中的分裂特性，是指C=C1∪C2，C1∩C2=φ，并且C1所有格子所在的列和行都與C2中所有格子所在列和行不等，即兩個(gè)子棋盤C1與C2在行列上沒有重疊，如圖3所示棋盤可以分裂成□和。圖2所示棋盤，按照性質(zhì)（2）展開有：

R（）=xR（）+R（）=x+xR（ ）+R（ ）=x+xR（）+xR（）+R（）=x+（2x+1）（xR（）+R（□））=x+（2x+1）（x+x+1）=4x2+5x+1，它所表達(dá)的信息為：該棋盤最多擺放2個(gè)棋子（即該多項(xiàng)式為2次式），擺放2個(gè)棋子有4種擺法；擺放1個(gè)棋子有5種擺法；擺放0個(gè)棋子有1種擺法。

圖3所示棋盤，按照性質(zhì)（3）展開有：

R（）=R（□）R（ ）=（x+1）（xR（□）+R（））=（x+1）（x2+x+xR（□）+R（））=（x+1）（2x2+2x+2x+1）= 2x3+6x2+ 5x+1，同理，它所表達(dá)的信息為：該棋盤最多擺放3個(gè)棋子（即該多項(xiàng)式為3次式），擺放3個(gè)棋子有2種擺法；擺放2個(gè)棋子有6種擺法；擺放1個(gè)棋子有5種擺法；擺放0個(gè)棋子有1種擺法。

棋盤多項(xiàng)式是棋盤上棋子擺放方案數(shù)的一種表示，它對(duì)于分析研究復(fù)雜排列組合問題有著重要的作用，如圍棋、象棋、機(jī)器人及計(jì)算機(jī)智能排課等問題。但是它對(duì)于棋子擺放的約束條件，卻大大限制了其應(yīng)用范圍，如象棋中博弈一方的2個(gè)車可以擺放在同一列或同一行上，排課系統(tǒng)中同一門課可以排在不同天的同一時(shí)間段，即課表中同一行上。為此，本文提出棋盤多項(xiàng)式的一種改進(jìn)思路，將其條件“棋盤中棋子既不能處于同一行也不能處于同一列”進(jìn)行擴(kuò)充，從而可以使棋盤多項(xiàng)式分析技術(shù)運(yùn)用于更多的實(shí)際問題中。

二、兩種改進(jìn)策略

針對(duì)正則擺放的限制條件，可以提出兩種改進(jìn)方法。這兩種改進(jìn)后的棋盤多項(xiàng)式與正則擺放的棋盤多項(xiàng)式具有相同的含義與性質(zhì)，只是棋子擺放條件進(jìn)行修改。

第一，取消對(duì)行的限制，即允許在同一行上同時(shí)擺放多個(gè)棋子，但同一列只能擺放一個(gè)棋子，我們稱這種擺放規(guī)則為行擺放。例如智能排課問題中，一天中同一門課一般不允許排兩次，但允許排在不同天的同一時(shí)間段，即屬于行擺放規(guī)則。行擺放規(guī)則下的棋盤多項(xiàng)式記為R1（C），對(duì)于棋盤中任意一格如果去掉此格得到的棋盤記為C1p及去掉該格子所在列后得到的棋盤記為C1I，則有其對(duì)應(yīng)性質(zhì)（1）、性質(zhì)（2）和性質(zhì)（3），性質(zhì)（1）與正則擺放規(guī)則中的性質(zhì)（1）保持一致。性質(zhì)（2）：R1（C）=xR1（C1I）+R1（C1p）。性質(zhì)（3）：如果棋盤C可以分裂成小棋盤C1和C2，這種分裂特性是指C=C1∪C2，C1∩C2=φ，并且C1所有格子的列號(hào)都與C2中所有格子的列號(hào)不等，即兩個(gè)子棋盤C1與C2在列上沒有重疊，則有R1（C）=R1（C1）*R1（C2）。

例如，圖2所示的棋盤可以分裂成

和，而且還可以進(jìn)一步分裂成□和□。由于行擺放中對(duì)行沒有約束，并且棋盤具有二維性，所以可以得出如下性質(zhì)（4）。

性質(zhì)（4）：行擺放規(guī)則中，任意形狀的二維棋盤C都可以分裂成多個(gè)小棋盤，這些小棋盤即由原始棋盤的各個(gè)列（記為C1，C2，C3，…）所構(gòu)成，則有R1（C）=R1（C1）*R1（C2）*R1（C3）…。

第二，取消對(duì)列的限制，即允許在同一列上同時(shí)擺放多個(gè)棋子，但同一行只能擺放一個(gè)棋子，我們稱這種擺放規(guī)則為列擺放。同理，將列擺放規(guī)則下的棋盤多項(xiàng)式記為R2（C），對(duì)于棋盤中任意一格如果去掉此格得到的棋盤記為C2p及去掉該格子所在行后得到的棋盤記為C2I，則有其對(duì)應(yīng)性質(zhì)（1）、性質(zhì)（2）和性質(zhì)（3），性質(zhì)（1）與正則擺放規(guī)則中的性質(zhì)（1）保持一致。性質(zhì)（2）：R2（C）=x R2（C2I）+R2（C2p）。性質(zhì)（3）：如果棋盤C可以分裂成小棋盤C1和C2，這種分裂特性是指C=C1∪C2，C1∩C2=φ，并且C1所有格子的行號(hào)都與C2中所有格子的行號(hào)不等，即兩個(gè)子棋盤C1與C2在行上沒有重疊，則有R2（C）=R2（C1）*R2（C2）。

例如，圖2所示的棋盤可以分裂成

和，而且還可以進(jìn)一步分裂成

和。同理在列擺放中對(duì)列沒有約束，并且棋盤具有二維性，所以可以得出如下性質(zhì)（4）。性質(zhì)（4）：列擺放規(guī)則中，任意形狀的二維棋盤C都可以分裂成多個(gè)小棋盤，這些小棋盤即由原始棋盤的各個(gè)行（記為C1，C2，C3，…）所構(gòu)成，則有R2（C）=R2（C1）*R2 （C2）*R2（C3）…

三、新規(guī)則下棋盤多項(xiàng)式的計(jì)算

棋盤多項(xiàng)式的首要目標(biāo)就是便于快速計(jì)算與分析，而根據(jù)棋盤多項(xiàng)式的定義，要求出棋盤多項(xiàng)式即要確定定義2中各個(gè)系數(shù)ri（C）（i=0，1，2，…），顯然這些系數(shù)不宜采用逐一求解方法計(jì)算，而是可以靈活運(yùn)用性質(zhì)（2）和性質(zhì)（3）。

性質(zhì)（2）、（3）均具有遞歸特性，為了減少遞歸帶來的運(yùn)算量，在正則擺放規(guī)則下棋盤多項(xiàng)式的計(jì)算規(guī)律為：優(yōu)先考慮性質(zhì)（3），如果棋盤沒有分裂特性則采用性質(zhì)（2）計(jì)算。對(duì)于行擺放和列擺放規(guī)則，其計(jì)算規(guī)律同樣為優(yōu)先考慮分裂特性，其次考慮改進(jìn)后的性質(zhì)（2）。

（一）行擺放規(guī)則下棋盤多項(xiàng)式的計(jì)算

運(yùn)用對(duì)應(yīng)性質(zhì)（2）對(duì)圖2所示棋盤進(jìn)行展開，計(jì)算過程為：

R1（）=xR1（）+R1（）=x（xR1（）+R1（））+xR1（）+R1（）=（x3+2x2+x）+（x3+2x2+x）+xR1（）+R1（）=（x3+2x2+x）+（x3+2x2+x）+（x3+2x2+x）+（x2+2x+1） =3x3+7x2+5x+1

運(yùn)用對(duì)應(yīng)性質(zhì)（3）或者是性質(zhì)（4）對(duì)圖2所示棋盤進(jìn)行展開，計(jì)算過程為

R1（）=R1（）*R1（）=R1（）*R1（）*R1（）=（3x+1）（x+1）（x+1）=3x3+7x2+5x+1

該計(jì)算結(jié)果所表達(dá)的信息為：按行擺放規(guī)則，該棋盤最多可以擺放3個(gè)棋子（即該多項(xiàng)式為3次式），擺放3個(gè)棋子有3種擺法，擺放2個(gè)棋子有7種擺法，擺放1個(gè)棋子有5種擺法；擺放0個(gè)棋子有1種擺法。

對(duì)于行擺放規(guī)則，有下面兩個(gè)計(jì)算公式。

公式1：R1（ ）=（x+1）n

公式2：R1（ ）=nx+1

運(yùn)用數(shù)學(xué)歸納法很容易證明這兩個(gè)公式。

結(jié)合對(duì)應(yīng)性質(zhì)（4）和這兩個(gè)計(jì)算公式，可以得出下列計(jì)算公式3。

公式3：假設(shè)棋盤各列（C1，C2，C3，…）的格子個(gè)數(shù)（即行數(shù)）分別為a1，a2，a3，…，則有R1（C）=（a1x+1）（a2x+1）（a3x+1）…

例如，圖1棋盤的行擺放規(guī)則棋盤多項(xiàng)式為：R1（圖1棋盤）=（5x+1）（5x+1） （5x+1）（5x+1）（5x+1）=（5x+1）5。

（二）列擺放規(guī)則下棋盤多項(xiàng)式的計(jì)算

運(yùn)用對(duì)應(yīng)性質(zhì)（2）對(duì)圖4所示棋盤進(jìn)行展開，計(jì)算過程為：

R2（）=xR2（）+R2（）=x（xR2（）+R2（））+xR2（）+R2（）=（2x2+x）+（2x2+x）+（2x+1）=4x2+4x+1

運(yùn)用對(duì)應(yīng)性質(zhì)（3）或者是性質(zhì)（4）對(duì)圖4所示棋盤進(jìn)行展開，計(jì)算過程為：

R2（）=R2（ ）*R2（）=（2x+1）（2x+1）=4x2+4x+1

該計(jì)算結(jié)果所表達(dá)的信息為：按列擺放規(guī)則，該棋盤最多可以擺放2個(gè)棋子（即該多項(xiàng)式為2次式），擺放2個(gè)棋子有4種擺法，擺放1個(gè)棋子有4種擺法；擺放0個(gè)棋子有1種擺法。

與行擺放規(guī)則類似，對(duì)于列擺放規(guī)則，有下面兩個(gè)計(jì)算公式。

公式1：R2（）=（x+1）n

公式2：R2（）=nx+1

運(yùn)用數(shù)學(xué)歸納法很容易證明這兩個(gè)公式。

結(jié)合對(duì)應(yīng)性質(zhì)（4）和這兩個(gè)計(jì)算公式，可以得出下列計(jì)算公式3。

公式3：假設(shè)棋盤各行（C1，C2，C3，…）的格子個(gè)數(shù)（即列數(shù)）分別為a1，a2，a3，...，則有R2（C）=（a1x+1）（a2x+1）（a3x+1）…

例如，圖3棋盤的列擺放規(guī)則棋盤多項(xiàng)式為：R2（圖3棋盤）=（2x+1）（2x+1） （x+1）=4x3+8x2+5x+1。

經(jīng)過分析可以發(fā)現(xiàn)，關(guān)于主對(duì)角線對(duì)稱或者副對(duì)角線對(duì)稱的棋盤，其行擺放規(guī)則和列擺放規(guī)則的棋盤多項(xiàng)式相同。因?yàn)殛P(guān)于主對(duì)角線對(duì)稱的棋盤，第一行和第一列是關(guān)于主對(duì)角線對(duì)稱的，即它們具有相同的格子數(shù)，根據(jù)兩種情況下的計(jì)算公式3的特點(diǎn)，很容易確定這個(gè)結(jié)論的正確性。例如，圖1、圖2、圖3的行擺放和列擺放規(guī)則下的棋盤多項(xiàng)式均相同。

四、結(jié)束語(yǔ)

本文對(duì)目前的棋盤多項(xiàng)式分析技術(shù)提出了一種改進(jìn)思路，并針對(duì)改進(jìn)的思路給出了棋盤多項(xiàng)式的求解算法，使得這種分析技術(shù)能夠應(yīng)用于更多的排列組合性質(zhì)問題。由于很多排列組合性質(zhì)問題（例如圍棋）的最終求解目標(biāo)具有很高的復(fù)雜性，因此如何將棋盤多項(xiàng)式分析技術(shù)靈活有效的運(yùn)用于其中，使之能夠發(fā)揮出作用，是一個(gè)值得進(jìn)一步深入研究和探討的問題。

參考文獻(xiàn)：

1、Goldman J，Joichi J T，White D.Rook theory I Rook equivalence of Ferrers boards[M].Proceedings of the AMS，1975.

2、盧開澄，盧華明.組合數(shù)學(xué)[M].清華大學(xué)出版社，2002.

（作者單位：湖北經(jīng)濟(jì)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系）

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>