五格骨牌

五格骨牌(Pentomino),又称五连块五连方五连方块伤脑筋十二块,是由五个全等正方形连成的多格骨牌,反射或旋转视作同一种共有十二种,可以英文字母代表。五格骨牌的相关问题及游戏是娱乐数学中流行的问题[1]。五格骨牌的谜题,最早是英国人亨利·杜德耐于1907年所发明,书名《坎特伯雷趣题和其他奇特问题》(Canterbury Puzzles and Other Curious Problems)[2]

12个五格骨牌可以组成18个不同的形状,其中6个没有对称的有加上其镜射后的形状

五格骨牌中每一个都满足康威准则,因此用任何一个都可以密铺整个平面[3]。所有具有对掌性英语Chirality (mathematics)的五格骨牌都可以在不镜射的条件下密铺整个平面[4]

历史

 
所有的五格骨牌,以及其对应的两组命名,上方的命名是条目中会使用的名称,下方的命名是康威的命名

五格骨牌的正式定义是由美国教授所罗门·格伦布在1953年开始定义,后来列在1965年出版的书籍《Polyominoes: Puzzles, Patterns, Problems, and Packings》[1][5]中。之后马丁·加德纳在《科学美国人》杂志1965年10月的数学游戏专栏英语Mathematical Games column中介绍,引起大家的兴趣。格伦布创建了五格骨牌的英文pentomino,源自古希腊语 πέντε / pénte(5),而-omino是采用domino(西洋骨牌),刻意的将domino前面的 d 视为是希腊文字首 di- (二个)的变形。格伦布用12个和五格骨牌外形较类似的英文字母来为五格骨牌命名。

约翰·何顿·康威有另外一个针对五格骨牌命名的系统,其中用O来代替I、Q来代替L、R来代替F、S来代替N。此命名法中,一些五格骨牌和其名称的关系较不直觉,不过好处是使用了连续的12个英文字母。在讨论康威生命游戏时会用到这个命名系统,例如用R骨牌来代替F骨牌。

对称性

  • F, L, N, P, Y的骨牌由于既非线对称亦非点对称,所以总共有8种固定五格骨牌,旋转后可以产生四种骨牌,镜射后再旋转后可以产生另外四种骨牌,其空间对称群只有恒等函数
  • T, U的骨牌由于有一条和格线平行的对称轴,因此只有4种固定五格骨牌。其空间对称群有二个元素,除了恒等函数外,还包括相对于对称轴的镜射
  • V, W的骨牌由于有一条和格线有45度夹角的对称轴,因此只有4种固定五格骨牌。其空间对称群有二个元素,除了恒等函数外,还包括相对于对称轴的镜射。
  • Z的骨牌有一个对称点,是二次的旋转对称英语Rotational symmetry,因此也只有4种固定五格骨牌,旋转后可以产生二种骨牌,镜射后再旋转可以产生另外二种骨牌。其空间对称群有二个元素,除了恒等函数外,也包括180度的旋转。
  • I的骨牌有两条对称轴(都平行格线)跟一个对称点,因此只有2种固定五格骨牌。其空间对称群有四个元素:恒等函数,两个镜射以及180度的旋转。I的骨牌是 n = 2 的二面体群,也称为克莱因四元群
  • X的骨牌有四条对称轴跟一个对称点,因此只有唯一一种固定五格骨牌。其四条对称轴分别平行格线以及二条对角线,也有四次的旋转对称。其对称轴是n = 4 的二面体群,有八个元素。

F, L, N, P, Y和Z的骨牌有对掌性英语Chirality (mathematics),因此若考虑无法翻面的单面骨牌,要加上这些骨牌的镜射(F', L', N', Q', Y', Z'),共有18种单面骨牌。若骨牌不允许旋转(固定骨牌),本段分类的第一类要乘以8,后面三类(T、U、V、W、Z)要乘以4,I要算2次,X只算1次,因此共有5×8 + 5×4 + 2 + 1 = 63 个固定的五格骨牌。

以下是L, F, N, P, Y 骨牌的八种可能放法:

           

长方形填充

标准的五格骨牌谜题是用五格骨牌密铺长方形,骨牌不能重叠,也不能留下没有骨牌的空格。每个五格骨牌的面积都等于五个单位方形,因此长方形的面积需等于60个单位方形。可能的尺寸有6×10, 5×12, 4×15 及3×20。狂热智力游戏玩家可能会徒手玩几个小时来求解这类问题。另一个问题的挑战性更大,是计算某一尺寸下有几种解法,一般会需要配合搜索算法来进行。

