棋阵多项式生成算法及其在禁位排列中的应用研究

孙静

摘 要：棋阵多项式生成算法拥有自己独立的计算原理，主要结合多种方法比较算法中的优缺点，最后得出最优算法实现设计程序，通过禁位排列显示算法在显示应用中实现计算过程。本文介绍了棋阵多项式生成算法的基本概念与正规布局形式。随后对棋阵多项式的基本性质、传统计算方法以及禁位排列实际应用展开分析。

关键词：棋阵多项式生成算法;组合数学;棋盘;组合法;禁位排列

中图分类号：TP301.6 文献标识码：A 文章编号：2095-9052（2020）03-0188-02

在组合数学中存在棋阵多项式这一重要工具，它能够被应用于禁位排列、博弈问题中且具有广泛用途。同时可在棋阵多项式中生成常用算法，这其中就包括了分部相乘法、直接观察法以及关键点递归法。但客观讲，这3种算法适用性表现普遍较差，且技巧性强不易自动生成关键节点，存在各种缺点问题。为有效克服这些问题，需要研究提出一种新生成算法，即组合法。组合法具有较强的适用性，且非常利于程序实现，例如它在禁位排列中的应用就是一个较好的例子。

1 棋阵多项式生成算法的基本理论

棋阵多项式生成算法中的基本理论内容丰富，包含了棋盘、正规布局等内容，同时也要对棋阵多项式的基本性质进行分析，下文将一一列举分析。

1.1 棋盘的基本概念

一般来说，棋阵多项式中的棋盘都是由单位正方形所构成的，具体如图1。

如图1，在棋盘C中如果尝试删除某一个格子，它所在的行列中剩余的棋盘可标记为C1，棋盘C中在删除掉某一格子后所剩下的棋盘标记为C2。假设棋盘中棋盘1为C，那么可以将其它格子设置为C的黑点，棋盘2、3分别代表了棋盘C2以及C1。另外棋盘C中还包含了C3和C4两部分，且二者是相互分离的。棋盘4是可分离的，但其余棋盘是无法分离的[1]。

1.2 正规布局的基本概念

在正规布局中可将k个数量的棋子都放在棋盘C上构建多种布局方式，确保每行每列都存在一个棋子的布局并作为正规布局。假设棋盘C中存在正整数k，这就说明正规棋盘布局并不唯一。结合本文讨论内容，需要确保棋盘C上的正规布局个数作为一个重要参数存在，并将这个数记作。这里假设有棋盘，它在棋盘4中布置了两个棋子，且拥有两种正规布局如图2。

从图2布局1、2来看，它恰好对应的是排列13和排列23，可以见得在棋盘C与正整数k背景下正规布局与k个元素排列在一起并一一对应。

1.3 棋阵多项式的表达方法

棋阵多项式的表达方法如下：

另外对棋阵多项式的基本性质进行分析，首先它的第一个性质中有，针对某一个格子中所布局的棋子来讲，它只有布置棋子和不布置棋子两种可能。如果C1中的某一个棋子布局到棋盘C2上，增加方案书，则可得出以下公式为[2]：

其中棋盘C可分裂为C3和C4两部分。

2 棋阵多项式生成算法的传统计算方法分析

如上文所述，棋阵多项式生成算法中的传统计算方法中包括了多种算法，包括了直接观察法、分部相乘法、关键点递归法等。直接观察法主要适用于棋盘中较为简单的算法情况，因为它的棋格尺寸是小于3*3的;而分部相乘法比较适用于棋盘中的可分离多部分情况展开分析，分离获得第一种方法并进行计算，同时采用如下公式：

另外还有关键点递归法，它主要选择了棋盘中的关键点，结合点将棋盘中的部分内容整合，形成，合理选择关键点，并给出公式如下：

结合上式分析，可以发现关键点递归法中的算式是没有普遍性的，而且其适用性表现较差，也不具备太强的技巧性，不容易自动生成，无法满足当前的算法实际需要[3]。

3 棋阵多项式生成算法的创新算法应用——组合法

