五格骨牌
五格骨牌(Pentomino),又称五连块、五连方、五连方块或伤脑筋十二块,是由五个全等正方形连成的多格骨牌,反射或旋转视作同一种共有十二种,可以英文字母代表。五格骨牌的相关问题及游戏是娱乐数学中流行的问题[1]。五格骨牌的谜题,最早是英国人亨利·杜德耐于1907年所发明,书名《坎特伯雷趣题和其他奇特问题》(Canterbury Puzzles and Other Curious Problems)[2]。
五格骨牌中每一个都满足康威准则,因此用任何一个都可以密铺整个平面[3]。所有具有对掌性的五格骨牌都可以在不镜射的条件下密铺整个平面[4]。
历史
五格骨牌的正式定义是由美国教授所罗门·格伦布在1953年开始定义,后来列在1965年出版的书籍《Polyominoes: Puzzles, Patterns, Problems, and Packings》[1][5]中。之后马丁·加德纳在《科学美国人》杂志1965年10月的数学游戏专栏中介绍,引起大家的兴趣。格伦布创建了五格骨牌的英文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的骨牌有一个对称点,是二次的旋转对称,因此也只有4种固定五格骨牌,旋转后可以产生二种骨牌,镜射后再旋转可以产生另外二种骨牌。其空间对称群有二个元素,除了恒等函数外,也包括180度的旋转。
- I的骨牌有两条对称轴(都平行格线)跟一个对称点,因此只有2种固定五格骨牌。其空间对称群有四个元素:恒等函数,两个镜射以及180度的旋转。I的骨牌是 n = 2 的二面体群,也称为克莱因四元群。
- X的骨牌有四条对称轴跟一个对称点,因此只有唯一一种固定五格骨牌。其四条对称轴分别平行格线以及二条对角线,也有四次的旋转对称。其对称轴是n = 4 的二面体群,有八个元素。
F, L, N, P, Y和Z的骨牌有对掌性,因此若考虑无法翻面的单面骨牌,要加上这些骨牌的镜射(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及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建筑的外墙会以以五格骨格为装饰,主要出现在东欧。图案主要是以6×10长方形问题的解为主。
脚注
- ^ 1.0 1.1 Eric Harshbarger - Pentominoes. [2006-01-18]. (原始内容存档于2020-02-03).
- ^ Pentominoes. [2012-06-09]. (原始内容存档于2017-12-17).
- ^ Rhoads, Glenn C. Planar Tilings and the Search for an Aperiodic Prototile. PhD dissertation, Rutgers University. 2003.
- ^ Gardner, Martin. More about tiling the plane: the possibilities of polyominoes, polyiamonds and polyhexes. Scientific American. 1975-08, 233 (2): 112–115.
- ^ people.rit.edu - Introduction - polyomino and pentomino. [2019-08-17]. (原始内容存档于2020-11-27).
- ^ C. B. Haselgrove; Jenifer Haselgrove. A Computer Program for Pentominoes. Eureka. October 1960, 23: 16–18.
- ^ Dana S. Scott (1958). "Programming a combinatorial puzzle". Technical Report No. 1, Department of Electrical Engineering, Princeton University.
- ^ Donald E. Knuth. "Dancing links" (页面存档备份,存于互联网档案馆) (Postscript, 1.6 megabytes). Includes a summary of Scott's and Fletcher's articles.
- ^ 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.
- ^ Hilarie K. Orman. Pentominoes: A First Player Win (页面存档备份,存于互联网档案馆) (Pdf).
- ^ Pritchard (1982),第83页.
参考资料
- Pritchard, D. B. Golomb's Game. Brain Games. Penguin Books. 1982: 83–85. ISBN 0-14-00-5682-3.
相关条目
- 龙博士
- 平铺拼图问题
- 都会棋
- 所罗门·格伦布
外部链接
- Pentomino, Homepage:有各种矩形的全部解
- George Huttlin's Pentomino Webpage:以十二块砌成英文字母
- Eric Harshbarger's Pentominoes Page (页面存档备份,存于互联网档案馆)
- Pentomino
- 拼图笔记,高文山
- 这里可以下载双人游戏(Pentacubes)
- 启发积木线上游戏。拖动,旋转和翻转积木瓷砖放在一起的图片或解决数字拼图,玩Tetromino或发现PEG纸牌的解决方案。