6×10的问题最早是由Colin Brian英语C. Brian HaselgroveJenifer Haselgrove英语Jenifer Haselgrove.[6]所解出,共有2339个解答,2339个解答中,不考虑若将整个长方形旋转或是镜射的解,旦若其中部分五格骨牌旋转或是镜射,则视为是不同的解。5×12的问题有1010个解,4×15的问题有368个解,3×20的问题只有二个解(图中的是其中一个解,将L, N, F, T, W, Y, Z方块组成的方块组镜射后,可得到另一个解)。

另一个比较简单(对称性较高)的问题,是中间挖掉2×2方块的8×8正方形,此问题最早由达纳·斯科特在1958年解出[7],共有65种解。斯科特的求解方式也是回溯法计算机程序的早期应用之一。此问题的变体是正方形中的4个空格在其他的位置,大部分的变体都可以解,除非空格都集中在某两个角附近,让两个角都要用P骨牌填充,或是强迫在角落放入T骨牌或U骨牌,使得出现其他五格骨牌无法填满的格子。

 

目前已有高效的算法可求解五格骨牌的密铺问题,像高德纳也有创建类似的算法[8]。若在现今的个人电脑上执行,只要几秒钟就能解出五格骨牌的摆放方式。

利用所有的n格骨牌来密铺长方形的问题,只有在n = 0, 1, 2和5时才有解。

平面填充

所有12种五格骨牌都满足康威准则,因此都可以只用同一种五格骨牌,来填满整个平面。

五立方体及立体填充

五立方体(pentacube)是由五个立方体组成的多连立方体,共有29个,其中有12个是高度为1的五格骨牌,另外17个是非平面的。

五立方体填充问题(pentacube puzzle)是由五立方体中12个高度为1的平面五立方体,填满三维的长方体。五立方体的体积是单位立方体的5倍,要填满的长方体体积就是单位立方体的60倍,可能的尺寸有2×3×10(12 个解)、2×5×6(264个解)及3×4×5(3940个解 solutions),以下就是这几种情形的各一个解[9] 

五立方体其实有29个,因此也可能会想是否可以用所有的五立方体(包括平面及非平面的)来填满长方体。不过29个五立方体的体积是单位立方体的29×5=145倍,可能的长方体尺寸只有29×5×1,而高度只有1,无法将非平面的五立方体放入,因此不可能用29个五立方体来填满长方体。

双人游戏

以十二块为基础,可作一个双人游戏。每人轮流在一个8×8的格网上放其中一块,使得每块不重叠而没有一块用多于一次。最后一个放的人胜。这个游戏是先手胜的[10]。这个游戏称为“格伦布游戏”[11]

1960年,桌上游戏设计师艾力克斯·兰多夫以此游戏增加限放规则的补天棋

建筑

 
以五格骨格为外墙装饰的Plattenbau建筑

有时,一些Plattenbau英语Plattenbau建筑的外墙会以以五格骨格为装饰,主要出现在东欧。图案主要是以6×10长方形问题的解为主。

脚注

  1. ^ 1.0 1.1 Eric Harshbarger - Pentominoes. [2006-01-18]. (原始内容存档于2020-02-03). 
  2. ^ Pentominoes. [2012-06-09]. (原始内容存档于2017-12-17). 
  3. ^ Rhoads, Glenn C. Planar Tilings and the Search for an Aperiodic Prototile. PhD dissertation, Rutgers University. 2003. 
  4. ^ Gardner, Martin. More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes. Scientific American. 1975-08, 233 (2): 112–115. 
  5. ^ people.rit.edu - Introduction - polyomino and pentomino. [2019-08-17]. (原始内容存档于2020-11-27). 
  6. ^ C. B. Haselgrove; Jenifer Haselgrove. A Computer Program for Pentominoes. Eureka英语Eureka (University of Cambridge magazine). October 1960, 23: 16–18. 
  7. ^ Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.
  8. ^ Donald E. Knuth. "Dancing links"页面存档备份,存于互联网档案馆) (Postscript, 1.6 megabytes). Includes a summary of Scott's and Fletcher's articles.
  9. ^ Barequet, Gill; Tal, Shahar. Solving General Lattice Puzzles. Lee, Der-Tsai; Chen, Danny Z.; Ying, Shi (编). Frontiers in Algorithmics. Springer Berlin Heidelberg. 2010: 124–135. doi:10.1007/978-3-642-14553-7_14. 
  10. ^ Hilarie K. Orman. Pentominoes: A First Player Win页面存档备份,存于互联网档案馆) (Pdf).
  11. ^ Pritchard (1982),第83页.

参考资料

  • Pritchard, D. B. Golomb's Game. Brain Games. Penguin Books. 1982: 83–85. ISBN 0-14-00-5682-3. 

相关条目

外部链接