王海燕，黄 骏

(1.宿迁学院信息工程学院，江苏 宿迁 223800； 2.南方科技大学计算机科学与技术系，广东 深圳 518055)

一种分数维改进的长方棋盘覆盖算法

王海燕1，黄 骏2

(1.宿迁学院信息工程学院，江苏 宿迁 223800； 2.南方科技大学计算机科学与技术系，广东 深圳 518055)

基于含有一个特殊方格的ik×jk棋盘结构，提出了一种改进与推广的长方棋盘覆盖算法。利用类似L型骨牌总是可以覆盖其余不含特殊方格子棋盘的顶点交汇处这一特点，对不含特殊方格的子棋盘算法进行改进，采用直接+间接递归及分治策略思想，以i=j=2为例设计了4个模块函数。该算法不仅避免了非特殊方格递归求解的盲目性，也减少了棋盘深层递归的层数。实验结果表明：与已有算法相比，改进的算法具有更好的性能。更加便于任意形状图像加密过程中所需的行与列不相等的二维随机密钥的生成。

棋盘覆盖；分治策略；直接递归；间接递归；图像加密

0 引言

棋盘问题是一个经典问题，早在1848年的时候，德国象棋大师马克思就提出解决8个女皇的棋盘覆盖难题的第一套方案，德国数学家高斯先生把8个女皇的棋盘覆盖推广到了n个女皇。到了1946年的时候，美国哲学家马克思又提出了二缺格国际象棋棋盘的类似围棋棋盘的双格骨牌填充方法的难题，掀起了第二次棋盘覆盖的研究热潮，1973年的时候，这个难题被美国数学家Gomory一举解决，到了20世纪80年代，基于四格骨牌的俄罗斯方块的游戏由此产生，今天类似的算法已经被广泛应用于数学领域[1-4]及计算机领域的文件加密[5]、图像加密[6-7]等技术处理中。……