Tromino谜题(棋盘覆盖)

来自计算思维百科
跳转至: 导航搜索
Tromino谜题(棋盘覆盖)2.png

Tromino谜题是这样的:一个2nX2n的棋盘中缺失了一个方块,如果利用三个邻接方块组成的L型瓦片覆盖住整个棋盘。

Tromino谜题(棋盘覆盖)1.png

解决方案

考虑大小为2x2的棋盘,很明显就是L型覆盖三个格子,那对于规模更大的棋盘呢?我们可以采用分治的思想。

1将棋盘分为四部分,确定缺失方格的位置

2用Tromino覆盖当前最中心区域除了缺失方块所在区域

3此时四部分区域都为典型的Tromino棋盘,按照次序来重复2直到覆盖完整个棋盘

Tromino谜题(棋盘覆盖)3.png

可以体现的计算思维

从上面的分析中容易看出在解决问题的过程中,问题的实例被分解成了几个规模更小的问题的实例且规模相同,对小规模的问题求解,这体现了计算思维的约简特点。