棋盘多项式的一种改进思路

摘要：棋盘多项式是在分析解决棋类问题过程中所产生的一种排列组合分析方法，由于它对棋子的排列规则有较严格的约束，从而导致很多类似于棋盘排列的问题难以直接应用这种棋盘多项式分析方法，因此文章对棋盘多项式做出了改进，使之能够为更多排列组合问题提供一种分析思路。

关键词：棋盘多项式；正则摆放；行摆放；列摆放

一、引言

棋盘多项式是在分析棋盘内棋子分布方案的过程中提出的一种方法，它不仅给棋盘上的棋子分布问题提供了较好的分析工具，而且也为其他很多排列组合问题提供了一种较为有用的分析方法。

定义1：一个n*n个方格组成的图形去掉其中某些方格，称为一个棋盘，用C表示，如图1、图2、图3、图4所示棋盘。

在棋盘中摆放棋子（去掉的格不能摆放），如果每行每列最多摆一个棋子，则这种摆放称为正则摆放，如图1所示。棋盘多项式就是描述这种正则摆放方案数的一种方法。

定义2：对于一个棋盘C而言，其棋盘多项式表示为R（C），则有：

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

其中ri（C）表示i个棋子摆放在棋盘C上有多少种摆法，并且规定：r0（C）=1；当C为空棋盘时，R（C）=R（）=1；

定义3：在棋盘C中任取一个格，将这个格去掉，得到的棋盘记作CP，把这个格所在的行和列都去掉得到的棋盘记作CI。则棋盘多项式具有如下性质：

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

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

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

性质（3）中的分裂特性，是指C=C1∪C2，C1∩C2=φ，并且C1所有格子所在的列和行都与C2中所有格子所在列和行不等，即两个子棋盘C1与C2在行列上没有重叠，如图3所示棋盘可以分裂成□和。图2所示棋盘，按照性质（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，它所表达的信息为：该棋盘最多摆放2个棋子（即该多项式为2次式），摆放2个棋子有4种摆法；摆放1个棋子有5种摆法；摆放0个棋子有1种摆法。

图3所示棋盘，按照性质（3）展开有：

R（）=R（□）R（ ）=（x+1）（xR（□）+R（））=（x+1）（x2+x+xR（□）+R（））=（x+1）（2x2+2x+2x+1）= 2x3+6x2+ 5x+1，同理，它所表达的信息为：该棋盘最多摆放3个棋子（即该多项式为3次式），摆放3个棋子有2种摆法；摆放2个棋子有6种摆法；摆放1个棋子有5种摆法；摆放0个棋子有1种摆法。

棋盘多项式是棋盘上棋子摆放方案数的一种表示，它对于分析研究复杂排列组合问题有着重要的作用，如围棋、象棋、机器人及计算机智能排课等问题。但是它对于棋子摆放的约束条件，却大大限制了其应用范围，如象棋中博弈一方的2个车可以摆放在同一列或同一行上，排课系统中同一门课可以排在不同天的同一时间段，即课表中同一行上。为此，本文提出棋盘多项式的一种改进思路，将其条件“棋盘中棋子既不能处于同一行也不能处于同一列”进行扩充，从而可以使棋盘多项式分析技术运用于更多的实际问题中。

二、两种改进策略

针对正则摆放的限制条件，可以提出两种改进方法。这两种改进后的棋盘多项式与正则摆放的棋盘多项式具有相同的含义与性质，只是棋子摆放条件进行修改。

第一，取消对行的限制，即允许在同一行上同时摆放多个棋子，但同一列只能摆放一个棋子，我们称这种摆放规则为行摆放。例如智能排课问题中，一天中同一门课一般不允许排两次，但允许排在不同天的同一时间段，即属于行摆放规则。行摆放规则下的棋盘多项式记为R1（C），对于棋盘中任意一格如果去掉此格得到的棋盘记为C1p及去掉该格子所在列后得到的棋盘记为C1I，则有其对应性质（1）、性质（2）和性质（3），性质（1）与正则摆放规则中的性质（1）保持一致。性质（2）：R1（C）=xR1（C1I）+R1（C1p）。性质（3）：如果棋盘C可以分裂成小棋盘C1和C2，这种分裂特性是指C=C1∪C2，C1∩C2=φ，并且C1所有格子的列号都与C2中所有格子的列号不等，即两个子棋盘C1与C2在列上没有重叠，则有R1（C）=R1（C1）*R1（C2）。

例如，图2所示的棋盘可以分裂成

和，而且还可以进一步分裂成□和□。由于行摆放中对行没有约束，并且棋盘具有二维性，所以可以得出如下性质（4）。

性质（4）：行摆放规则中，任意形状的二维棋盘C都可以分裂成多个小棋盘，这些小棋盘即由原始棋盘的各个列（记为C1，C2，C3，…）所构成，则有R1（C）=R1（C1）*R1（C2）*R1（C3）…。

