多格骨牌
此条目目前正依照其他维基百科上的内容进行翻译。 (2020年2月15日) |
多格骨牌(Polyomino),又称多连块、多连方、多方块或多连方块,是由全等正方形连成的图形,包括四格骨牌、五格骨牌、六格骨牌等,n格骨牌的个数为(镜射或旋转视作同一种):
- 1, 1, 1, 2, 5, 12, 35, 108, 369, 1285, 4655, 17073, 63600, 238591, 901971, 3426576, 13079255, 50107909, 192622052, 742624232, 2870671950, ... (OEIS数列A000105)
除了n=0, 1, 2的显然易见的条件以外,只有n=5的时候才能用所有的n格骨牌填满一个长方形(见五格骨牌#长方形填充),n=3的情形显然无解,对n=4和n=6无解的证明需要使用肢解国际象棋盘问题的概念,而时,n格骨牌中有些骨牌的中间有空洞,因此也无解。
列表
多格骨牌有三种,以对称分类:
名称 | 两面(自由)[2] | 片面(单边)[3] | 有向(固定)[4] | |
---|---|---|---|---|
1 | 一格骨牌 | 1 | 1 | 1 |
2 | 二格骨牌 | 1 | 1 | 2 |
3 | 三格骨牌 | 2 | 2 | 6 |
4 | 四格骨牌 | 5 | 7 | 19 |
5 | 五格骨牌 | 12 | 18 | 63 |
6 | 六格骨牌 | 35 | 60 | 216 |
7 | 七格骨牌 | 108 | 196 | 760 |
8 | 八格骨牌 | 369 | 704 | 2725 |
9 | 九格骨牌 | 1285 | 2500 | 9910 |
10 | 十格骨牌 | 4655 | 9189 | 36446 |
11 | 十一格骨牌 | 17073 | 33896 | 135268 |
12 | 十二格骨牌 | 63600 | 126759 | 505861 |
13 | 十三格骨牌 | 238591 | 476270 | 1903890 |
14 | 十四格骨牌 | 901971 | 1802312 | 7204874 |
15 | 十五格骨牌 | 3426576 | 6849777 | 27394666 |
计算算法
渐近分析
若A(n)是自由n格骨牌的总数,则有猜想说明
其中 。但是这个是未解决的问题,缺乏证明。[7]
密铺
平面
任何少于或等于六格的骨牌都可以铺满整个平面,因为它们都满足康威准则,而在全部108种七格骨牌中,有101种满足康威准则,有104种可以铺满整个平面,另外4种(包括唯一一个中间有洞的那种)无法铺满整个平面,至于369种八格骨牌则有320种满足康威准则,有343种可以铺满整个平面;1285种九格骨牌中则有960种满足康威准则,有1050种可以铺满整个平面。
长方形
若需要至少n个多格骨牌P覆盖任何长方形(或矩形的格子),则n是P的次数(order)。若一个多格骨牌不可以覆盖(如Z形的四格骨牌),则其次数是未定义的。[11][1][12]
L形骨牌有次数2。[13]
未解决的数学问题:奇数次数的多格骨牌存在吗? |
可不可以使用5、7或9个骨牌密铺一个长方形这个问题仍未解答。有次数2的骨牌P,可以使用11个P覆盖一个更大的长方形。[15][1][12]
截至2020年,有两个未解决的问题:
- 奇数次数的多格骨牌存在吗?
- 若可以用n个骨牌密铺一个长方形,且n是奇数,最小的n为何?现在已知n最多为11。
未解决的数学问题:若可以用n个骨牌密铺一个长方形,且n是奇数,最小的n为何?现在已知n最多为11。 |
谜题和游戏
- 有些数独#变体用多格骨牌
- 角斗士棋
- 俄罗斯方块
最小面积
若可以用骨牌A覆盖每个n格骨牌,则A是共同超形式(common superform、CS)。若A是共同超形式中面积最小的那个,则A是最小共同超形式(minimal common superform、MCS)。比如,五格骨牌的MCS是下面两个九格骨牌。无论P是哪一个五格骨牌,P都可以放在这两个骨牌里。[1][12][18]
### ### ##### ##### # #
参见
参考文献
- ^ 1.0 1.1 1.2 1.3 Golomb, Golomb. Polyominoes. 1975.
- ^ (OEIS数列A000105)
- ^ (OEIS数列A000988)
- ^ (OEIS数列A001168)
- ^ Jensen, Iwan. Enumerations of Lattice Animals and Trees. Journal of Statistical Physics. 2001, 102 (3/4): 865–881. doi:10.1023/A:1004855020556.
- ^ Conway, A. Enumerating 2D percolation series by the finite-lattice method: theory. Journal of Physics A: Mathematical and General. 1995-01-21, 28 (2): 335–349. ISSN 0305-4470. doi:10.1088/0305-4470/28/2/011.
- ^ Jensen, Iwan; Guttmann, Anthony J. Statistics of lattice animals (polyominoes) and polygons. Journal of Physics A: Mathematical and General. 2000-07-28, 33 (29): L257–L263. ISSN 0305-4470. doi:10.1088/0305-4470/33/29/102.
- ^ Barequet Gill, Rote Günter; ShalahMira. λ > 4: an improved lower bound on the growth constant of polyominoes. Communications of the ACM. 2016-06-24 [2020-02-15]. doi:10.1145/2851485. (原始内容存档于2020-06-30) (英语). Authors list列表缺少
|last2=
(帮助) - ^ Klarner, D. A.; Rivest, R. L. A Procedure for Improving the Upper Bound for the Number of n -Ominoes. Canadian Journal of Mathematics. 1973-06, 25 (3): 585–602. ISSN 0008-414X. doi:10.4153/CJM-1973-060-4 (英语).
- ^ Golomb, Solomon W. Tiling with sets of polyominoes. Journal of Combinatorial Theory. 1970-07, 9 (1): 60–71 [2020-02-15]. doi:10.1016/S0021-9800(70)80055-2. (原始内容存档于2021-02-26) (英语).
- ^ Tiling Rectangles With Polyominoes. www.eklhad.net. [2020-02-15]. (原始内容存档于2020-02-15).
- ^ 12.0 12.1 12.2 12.3 12.4 Golomb, Solomon W. (Solomon Wolf). Polyominoes : puzzles, patterns, problems, and packings. 2nd ed. Princeton, N.J.: Princeton University Press https://www.worldcat.org/oclc/29358809. 1994. ISBN 0-691-08573-0. OCLC 29358809. 缺少或
|title=
为空 (帮助) - ^ Weisstein, Eric W. (编). L-Polyomino. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. [2020-02-15]. (原始内容存档于2015-07-26) (英语).
- ^ Stewart, I. N; Wormstein, A. Polyominoes of order 3 do not exist. Journal of Combinatorial Theory, Series A. 1992-09-01, 61 (1): 130–136 [2020-02-15]. ISSN 0097-3165. doi:10.1016/0097-3165(92)90058-3. (原始内容存档于2020-01-12) (英语).
- ^ Primes of the P hexomino. www.cflmath.com. [2020-02-15]. (原始内容存档于2016-03-22).
- ^ Tiling Rectangles and Half Strips with Congruent Polyominoes. www.cflmath.com. [2020-02-15]. (原始内容存档于2020-01-15).
- ^ co.combinatorics - Cutting a rectangle into an odd number of congruent pieces. MathOverflow. [2020-02-15]. (原始内容存档于2020-02-15).
- ^ Polyomino Common Superforms. puzzlezapper.com. [2020-02-15]. (原始内容存档于2017-05-21).
- ^ Whittington, S. G.; Soteros, C. E. (1990)., Whittington, S. G.; Soteros, C. E. (1990). "Lattice Animals: Rigorous Results and Wild Guesses"..
- ^ In Grimmett, G.; Welsh, D. (eds.)., In Grimmett, G.; Welsh, D. (eds.). Disorder in Physical Systems. Oxford University Press..