结合棋阵多项式的基本定义提出以下算式为：

在计算过程中需要将个棋子分布于棋盘C上并明确正规布局个数，进行棋盘正规布局定义，保证个棋子分布于棋盘C的行与列位置上，并满足条件集合全体构成一套完整的方案集，它上面的元素数量应该为。基于此可以分析并生成某一种方案，找到阴影中的横竖轴坐标并曲调其中所在行列的阴影，然后再寻找下一个阴影，曲调行列中的阴影，并以此类推，直到找到第k个阴影为止。整个过程中可生成一个完整的集合方案应该如下：

如上反复执行这一集合方案计算过程，可获得不同方案，考虑到位有限正整数，结合上述有限步进行计算，可证明组合法计算方法的有效性。结合棋阵多项式的表达方法即可求解得出相应的新棋阵多项式。新的棋阵多项式组合计算方法相比于上述传统计算方法在适用性方面表现更强，且可同时依靠计算机用递归算法满足优化计算流程，整体看来通俗易懂[4]。

4 棋阵多项式组合计算方法的算法描述应用

4.1 算法描述

第一，在棋阵多项式组合计算方法中生成算法，需要首先对算法进行初始化整合，确保棋盘方针中的棋子数量为count，临时数组中方案总数可设置为temp，且初始值可设置为0，它的取值一般分为3种情况，其中0表示没有棋子，1表示有棋子且可计数使用，2表示有棋子且不能被计数使用。

第二，判断棋阵多项式组合计算方法中的count值，如果count值为1，则需要按照行序优先原则进行方阵扫描检查，记录值为1的元素个数。可将数据保存在temp中。

第三，按照从头到尾的顺序进行方阵Array扫描，找到第一个值为1的单元元素。

第四，将Array所在行的列元素分别存入到TempRow中，列元素位置为0，且要有效曲调Array中的所在行列阴影内容。

第五，通过count值减1，再利用处理方阵A进行递归算法应用，获得结果与temp可相互积累。

第六，恢复现场，确保TempRow代替原有的Array，确保所在行与列完整。

第七，从Array中继续按照行列优先顺序进行扫描排列，找到下一个值为1的元素，在扫描Array后返回方案总数temp中[5]。

4.2 禁位排列应用

在禁位排列应用中可将主动禁止的某些元素放到不同位置，通过排列定义了解到n个元素的具体排列位置，客观反映不同元素的不同位置，构建一个围绕n阶的方针映射体系，即禁位排列代表了一个n阶方阵的对应排列。比如某一个单位划分出了5个工作区域，其中每个工作区域的工作人员不得随意进入其它任何一个工作区域，如图3。

如图3中，黑色阴影部分即为禁区，它表示不同区域的工作人员不得擅自闯入禁区，结合这一目标可以计算禁位排列的具体方案数与排列方案。满足棋盘大小动态变化，保证在10x10的整形数组中表示前n行与前n列内容[6]。

5 结语

在组合数学中研究棋阵多项式组合算法，探讨其禁位排列技术内容是具有一定技術研究前景的，它能够基于计算机软件理论基础深入研究棋阵多项式这一实用性工具，解决某些禁位排列问题，整体来看通俗易懂且易于推广。

参考文献：

[1]牛立新，等.棋阵多项式生成算法及其在禁位排列中的应用[J].计算机工程与应用，2006，42（10）：91-93+150.

[2]侯政.用图论解决几个特殊的禁位排列问题[J].江西电力职业技术学院学报，2015（2）：38-39+48.

[3]壹号元素（广州）科技有限公司.一种无序排列的宽禁带半导体纳米线的同位素电池：CN201710849974.0[P].2018-03-09.

[4]史岚，吕建辉.基于禁位排列原理的路由决策算法[J].计算机应用研究，2014，31（1）：257-260.

[5]姜学杰.错位排列和禁位排列及其排列数公式[J].数学学习与研究，2011（9）：89.

[6]梁作松.车多项式在解决禁位排列问题中的应用[J].高等函授学报（自然科学版），2009（3）：55-56.

（责任编辑：李凌峰）