五连珠问题..docx

五连珠问题摘要五连珠好比我们的五子棋，五子相连为获胜而本文就对五子棋相关的五连珠问题做出一些研究，在棋盘上的每个小方格中都放上棋子，从中取出一些棋子，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连，求满足条件的取出最少的棋子数。对于这道题目而言，三个问题从特殊到一般，从二维平面到三维空间。对于二维特殊问题的求解，可以根据简单的数学推理与图形演示来表达。而对于二维平面和三维空间这个一般问题而言，就不能通过简单的图示来表示，只能够通过计算机编程与优化进行讨论，而对于解法，我们则采用回溯法和递归的思想。针对问题一，在6*7的棋盘上取出一些棋子，我们采用数学推理证明的思想得出答案，通过画图找到一种取出8个棋子满足，之后我们通过在一些规律下的逻辑推理证明7个确实不满足要求，所以8个为最终解。针对问题二，则是相对问题一的一般情况，将棋盘的大小扩充到m*n的情况，此时利用数学推理证明的思想是行不通的，我们的想法是首先采用0和1的思想，将需要取出的棋子的位置标为0，有棋子的位置标为1 。每一个棋盘的位置点可以用一个二维数组来表示。通过对题目的数学理解，我们发现此题与“八皇后问题”十分类似，都采用“马走日”的思想。但对于“五子连珠”问题，每行每列可以有多个“0”元素，显然较为复杂。但是我们可以将其抽象为“五皇后”问题，然后进行5*5矩阵的叠加与和递归的想法，首先把第一行处理，然后其他行列根据第一行进行排列，最后输出整个矩阵与所求k值。 之后利用这个数学模型求出17*13棋盘的满足条件的k值为44。针对问题三，是在问题二的二维平面扩充到三维的立体网格m*n*p的棋盘，这个问题和第二问题的想法是相似的，只是将“平面八皇后问题”转化为“空间八皇后问题”。可以考虑将空间整数点用三维坐标表示后，首先固定其中一个与 X轴平行的平面作为初始平面（此平面的选取可以为任意与X轴，Y轴，Z轴垂直的平面），利用问题二中算法定出这个面的棋子摆放位置，然后分别利用其行，列来确定行列所在垂直平面上棋子的摆放位置，此时整个空间的点已经摆放完整，可以利用与最初选定的平面平行的平面进行验证斜线和这些平面上的点是否满足条件。最后利用计算机模型求出6*7*6的空间网格求出满足题意的最小k值为51。关键字：穷举法 微元棋盘 C 语言目录摘要问题重述1.1问题的说明1.2问题的提出问题分析2.1 问题一分析2.2 问题二分析2.3 问题三分析模型假设四、符号说明五、模型的建立与求解5.1 问题一的求解5.2 问题二的模型建立和解决5.3 问题三的模型建立和解决模型评价6.1 模型优点6.2 模型缺点6.3 模型改进参考文献附录问题重述1.1问题的说明 一个的空间长方体网格每个小方格的中心点各放一个棋子。如果两个棋子所在的小方格共边或共顶点，那么称这两个棋子相连。现从这个棋子中取出一些，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连。在三维空间中，每个格子是一个1×1×1的小正方体。在这些格子中同样都填满了棋子，现要从中抽取一部分，使得在每种平面，包括横向所截的个平面，纵向所截的个平面，竖直方向所截的个平面，在每个平面上在横向、纵向、斜方向上都不出现5子连珠。并且要求在空间斜线上也不出现5子连珠。1.2问题的提出1）棋盘问题 在的长方形棋盘的每个小方格的中心点各放一个棋子，用数学的方法解决最少取出多少个棋子才能满足要求？并说明理由。同时给出一种去掉棋子的方式。2）二维问题针对任意规模的棋盘，要求满足的条件与问题1相同。问至少去掉多少个棋子，可以使没有五个在一条直线（横、竖、斜方向）上依次相连。并针对13×17的长方形棋盘，给出具体的求解结果，并将最后结果给出直观的棋盘表格显示。3）三维问题 在三维空间的空间长方体网格，问最少去掉多少个棋子可以满足要求。请建立一般问题的数学模型。针对的空间网格用计算机求解，并给出具体的解结果。问题分析2.1问题一分析对于问题，题目要求最少取出多少个棋子才能满足棋盘上剩下的棋子没有五个在一条直线（横、竖、斜方向）上依次相连。那么如果证明至少需要取出个棋子。可采用的一种思路是：理论上证明取个棋子不能满足要求，而我确实找到一种取出个棋子就可以满足要求的取法。另一种思路是采用一种方法证明至少需要取个棋子才能满足要求，而我确实找到一种取出个棋子就可以满足要求的取法。2.2问题二分析对问题1中使用数学证明的方法，只能解决规模很小的问题。而且针对不同的规模，所使用的数学技巧会不同。这样就不具有一般性。一个很自然的想法是利用数学建模的方法建立一般模型，然后设计算法或利用软件求解。2.3问题三分析题目要求每种平面，包括横向所截的个平面，纵向所截的个平面，竖直方向所截的个平面，在每个平面上在横向、纵向、斜方向上都不出现5子连珠。并且