四方连块的正方形拼图游戏

发布于:2020-06-26 分类:人科专业   

摘要:多方块的矩形拼图(Tiling the rectangle)是一个有趣而常见的拼图游戏,它的基本规则是:每一种等面积的多方连块至少都用一个来拼一个矩形。「四方连 块」(tetrominoes)是指四个单位正方形以边与边相连接而成,并扣除图形旋转、镜射,所形成之五种不同形状的几何平面图形。本文探讨四方连块的 拼图问题。

多方块的矩形拼图(Tiling the rectangle)是一个有趣而常见的拼图游戏,它的基本规则是:每一种等面积的多方连块至少都用一个来拼一个矩形。「四方连块」(tetrominoes)是指四个单位正方形以边与边相连接而成,并扣除图形旋转、镜射,所形成之五种不同形状的几何平面图形,如下图所示,分别为 L 型、Z 型、O 型、I 型、T 型。

四方连块的正方形拼图游戏在四方连块的拼图游戏中,我们已经知道:若每个四方连块恰用一个并无法拼出一个面积为 $$20$$ 单位的矩形;若是每种四方连块恰用二个,我们可以拼出 $$5\times 8$$ 和 $$4\times 10$$ 的矩形。然而能否拼出恰用 $$9$$ 个四方连块组成最小可能的 $$6\times 6$$ 正方形?这个问题的答案显然是肯定的,只要嚐试着动手拼拼看,应该马上可以得到很多种不同的拼法,下图为 O 型、I 型、T 型、Z 型 各 $$2$$ 个和 $$1$$ 个 L 型的例子:

四方连块的正方形拼图游戏四方连块的正方形拼图游戏几次嚐试之后,我们一直无法拼出一个最极端状况的拼法,也就是:是否能用 $$5$$ 个同一型的四方连块和其他四型的四方连块各 $$1$$ 个来拼成 $$6\times 6$$ 正方形?这个问题的解答可以藉由一个拼多方块常用的手法加以解决,首先将 $$6\times 6$$ 正方形涂成黑白相间的棋盘(如下图),

四方连块的正方形拼图游戏而将这五个类型的四方连块放在此棋盘上时, L 型、Z 型、O 型、I 型恰各覆盖 $$2$$ 黑格和 $$2$$ 白格,但 T 型只可能覆盖 $$1$$ 黑格、$$3$$ 白格或是 $$3$$ 黑格、$$1$$ 白格,由于 $$6\times 6$$ 正方形棋盘上黑、白格数相同,所以若要能将此棋盘盖满,T 型四方连块的个数必需为偶数,因此不可能用 $$5$$ 个同一型的四方连块和其他四型的四方连块各 $$1$$ 个来拼成 $$6\times 6$$ 正方形。藉此我们也可以知道这个拼图游戏中的 T 型个数只可能是 $$4$$ 个或 $$2$$ 个。

在诸多四方连块拼成 $$6\times 6$$ 正方形的方法中,我们可以发现有一些拼法可以将 $$6\times 6$$ 正方形分割成两个较小的矩形,下图为其中一个例子($$6\times 4$$、$$6\times 2$$):
四方连块的正方形拼图游戏在这个例子中,可以透过将 $$6\times 4$$ 和 $$6\times 2$$ 矩形旋转 $$180^\circ$$、水平及铅直镜射来重新组合成 $$6\times 6$$ 的正方形,扣除组合成大正方形后本身图形可由旋转、镜射变换而成的相同图形,共可组合出 $$8$$ 种不同拼法。所以当我们进一步想求出用四方连块拼出  $$6\times 6$$ 正方形的所有可能拼法数时,可把可能的拼法分成两类,一类的拼法是可以将 $$6\times 6$$ 正方形拆成更小的两个矩形,另一类则是不行。若要将 $$6\times 6$$ 的正方形拆成两个矩形,这两个小矩形的面积必定是 $$4$$ 的倍数,故只可
能拆成 $$6\times 4$$、$$6\times 2$$(或 $$6\times 2$$、$$6\times 4$$)两个矩形,而 $$6\times 2$$ 的矩形的拼法只有如下 $$4$$ 种(将旋转、镜射后相同的图形视为同一种):

四方连块的正方形拼图游戏由左至右分别为:$$3$$ 个 O 型、$$1$$ 个 O 型 $$2$$ 个 L 型、$$1$$ 个 O 型 $$2$$ 个 I 型、$$1$$ 个 I 型 $$2$$ 个 L 型

上面的 $$4$$ 种 $$6\times 2$$ 的矩形中皆不含 T 型和 Z 型,所以 $$6\times 4$$ 的矩形可依包含的四方连块种类分成:只含 T,Z, L 型、T,Z,I 型、T,Z,O 型、T,Z,L,I 型、T,Z,L,O 型、T,Z,I ,O 型及T,Z,I,O,L 型;而这七个种类不一定都会存在,经检验可知只含 T,Z,O 和只含 T,Z,I,O 的 $$6\times 4$$ 矩形是不可能存在的,而在剩下 $$5$$ 种 $$6\times 4$$ 矩形中,有一些又可再拆成两个更小的矩形,讨论可能的拆法有:拆成  $$5\times 4$$ 和 $$1\times 4$$、$$4\times 4$$ 和 $$2\times 4$$、$$3\times 4$$ 和 $$3\times 4$$,在需要含 T 型和 Z 型的条件下,可构成小矩形的种类并不多,读者可以试着把所有的可能情况找出来。利用拆成更小矩形的方式可以更有效率地计算可能的拼图方式,例如下图由 $$2\times 4$$、$$4\times 4$$ 和 $$6\times 2$$ 矩形组合出 $$6\times 6$$ 正方形:

四方连块的正方形拼图游戏因为 $$2\times 4$$ 矩形有原图形及水平镜射两种图形,$$4\times 4$$ 矩形有原图形及水平镜射的图形并皆可再旋转 $$90^\circ$$、$$180^\circ$$、$$270^\circ$$,所以可组合出 $$2\times 2\times 4=16$$ 种不同的 $$6\times 4$$ 矩形,又这 $$16$$ 个矩形除了原图形,皆可旋转 $$180^\circ$$ 或作铅直镜射,加上 $$6\times 2$$ 矩形有原图形和旋转 $$180^\circ$$ 的图形,故有 $$16\times 3\times 2 = 96$$ 种不同方式组合出 $$6\times 6$$ 正方形。要计算以四方连块(每种类型至少一个)组成 $$6\times 6$$ 正方形拼图方式的方法数,并不是一件容易的事,不过我们应该可以利用上叙的分类方式,加上「人工检验」或利用电脑检验,进一步把拼出 $$6\times 6$$ 正方形的方法数计算出来。


参考资料


正文到此结束.