棋盘覆盖问题

来自计算思维百科
跳转至: 导航搜索
棋盘覆盖问题1.png

在一个2^k*2^k的方格组成的棋盘中,例如右图中的4*4的棋盘,有一个特殊方格(黄色),要用如下不同形式的L型骨牌把棋盘上除了特殊方格的其他所有方格覆盖,且骨牌之间不能有重叠,怎样摆放呢?

涉及的计算思维

解决这个问题我们可以使用分治法,分治法是将复杂问题分成若干个与原问题同类型的简单子问题进行解决,然后合并子问题的解得到原问题的解。体现了计算思维的递归思想。

解决方案

方案一——分治法

先将棋盘分成相等的四块子棋盘,其中特殊方块位于四个中的一个,我们的目标是使没有特殊方块的三个子棋盘中也都要存在一个特殊方块,我们可以防止一个L型骨牌达到这个效果,如下图所示。这时,四个子棋盘的情况都是相同的,我们拿出一个子棋盘进行处理。

对于这个子棋盘而言,和原始问题是一样的,仅仅是问题的规模大小变小了,那么最小的子棋盘是多大呢?很明显,是2×2的子棋盘,而2×2的棋盘中有一个特殊棋子,只用加一个骨牌就可以覆盖住,这样,就可以顺利地填好给定的所有棋盘。

棋盘覆盖问题2.png