王氏磚

王氏磚（英語：Wang tile）也稱為王氏多米諾骨牌，最早由美籍華裔數學家、邏輯學家和哲學家王浩於1961年提出，屬於邊緣匹配拼圖（英語：Edge-matching puzzle），也是形式系統。

王氏磚的外觀是正方形，正方形的每一邊可以有不同的顏色，也可以以各邊和中心點組成的三角形來著色，一個王氏磚中裡可以有二個至四個不同的顏色。二個王氏磚拼合時，其相鄰的邊需要有相同的顏色，在王氏磚拼合時，不允許旋轉王氏磚，王氏磚也不能翻面。

關於特定一組王氏磚的基本問題是：是否可以用這組王氏磚密鋪平面？也就是以符合王氏磚規則的方式填合無限大的平面。下一個問題是是否存在周期性的密鋪方式？

多米諾骨牌問題

王浩於1961年提出猜想，如果一組有限多個的王氏磚可以在鄰邊相互匹配的條件下，密鋪整個平面，那麼也存在針對這組王氏磚的周期性密鋪鋪法，也就是說這種鋪法在二維點陣中的矢量平移轉換下不變，就如壁紙圖案一般。他還觀察到，若這個猜想成立意味着有一種算法，可以用來判斷任何一組有限多個的王氏磚是否可以密鋪整個平面^[1] ^[2]。將瓷磚按照相鄰邊相互匹配的想法見於多米諾骨牌遊戲中，所以王氏磚也被稱為王氏多米諾骨牌。 ^[3]判斷一組骨牌是否可以平鋪整個平面的算法問題被稱為多米諾骨牌問題^[4] 。

根據王浩的學生，羅伯特·伯傑（英語：Robert Berger (mathematician)）所言^[5]

多米諾骨牌問題指的是，如何判斷任何一組多米諾骨牌是否可解？對於任意規格的一組多米諾骨牌，若存在一種算法來幫助判定它是否可解，則我們講多米諾骨牌問題是「可判定」的。否則是「無法判定」的。

換句話說，多米諾骨牌問題問的是，是否存在一個有效方法（英語：Effective method），對任何多米諾骨牌集，都能正確地解決問題？

1966年，伯傑解決了王氏磚的多米諾骨牌問題，他證明了不存在能夠解決該問題的算法。其解法如下：可以將任何圖靈機轉變成一組密鋪整個平面的王氏平鋪，當且僅當此圖靈機永不停止。而停機問題（測試圖靈機是否最終停止的問題）的不可判斷性導致了王氏平鋪問題的不可判定性^[5]。

非周期性的瓷磚組

結合王浩的觀察以及伯傑的不可判斷性結果，可以推測存在一組有限多個的王氏磚，可以密鋪整個二維平面，但只能非周期性密鋪。此密鋪類似彭羅斯平鋪（英語：Penrose tiling），或准晶體中原子的排列。

伯傑在論文中有提到一種非周期性密鋪集合，是由20,426塊王氏磚組合，但他猜測也可能存在只能非周期性密鋪的較小集合。伯傑發表的博士學位論文中有提到數量較少（104個）的王氏磚。在後來的幾年中，又發現了越來越少的王氏磚組^[6] ^[7] ^[8] ^[9]。例如，上圖中給出的13個圖塊是由Karel Culik II於1996年出版的非周期集。^[7]它可以密鋪二維平面，但不能周期性密鋪。2015年Emmanuel Jeandel和Michael Rao發現了使用4種顏色的11塊非周期性密鋪集合，並使用暴力搜索來確定，若減到10塊王氏磚或是只有3種顏色，都不足以強制非周期性^[9]。

擴展

王氏磚可以擴展為其他的形式，而許多相關的問題也是不可判定的。例如，王氏立方體（Wang cubes）是具有彩色面的正立方體，相對的面拼合時需要有相同的顏色。Culik和Kari展示了非周期性的王氏立方體^[10]。 Winfree等已經證明了用DNA製成的分子「磚」的可行性，它與王氏磚有相似之處^[11]。米塔爾等人已經證明，這些王氏「磚」可以由肽核酸（PNA）組成，肽核酸是穩定的DNA人工模擬物^[12]。

應用

王氏磚已用來做為程序化生成的產生工具，可以用來產生紋理、地形和其他大型和非重複的二維數據集。可以用較便宜的成本，預先計算或手工製作一小組的「源磚」，確認其它們拼貼出的結果不會有太明顯的重複，且沒有周期性。在這種情況下，傳統的非周期性方格排列顯示其非常規則的結構。王氏磚程序化生成的限制較少，而且確保可以密鋪，並且可以用偽隨機的方式選擇每塊磚 ^[13] ^[14] ^[15] ^[16]。

