多格骨牌(Polyomino),又稱多連塊、多連方、多方塊或多連方塊,是由全等正方形連成的圖形,包括四格骨牌、五格骨牌、六格骨牌等,n格骨牌的個數為(鏡射或旋轉視作同一種):
:1, 1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655, 17073, 63600, 238591, 901971, 3426576, 13079255, 50107909, 192622052, 742624232, 2870671950, ...
除了n=0, 1, 2的顯然易見的條件以外,只有n=5的時候才能用所有的n格骨牌填滿一個長方形(見五格骨牌#長方形填充),n=3的情形顯然無解,對n=4和n=6無解的證明需要使用肢解西洋棋盤問題的概念,而n\geq 7時,n格骨牌中有些骨牌的中間有空洞,因此也無解。
形成一個8×8平方,刪除中間的2x2平方]](两面),不考慮對稱相同則有60個片面骨牌。 不同顏色代表不同对称性类型。]]
]]
列表
(n = 4)]]
(n = 5)。每個骨牌使用一个拉丁字母的字母。]]多格骨牌有三种,以对称分类:
自由(两面)骨牌(刚体):平移、转动、反射、;可以包括洞以及單連通(无洞)的骨牌
一片面:平移、转动(不可反射)
固定(有向):平移(不可转动、不可反射)
计算算法
- 母函数
- 传递矩阵法,这使用统计力学的渗流理论(阅读文章,扩充内容)
渐近分析
若A(n)是自由n格骨牌的总数,則有猜想說明
A_n \sim c\lambda^n / n
其中c \approx 0.3169, \ \lambda \approx 4.0626。但是这个是未解决的问题,缺乏证明。
但是有证明表示A為指數增長(4.00253 )
\lim_{n \to \infty} (A_n)^{1/n} = \lambda
密铺
- 双体模型,使用二格骨牌密铺格子
*康威準則
*娛樂數學
*王氏砖
這些問題有些是NP完全的,或與递归集合有關。
平面
任何少於或等於六格的骨牌都可以鋪滿整個平面,因為它們都滿足康威準則,而在全部108種七格骨牌中,有101種滿足康威準則,有104種可以鋪滿整個平面,另外4種(包括唯一一個中間有洞的那種)無法鋪滿整個平面,至於369種八格骨牌則有320種滿足康威準則,有343種可以鋪滿整個平面;1285種九格骨牌中則有960種滿足康威準則,有1050種可以鋪滿整個平面。
长方形
若需要至少n個多格骨牌P覆盖任何长方形(或矩形的格子),则n是P的次数(order)。若一個多格骨牌不可以覆盖(如Z形的四格骨牌),則其次数是未定义的。
L形骨牌有次数2。
次数4n的骨牌存在(n是整数)。
截至2020年,有两个未解决的问题:
- 奇数次数的多格骨牌存在嗎?
- 若可以用n個骨牌密铺一个长方形,且n是奇数,最小的n為何?现在已知n最多為11。
謎題和遊戲
- 有些數獨#變體用多格骨牌
- 角鬥士棋
- 俄羅斯方塊
最小面积
若可以用骨牌A覆盖每個n格骨牌,则A是共同超形式(common superform、CS)。若A是共同超形式中面积最小的那個,则A是最小共同超形式(minimal common superform、MCS)。比如,五格骨牌的MCS是下面两個九格骨牌。无论P是哪一個五格骨牌,P都可以放在这两個骨牌裡。
### ###
#####
# #
參見
*多連立方體
*渗流理论
*杨表
*角鬥士棋
*多格形
參考文獻
评论 (0)