关于棋盘上的马控制问题.pdf

关于棋盘上的马控制问题 复旦附中 2010 届 8 班 杨佼文 张宸元 范瀛祥 指导老师：张建国 目前来说,MK(m,n)的精确求解仍然是一个世界难题. 本文通过计算机编程, 染色, 举例, 反证等方法对 m*n 棋盘上的马控制数 MK(m,n) 进行了 研究. 其中,对于 m 和 n 的值比较小的时候做出了精确求解,并且对于 m=4 的情况进行了探索,得到 了一种重要的马的摆法,从而提出了解决这一问题的一个可行方法,并对于 m,n 比较大时 MK(m,n) 的上界作了估计. 本文还指出了这一问题在各方面的应用前景. m*n 棋盘上的马控制问题是一个容量很大的问题,至今尚未解决 m*n 棋盘上的马控制数,连 n*n 棋盘上的马控制问题也只得到了为数极少的几个解, 比如 5*5 的棋盘上至少需要 5 个 马.[1] 由于m*n 棋盘上马控制数的求解十分困难，尤其是当 m ，n 都比较大的情况. 于是我们转而考虑 m*n 棋盘马控制数的一个范围. 研究目的：估算 M*N 棋盘上马控制数的上界。 研究难点：马的走法较其他棋子而言十分独特，难以通过局部分析从而推广。 研究思路：试图从先前已经研究过的简单情况入手，即通过对 1*1 到 10*10 的图形进行拼接 来达到最终的估算目的。 1 定义 1 一般地，在方格棋盘中，如果一个棋子占据了某个格子或着按照规则走一步就可以到达这个 格子，则称该棋子控制了这个格子。[1] 定义 2 在 m*n 棋盘中放若干只棋，若对棋盘中的任何一个格，都至少被其中的一只所控制， 则称这些棋控制了棋.同一类型的棋Q 对棋盘的控制数简称为棋盘的 Q 控制，如棋盘的马控 制，棋盘的车控制. [1] 定义 3 在 m*n 的Q 控制中，所需要的棋 Q 的最少个数称为m*n 棋盘的 Q 控制数，记作 QK （m ，n ）.比如m*n 的棋盘马控制数可记为MK(m,n) [1] 在这里,我们先就 m, n 比较小的情况做一下探索研究 Part 1 (第一部分) 当m 和 n 都比较小时, 可以通过计算机编程得出 MK(m,n) 的值 m/n 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 4 4 4 4 4 6 8 8 3 4 4 4 4 6 8 8 4 4 4 4 6 8 8 5 5 6 7 8 9 6 8 8 8 7 10 12 8 12 9 以下是程序的源代码（free pascal ） const maxn=10; x:array[1..9]of longint=(0,+1,+2,+2,+1,-1,-2,-2,-1); y:array[1..9]of longint=(0,-2,-1,+1,+2,-2,-1,+1,+2);——以马所在的格子为（0，0 ），分别 对应于一匹马可以控制的 9 个格子 var a:array[-1..maxn+2,-1..maxn+2]of longint; n,m,mid,l,r:long