王氏磚也用於細胞自動機理論中決定性問題的證明^[17]。

流行文化

澳洲作家格雷格·伊根有一個短篇故事《王氏地毯》，後來擴展為小說《海外僑民（英語：Diaspora (novel)）》（Diaspora），描寫了有有居民生物和智慧生物的假想宇宙，這些生物都是由複雜分子模式實現的王氏磚^[18]。

參見

邊緣匹配拼圖（英語：Edge-matching puzzle）
永恆II拼圖（英語：Eternity II puzzle）
珀西·亞歷山大麥克·馬洪（英語：Percy Alexander MacMahon）
TetraVex

參考文獻

[1]
Wang, Hao, Proving theorems by pattern recognition—II, Bell System Technical Journal, 1961, 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x
[2]
Wang, Hao, Games, logic and computers, Scientific American, November 1965: 98–106. Presents the domino problem for a popular audience.
[3]
Renz, Peter, Mathematical proof: What it is and what it ought to be, The Two-Year College Mathematics Journal, 1981, 12 (2): 83–103, doi:10.2307/3027370.
[4]
Berger, Robert, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 1966, 66: 72, MR 0216954. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
[5]
Berger, Robert, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 1966, 66: 72, MR 0216954. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.
[6]
Robinson, Raphael M., Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 1971, 12: 177–209, Bibcode:1971InMat..12..177R, MR 0297572, doi:10.1007/bf01418780.
[7]
Culik, Karel, II, An aperiodic set of 13 Wang tiles, Discrete Mathematics, 1996, 160 (1-3): 245–251, MR 1417576, doi:10.1016/S0012-365X(96)00118-5（包括5個顏色的13個王氏磚）
[8]
Kari, Jarkko, A small aperiodic set of Wang tiles, Discrete Mathematics, 1996, 160 (1-3): 259–264, MR 1417578, doi:10.1016/0012-365X(95)00120-L.
[9]
Jeandel, Emmanuel; Rao, Michael, An aperiodic set of 11 Wang tiles, Computing Research Repository, 2015, Bibcode:2015arXiv150606492J, arXiv:1506.06492 （包括4個顏色的11個王氏磚）}
[10]
Culik, Karel, II; Kari, Jarkko, An aperiodic set of Wang cubes, Journal of Universal Computer Science, 1995, 1 (10): 675–686 [2019-08-13], MR 1392428, doi:10.1007/978-3-642-80350-5_57, （原始內容存檔於2019-08-13）.
[11]
Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C., Design and self-assembly of two-dimensional DNA crystals, Nature, 1998, 394: 539–544, Bibcode:1998Natur.394..539W, PMID 9707114, doi:10.1038/28998
[12]
Lukeman, P.; Seeman, N.; Mittal, A., Hybrid PNA/DNA nanosystems, 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii, 2002.
[13]
Stam, Jos, Aperiodic Texture Mapping (PDF), 1997 [2019-08-13], （原始內容 (PDF)存檔於2016-04-30）. Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
[14]
Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver, Wang tiles for image and texture generation, ACM SIGGRAPH 2003 (PDF), New York, NY, USA: ACM: 287–294, 2003 [2019-08-13], ISBN 1-58113-709-5, doi:10.1145/1201775.882265, 原始內容存檔於2006-03-18. Introduces stochastic tiling.
[15]
Wei, Li-Yi, Tile-based texture mapping on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM: 55–63, 2004 [2019-08-13], ISBN 3-905673-15-0, doi:10.1145/1058129.1058138, （原始內容存檔於2016-05-07）. Applies Wang Tiles for real-time texturing on a GPU.
[16]
. Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani, Recursive Wang tiles for real-time blue noise, ACM SIGGRAPH 2006, New York, NY, USA: ACM: 509–518, 2006 [2019-08-13], ISBN 1-59593-364-6, doi:10.1145/1179352.1141916, （原始內容存檔於2019-08-18）. Shows advanced applications.
[17]
Kari, Jarkko, Reversibility of 2D cellular automata is undecidable, Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena 45 (1-3): 379–385, 1990, Bibcode:1990PhyD...45..379K, MR 1094882, doi:10.1016/0167-2789(90)90195-U.
[18]
Burnham, Karen, Greg Egan, Modern Masters of Science Fiction, University of Illinois Press: 72–73, 2014, ISBN 9780252096297

外部連結

Steven Dutch的頁面，包括許多非周期性瓷磚的圖片
一個簡單的王氏平鋪方法的動畫演示（頁面存檔備份，存於網際網路檔案館） - 需要Javascript和HTML5