第二，取消对列的限制，即允许在同一列上同时摆放多个棋子，但同一行只能摆放一个棋子，我们称这种摆放规则为列摆放。同理，将列摆放规则下的棋盘多项式记为R2（C），对于棋盘中任意一格如果去掉此格得到的棋盘记为C2p及去掉该格子所在行后得到的棋盘记为C2I，则有其对应性质（1）、性质（2）和性质（3），性质（1）与正则摆放规则中的性质（1）保持一致。性质（2）：R2（C）=x R2（C2I）+R2（C2p）。性质（3）：如果棋盘C可以分裂成小棋盘C1和C2，这种分裂特性是指C=C1∪C2，C1∩C2=φ，并且C1所有格子的行号都与C2中所有格子的行号不等，即两个子棋盘C1与C2在行上没有重叠，则有R2（C）=R2（C1）*R2（C2）。

例如，图2所示的棋盘可以分裂成

和，而且还可以进一步分裂成

和。同理在列摆放中对列没有约束，并且棋盘具有二维性，所以可以得出如下性质（4）。性质（4）：列摆放规则中，任意形状的二维棋盘C都可以分裂成多个小棋盘，这些小棋盘即由原始棋盘的各个行（记为C1，C2，C3，…）所构成，则有R2（C）=R2（C1）*R2 （C2）*R2（C3）…

三、新规则下棋盘多项式的计算

棋盘多项式的首要目标就是便于快速计算与分析，而根据棋盘多项式的定义，要求出棋盘多项式即要确定定义2中各个系数ri（C）（i=0，1，2，…），显然这些系数不宜采用逐一求解方法计算，而是可以灵活运用性质（2）和性质（3）。

性质（2）、（3）均具有递归特性，为了减少递归带来的运算量，在正则摆放规则下棋盘多项式的计算规律为：优先考虑性质（3），如果棋盘没有分裂特性则采用性质（2）计算。对于行摆放和列摆放规则，其计算规律同样为优先考虑分裂特性，其次考虑改进后的性质（2）。

（一）行摆放规则下棋盘多项式的计算

运用对应性质（2）对图2所示棋盘进行展开，计算过程为：

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

运用对应性质（3）或者是性质（4）对图2所示棋盘进行展开，计算过程为

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

该计算结果所表达的信息为：按行摆放规则，该棋盘最多可以摆放3个棋子（即该多项式为3次式），摆放3个棋子有3种摆法，摆放2个棋子有7种摆法，摆放1个棋子有5种摆法；摆放0个棋子有1种摆法。

对于行摆放规则，有下面两个计算公式。

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

公式2：R1（ ）=nx+1

运用数学归纳法很容易证明这两个公式。

结合对应性质（4）和这两个计算公式，可以得出下列计算公式3。

公式3：假设棋盘各列（C1，C2，C3，…）的格子个数（即行数）分别为a1，a2，a3，…，则有R1（C）=（a1x+1）（a2x+1）（a3x+1）…

例如，图1棋盘的行摆放规则棋盘多项式为：R1（图1棋盘）=（5x+1）（5x+1） （5x+1）（5x+1）（5x+1）=（5x+1）5。

（二）列摆放规则下棋盘多项式的计算

运用对应性质（2）对图4所示棋盘进行展开，计算过程为：

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

运用对应性质（3）或者是性质（4）对图4所示棋盘进行展开，计算过程为：

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

该计算结果所表达的信息为：按列摆放规则，该棋盘最多可以摆放2个棋子（即该多项式为2次式），摆放2个棋子有4种摆法，摆放1个棋子有4种摆法；摆放0个棋子有1种摆法。

与行摆放规则类似，对于列摆放规则，有下面两个计算公式。

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

公式2：R2（）=nx+1

运用数学归纳法很容易证明这两个公式。

结合对应性质（4）和这两个计算公式，可以得出下列计算公式3。

公式3：假设棋盘各行（C1，C2，C3，…）的格子个数（即列数）分别为a1，a2，a3,...，则有R2（C）=（a1x+1）（a2x+1）（a3x+1）…

例如，图3棋盘的列摆放规则棋盘多项式为：R2（图3棋盘）=（2x+1）（2x+1） （x+1）=4x3+8x2+5x+1。

经过分析可以发现，关于主对角线对称或者副对角线对称的棋盘，其行摆放规则和列摆放规则的棋盘多项式相同。因为关于主对角线对称的棋盘，第一行和第一列是关于主对角线对称的，即它们具有相同的格子数，根据两种情况下的计算公式3的特点，很容易确定这个结论的正确性。例如，图1、图2、图3的行摆放和列摆放规则下的棋盘多项式均相同。

四、结束语

本文对目前的棋盘多项式分析技术提出了一种改进思路，并针对改进的思路给出了棋盘多项式的求解算法，使得这种分析技术能够应用于更多的排列组合性质问题。由于很多排列组合性质问题（例如围棋）的最终求解目标具有很高的复杂性，因此如何将棋盘多项式分析技术灵活有效的运用于其中，使之能够发挥出作用，是一个值得进一步深入研究和探讨的问题。

参考文献：

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

2、卢开澄,卢华明.组合数学[M].清华大学出版社,2002.

（作者单位：湖北经济学院计算机科学与技术系）

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”

推荐访问:多项式 棋盘 思路 改进

---