五格骨牌
五格骨牌（Pentomino），又稱五連塊、五連方、五連方塊或傷腦筋十二塊，是由五個全等正方形連成的多格骨牌，鏡射或旋轉視作同一種共有十二種，可以英文字母代表。五格骨牌的相關問題及遊戲是娛樂數學中流行的問題[1]。五格骨牌的謎題，最早是英國人亨利·杜德耐於1907年所發明，書名《坎特伯雷趣题和其他奇特问题》（Canterbury Puzzles and Other Curious Problems）[2]。
五格骨牌中每一個都滿足康威準則，因此用任何一個都可以密鋪整個平面[3]。甚至，所有五格骨牌都可以在不鏡射的條件下密鋪整個平面[4]。
五格骨牌只有十二種的證明
數字5有7種分拆：{5}、{4,1}、{3,2}、{3,1,1}、{2,2,1}、{2,1,1,1}、{1,1,1,1,1}。
- {5}：
- 第一列有五格：
- I骨牌/O骨牌（1）
- 第一列有五格：
- {4,1}：
- 第一列有四格，第二列有一格：
- 第二列的那格位於第一列的第一格下方：
- L骨牌/Q骨牌（2）
- 第二列的那格位於第一列的第二格下方：
- Y骨牌（3）
- 第二列的那格位於第一列的第三格下方：（同「第二列的那格位於第一列的第二格下方」）
- 第二列的那格位於第一列的第四格下方：（同「第二列的那格位於第一列的第一格下方」）
- 第二列的那格位於第一列的第一格下方：
- 第一列有四格，第二列有一格：（同「第一列有四格，第二列有一格」）
- 第一列有四格，第二列有一格：
- {3,2}：
- 第一列有三格，第二列有兩格：
- 第二列的那兩格位於第一列的第一格下方及其左方一格：
- N骨牌/S骨牌（4）
- 第二列的那兩格位於第一列的第一、二格下方：
- P骨牌（5）
- 第二列的那兩格位於第一列的第一、三格下方：
- U骨牌（6）
- 第二列的那兩格位於第一列的第二、三格下方：（同「第二列的那兩格位於第一列的第一、二格下方」）
- 第二列的那兩格位於第一列的第三格下方及其右方一格：(同「第二列的那兩格位於第一列的第一格下方及其左方一格」）
- 第二列的那兩格位於第一列的第一格下方及其左方一格：
- 第一列有兩格，第二列有三格：（同「第一列有三格，第二列有兩格」）
- 第一列有三格，第二列有兩格：
- {3,1,1}：
- 第一列有三格，第二列有一格，第三列有一格：
- 第二、三列的那兩格位於第一列的第一格下方：
- V骨牌（7）
- 第二、三列的那兩格位於第一列的第二格下方：
- T骨牌（8）
- 第二、三列的那兩格位於第一列的第三格下方：（同「第二、三列的那兩格位於第一列的第一格下方」）
- 第二、三列的那兩格位於第一列的第一格下方：
- 第一列有一格，第二列有三格，第三列有一格：
- 第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第一格下方：（同「T骨牌」）
- 第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第二格下方：
- F骨牌/R骨牌（9）
- 第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第三格下方：
- Z骨牌（10）
- 第一列的那格位於第二列的第二格上方，第三列的那格位於第二列的第一格下方：（同「第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第二格下方」）
- 第一列的那格位於第二列的第二格上方，第三列的那格位於第二列的第二格下方：
- X骨牌（11）
- 第一列的那格位於第二列的第二格上方，第三列的那格位於第二列的第三格下方：（同「第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第二格下方」）
- 第一列的那格位於第二列的第三格上方，第三列的那格位於第二列的第一格下方：（同「第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第三格下方」）
- 第一列的那格位於第二列的第三格上方，第三列的那格位於第二列的第二格下方：（同「第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第二格下方」）
- 第一列的那格位於第二列的第三格上方，第三列的那格位於第二列的第三格下方：（同「第一列的那格位於第二列的第一格上方，第三列的那格位於第二列的第一格下方」）
- 第一列有三格，第二列有一格，第三列有一格：
- {2,2,1}：
- 第一列有兩格，第二列有兩格，第三列有一格：
- 第二列的那兩格位於第一列的第一格下方及其左方一格，第三列的那格位於第二列的第一格下方：
- W骨牌（12）
- 第二列的那兩格位於第一列的第一格下方及其左方一格，第三列的那格位於第二列的第二格下方：（同「F骨牌/R骨牌」）
- 第二列的那兩格位於第一列的第一、二格下方，第三列的那格位於第二列的第一格下方：（同「P骨牌」）
- 第二列的那兩格位於第一列的第一、二格下方，第三列的那格位於第二列的第二格下方：（同「第二列的那兩格位於第一列的第一、二格下方，第三列的那格位於第二列的第一格下方」）
- 第二列的那兩格位於第一列的第二格下方及其右方一格，第三列的那格位於第二列的第一格下方：（同「第二列的那兩格位於第一列的第一格下方及其左方一格，第三列的那格位於第二列的第二格下方」）
- 第二列的那兩格位於第一列的第二格下方及其右方一格，第三列的那格位於第二列的第二格下方：（同「第二列的那兩格位於第一列的第一格下方及其左方一格，第三列的那格位於第二列的第一格下方」）
- 第二列的那兩格位於第一列的第一格下方及其左方一格，第三列的那格位於第二列的第一格下方：
- 第一列有兩格，第二列有一格，第三列有兩格：
- 第二列的那格位於第一列的第一格下方，第三列的那兩格位於第二列的那格下方及其左方一格：（同「Z骨牌」）
- 第二列的那格位於第一列的第一格下方，第三列的那兩格位於第二列的那格下方及其右方一格：（同「U骨牌」）
- 第二列的那格位於第一列的第二格下方，第三列的那兩格位於第二列的那格下方及其左方一格：（同「第二列的那格位於第一列的第一格下方，第三列的那兩格位於第二列的那格下方及其右方一格」）
- 第二列的那格位於第一列的第二格下方，第三列的那兩格位於第二列的那格下方及其右方一格：（同「第二列的那格位於第一列的第一格下方，第三列的那兩格位於第二列的那格下方及其左方一格」）
- 第一列有一格，第二列有兩格，第三列有兩格：（同「第一列有兩格，第二列有兩格，第三列有一格」）
- 第一列有兩格，第二列有兩格，第三列有一格：
- {2,1,1,1}：（因骨牌高度為4，寬度最多是2+(1−1)+(1−1)+(1−1)=2，寬度少於高度，故得到的骨牌必定跟前面某個骨牌相同，而不會得到新的骨牌）
- {1,1,1,1,1}：（因骨牌高度為5，寬度最多是1+(1−1)+(1−1)+(1−1)+(1−1)=1，寬度少於高度，故得到的骨牌必定跟前面某個骨牌相同，而不會得到新的骨牌）
歷史
五格骨牌的正式定義是由美國教授所羅門·格倫布在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個英文字母（為字母表的最後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 個固定的五格骨牌。
以下是F, L, N, P, Y 骨牌的八種可能放法：
長方形填充
標準的五格骨牌謎題是用五格骨牌密鋪長方形，骨牌不能重疊，也不能留下沒有骨牌的空格。每個五格骨牌的面積都等於五個單位方形，因此長方形的面積需等於60個單位方形。可能的尺寸有6×10, 5×12, 4×15 及3×20。狂熱智力游戏玩家可能會徒手玩幾個小時來求解這類問題。另一個問題的挑戰性更大，是計算某一尺寸下有幾種解法，一般會需要配合搜索算法來進行。
6×10的問題最早是由柯林·布萊恩及珍妮佛·哈塞爾格羅夫[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個空格在其他的位置，大部份的變體都可以解（如果4個空格的位置讓剩下的區域變得不連通就無解，另外根據肢解西洋棋盤問題，把這個8×8正方形依照西洋棋盤的方式來著色時，如果4個空格都在同色格就不能解），除非空格都集中在某兩個角附近，讓兩個角都要用P骨牌填充，或是強迫在角落放入T骨牌或U骨牌，使得出現其他五格骨牌無法填滿的格子。
目前已有高效的演算法可求解五格骨牌的密鋪問題，像高德纳也有創建類似的演算法[8]。若在現今的个人电脑上執行，只要幾秒鐘就能解出五格骨牌的擺放方式。
如果是要只使用同一種五格骨牌來拼成長方形，則只有I,L,P三種骨牌可以做到，而I骨牌的次數是1，L骨牌跟P骨牌的次數則是2。
用到全部12種五格骨牌的長方形：
| 長方形 | 解法數目（旋轉與鏡射視為同一種解法） |
| 3×20 | 2 |
| 4×15 | 368 |
| 4×16（中間挖掉2×2） | 47 |
| 5×12 | 1010 |
| 6×10 | 2339 |
| 8×8（中間挖掉2×2） | 65 |
| 8×8（挖掉四個角） | 2170 |
不用用到全部12種五格骨牌的長方形：
| 長方形 | 解法數目（旋轉與鏡射視為同一種解法） |
| 3×5 | 7 |
| 3×10 | 145 |
| 3×15 | 201 |
| 4×5 | 50 |
| 4×10 | 2085 |
| 5×5 | 107 |
| 5×6 | 541 |
| 5×7 | 1396 |
| 5×8 | 3408 |
| 5×9 | 5902 |
| 5×10 | 6951 |
| 5×11 | 4103 |
所有12種五格骨牌都滿足康威準則，因此都可以只用同一種五格方塊，來填滿整個平面。
每一種五格骨牌都可以把長寬都放大三倍，變成一個45格單位的圖形，而且都可以用12種五格骨牌中的9種來拼出來。
| 放大三倍的五格骨牌 | 解法數目 |
| I | 201 |
| L | 113 |
| Y | 86 |
| N | 68 |
| P | 497 |
| U | 48 |
| V | 63 |
| T | 106 |
| F | 125 |
| Z | 131 |
| X | 15 |
| W | 91 |
利用所有的n格骨牌來密鋪長方形的問題，只有在n = 0, 1, 2和5時才有解，所以除去n = 0, 1, 2的顯然情況（只有一個n格骨牌）外，n = 5拼出的那些60格的長方形是獨一無二的。
雖然全部五種四格骨牌並不能拼成長方形，但是可以用一種五格骨牌跟全部五種四格骨牌拼成一個5×5的正方形，所有的五格骨牌當中，除了I, T, V, X以外都可以做到。
最小區域問題
找出一個最小的區域，使得每一種五格骨牌都能個別放入，滿足這個條件的區域最少有九格，證明如下：
要放入I骨牌，就需要一條長五格的直線，再考慮X骨牌，它跟I骨牌有三格會重疊（不然就需要九格，或者最長的直線就必須要有六格，然而這樣一來就會有八格了，而要再放入P骨牌就需要第九格），此時，無論格子怎麼排，要再放入V骨牌就需要第八格，而還要再放入P骨牌又需要第九格，因此八格是不夠的。
平面填充
所有的五格方塊都滿足康威準則，因此都可以只使用同一種五格骨牌，來鋪滿整個平面，即使不允許翻面也一樣都可以。
五立方體及立體填充
五立方體（pentacube）是由五個立方體組成的多連立方體，共有29個，其中有12個是高度為1的五格骨牌，另外17個是非平面的。（如果允許鏡射（在四維空間中翻面），則有23個）
五立方體填充問題（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個五立方體來填滿長方體。或者你也可以跟「五格骨牌有12個」一樣，把鏡射的算作同一個，此時會有23個五立方體，總體積為單位立方體的115倍，可能的長方體尺寸只有23×5×1，因此也不可能用23個五立方體來填滿長方體。
康威生命遊戲
若以這十二種五格骨牌分別作為康威生命遊戲的起始狀態，則結局分別為：
I骨牌：6步後變為「紅綠燈」（振盪狀態）
L骨牌：9步後變為「紅綠燈」（振盪狀態）
Y骨牌：3步後即消失殆盡
N骨牌：5步後即消失殆盡
P骨牌：4步後即消失殆盡
U骨牌：4步後即消失殆盡
V骨牌：3步後變為「麵包」（穩定狀態）
T骨牌：10步後變為「紅綠燈」（振盪狀態）
F骨牌：1103步後變為8個「板凳」（穩定狀態），4個「蜂巢」（穩定狀態），1個「麵包」（穩定狀態），1個「小船」（穩定狀態），1個「大船」（穩定狀態），4個「信號燈」（振盪狀態），6個「滑翔機」（會移動的振盪狀態）
Z骨牌：3步後即消失殆盡
X骨牌：6步後變為「紅綠燈」（振盪狀態）
W骨牌：2步後變為「麵包」（穩定狀態）
 紅綠燈 |
 麵包 |
 板凳 |
 蜂巢 |
 小船 |
 大船 |
 信號燈 |
 滑翔機 |
經典智力題
16根火柴棒排成N骨牌的所有五個正方形的所有邊，要如何只移動兩根火柴棒，使正方形的數量從五變成四？注意：不能有「游離端」，也就是火柴棒沒構成正方形的邊。
雙人遊戲
以十二塊五格骨牌為基礎，可作一個雙人遊戲。每人輪流在一個8×8的格網上放其中一塊，使得每塊不重疊而沒有一塊用多於一次。最後一個放的人勝。這個遊戲是先手勝的[10]。這個遊戲稱為「格倫布遊戲」[11]。
1960年，桌上遊戲設計師艾力克斯·蘭多夫以此遊戲增加限放規則的補天棋。
建築
有時，一些帕拉滕堡建築的外牆會以五格骨牌為裝飾，主要出現在東歐。圖案主要是以6×10長方形問題的解為主。
腳註
- ^ 1.0 1.1 Eric Harshbarger - Pentominoes
- ^ Pentominoes
- ^ 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
- ^ 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纸牌的解决方案。
| ||||||||||||