延伸閱讀

Grünbaum, Branko; Shephard, G. C., Tilings and Patterns, New York: W. H. Freeman, 1987, ISBN 0-7167-1193-1

[1] [1]
Wang, Hao, Proving theorems by pattern recognition—II, Bell System Technical Journal, 1961, 40 (1): 1–41, doi:10.1002/j.1538-7305.1961.tb03975.x

[2] [2]
Wang, Hao, Games, logic and computers, Scientific American, November 1965: 98–106. Presents the domino problem for a popular audience.

[3] [3]
Renz, Peter, Mathematical proof: What it is and what it ought to be, The Two-Year College Mathematics Journal, 1981, 12 (2): 83–103, doi:10.2307/3027370.

[berger_2-4] [4]
Berger, Robert, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 1966, 66: 72, MR 0216954. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.

[berger-5] [5]
Berger, Robert, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 1966, 66: 72, MR 0216954. Berger coins the term "Wang tiles", and demonstrates the first aperiodic set of them.

[6] [6]
Robinson, Raphael M., Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 1971, 12: 177–209, Bibcode:1971InMat..12..177R, MR 0297572, doi:10.1007/bf01418780.

[culik-7] [7]
Culik, Karel, II, An aperiodic set of 13 Wang tiles, Discrete Mathematics, 1996, 160 (1-3): 245–251, MR 1417576, doi:10.1016/S0012-365X(96)00118-5（包括5個顏色的13個王氏磚）

[8] [8]
Kari, Jarkko, A small aperiodic set of Wang tiles, Discrete Mathematics, 1996, 160 (1-3): 259–264, MR 1417578, doi:10.1016/0012-365X(95)00120-L.

[jeandel-9] [9]
Jeandel, Emmanuel; Rao, Michael, An aperiodic set of 11 Wang tiles, Computing Research Repository, 2015, Bibcode:2015arXiv150606492J, arXiv:1506.06492 （包括4個顏色的11個王氏磚）}

[10] [10]
Culik, Karel, II; Kari, Jarkko, An aperiodic set of Wang cubes, Journal of Universal Computer Science, 1995, 1 (10): 675–686 [2019-08-13], MR 1392428, doi:10.1007/978-3-642-80350-5_57, （原始內容存檔於2019-08-13）.

[11] [11]
Winfree, E.; Liu, F.; Wenzler, L.A.; Seeman, N.C., Design and self-assembly of two-dimensional DNA crystals, Nature, 1998, 394: 539–544, Bibcode:1998Natur.394..539W, PMID 9707114, doi:10.1038/28998

[12] [12]
Lukeman, P.; Seeman, N.; Mittal, A., Hybrid PNA/DNA nanosystems, 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii, 2002.

[13] [13]
Stam, Jos, Aperiodic Texture Mapping (PDF), 1997 [2019-08-13], （原始內容 (PDF)存檔於2016-04-30）. Introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.

[14] [14]
Cohen, Michael F.; Shade, Jonathan; Hiller, Stefan; Deussen, Oliver, Wang tiles for image and texture generation, ACM SIGGRAPH 2003 (PDF), New York, NY, USA: ACM: 287–294, 2003 [2019-08-13], ISBN 1-58113-709-5, doi:10.1145/1201775.882265, 原始內容存檔於2006-03-18. Introduces stochastic tiling.

[15] [15]
Wei, Li-Yi, Tile-based texture mapping on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on Graphics Hardware (HWWS '04), New York, NY, USA: ACM: 55–63, 2004 [2019-08-13], ISBN 3-905673-15-0, doi:10.1145/1058129.1058138, （原始內容存檔於2016-05-07）. Applies Wang Tiles for real-time texturing on a GPU.

[16] [16]
. Kopf, Johannes; Cohen-Or, Daniel; Deussen, Oliver; Lischinski, Dani, Recursive Wang tiles for real-time blue noise, ACM SIGGRAPH 2006, New York, NY, USA: ACM: 509–518, 2006 [2019-08-13], ISBN 1-59593-364-6, doi:10.1145/1179352.1141916, （原始內容存檔於2019-08-18）. Shows advanced applications.

[17] [17]
Kari, Jarkko, Reversibility of 2D cellular automata is undecidable, Cellular automata: theory and experiment (Los Alamos, NM, 1989), Physica D: Nonlinear Phenomena 45 (1-3): 379–385, 1990, Bibcode:1990PhyD...45..379K, MR 1094882, doi:10.1016/0167-2789(90)90195-U.

[18] [18]
Burnham, Karen, Greg Egan, Modern Masters of Science Fiction, University of Illinois Press: 72–73, 2014, ISBN 9780252096297

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]