五格骨牌

五格骨牌（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 Haselgrove）及Jenifer 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. 

相关条目

外部链接