Wang Tiles: Difference between revisions
Jump to navigation
Jump to search
→Busy Beaver function: Fixed first champion |
|||
| (10 intermediate revisions by 5 users not shown) | |||
| Line 1: | Line 1: | ||
{{Stub}} | |||
'''Wang Tiles''' (or Wang dominoes) are a class of formal mathematical systems first proposed by Hao Wang in 1961. They consist of equal-sized square tiles with colored edges that are arranged side-by-side on a regular grid. | '''Wang Tiles''' (or Wang dominoes) are a class of formal mathematical systems first proposed by Hao Wang in 1961. They consist of equal-sized square tiles with colored edges that are arranged side-by-side on a regular grid. | ||
| Line 10: | Line 11: | ||
Define the ''score'' of a set of Wang tiles as the largest d such that it can tile a dxd square, or 0 if there is no largest d. | Define the ''score'' of a set of Wang tiles as the largest d such that it can tile a dxd square, or 0 if there is no largest d. | ||
Then | Then BB<sub>WT</sub>(n) = the maximum score over all n-tile sets. | ||
The current format to describe a set of tiles is a list of tuples that have 4 nonegative numbers, each representing a side color. Example: <code>[TOP,RIGHT,BOTTOM,LEFT]</code> | The current format to describe a set of tiles is a list of tuples that have 4 nonegative numbers, each representing a side color. Example: <code>[TOP,RIGHT,BOTTOM,LEFT]</code> | ||
| Line 18: | Line 19: | ||
!Value | !Value | ||
!Champion | !Champion | ||
!Image | |||
|- | |- | ||
|1 | |1 | ||
|1 | |1 | ||
|<code>[1,0,0,0]</code> | |<code>[1,0,0,0]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 1.png|alt=The definite champion for the largest valid square patch (1 by 1) made by a set of 1 Wang tile.|border|center|frameless]] | |||
|- | |- | ||
|2 | |2 | ||
|2 | |2 | ||
|<code>[1,0,2,0] [2,0,3,0]</code> | |<code>[1,0,2,0] [2,0,3,0]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 2.png|alt=The definite champion for the largest valid square patch (2 by 2) made by a set of 2 Wang tiles.|border|center|frameless]] | |||
|- | |- | ||
|3 | |3 | ||
|3 | |3 | ||
|<code>[1,0,2,0] [2,0,3,0] [3,0,4,0]</code> | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 3.png|alt=The definite champion for the largest valid square patch (3 by 3) made by a set of 3 Wang tiles.|border|center|frameless]] | |||
|- | |- | ||
|4 | |4 | ||
|4 | |4 | ||
|<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0]</code> | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 4.png|alt=The definite champion for the largest valid square patch (4 by 4) made by a set of 4 Wang tiles.|border|center|frameless]] | |||
|- | |- | ||
|5 | |5 | ||
|≥ | |6<ref name="YeyitoWTRocq">Yeyito, "[https://github.com/Yeyito777/bbchallenge-discoveries/blob/main/wang-tiles/rocq/wang/README.md BB_WT in Rocq: BB_WT(5) = 6, BB_WT(6) = 8, BB_WT(7) = 16, BB_WT(8) ≥ 17]". Github document, November 2026. Accessed 7 November 2026.</ref> | ||
|<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,6,1,5] [4,5,2,6]</code> | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,6,1,5] [4,5,2,6]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 5.png|alt=The best known champion for the largest valid square patch (6 by 6) made by a set of 5 Wang tiles.|border|center|frameless]] | |||
|- | |- | ||
|6 | |6 | ||
| | |8<ref name="YeyitoWTRocq" /> | ||
|<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,7,1,6] [5,6,2,7]</code> | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,7,1,6] [5,6,2,7]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 6.png|alt=The best known champion for the largest valid square patch (8 by 8) made by a set of 6 Wang tiles.|border|center|frameless]] | |||
|- | |||
|7 | |||
|16<ref name="YeyitoWTRocq" /> | |||
|<code>[4,0,3,0] [3,0,4,1] [3,1,3,2] [5,2,4,0] [4,1,4,2] [4,1,3,1] [3,2,5,0]</code><ref name="YeyitoWTdcannounce">https://discord.com/channels/960643023006490684/1529586687926210691/1567754354671493152</ref> | |||
|[[File:BusyBeaverWangTiles CurrentChampion 7.png|alt=The best known champion for the largest valid square patch (16 by 16) made by a set of 7 Wang tiles.|border|center|frameless]] | |||
|- | |||
|8 | |||
|≥ 17<ref name="YeyitoWTRocq" /> | |||
|<code>[4,0,3,0] [3,0,4,1] [3,1,3,2] [5,2,4,0] [4,1,4,2] [4,1,3,1] [3,2,5,0] [0,0,3,1]</code><ref name="YeyitoWTdcannounce" /> | |||
|[[File:BusyBeaverWangTiles CurrentChampion 8.png|alt=The best known champion for the largest valid square patch (17 by 17) made by a set of 8 Wang tiles.|border|center|frameless]] | |||
|- | |||
|9 | |||
|≥ 17 | |||
|<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,0,6,0] [6,0,7,0] [7,9,1,8] [7,8,2,9] [6,8,3,9]</code> | |||
|[[File:BusyBeaverWangTiles CurrentChampion 9.png|alt=The best known champion for the largest valid square patch (17 by 17) made by a set of 9 Wang tiles.|border|center|frameless]] | |||
|- | |||
|10 | |||
|≥ 212<ref name="JeandelRao2021">Emmanuel Jeandel, Michaël Rao, "[https://arxiv.org/pdf/1506.06492 An aperiodic set of 11 Wang tiles]". January 2021. Accessed 7 November 2026.</ref> | |||
| | |||
| | |||
|} | |} | ||
== Analysis == | |||
TODO | |||
== References == | |||
[[Category:Functions]] | |||
[[Category:Stubs]] | |||
Latest revision as of 15:55, 7 November 2026
Wang Tiles (or Wang dominoes) are a class of formal mathematical systems first proposed by Hao Wang in 1961. They consist of equal-sized square tiles with colored edges that are arranged side-by-side on a regular grid.
When placing tiles to cover an infinite plane, you must strictly follow three structural constraints:
- Orientation: Tiles must be placed with a fixed orientation and cannot be rotated or reflected.
- Edge Matching: Adjoining edges of touching tiles must share the exact same color.
- Grid Alignment: Every tile must occupy exactly one square in a standard square grid.
Busy Beaver function
Define the score of a set of Wang tiles as the largest d such that it can tile a dxd square, or 0 if there is no largest d.
Then BBWT(n) = the maximum score over all n-tile sets.
The current format to describe a set of tiles is a list of tuples that have 4 nonegative numbers, each representing a side color. Example: [TOP,RIGHT,BOTTOM,LEFT]
| n | Value | Champion | Image |
|---|---|---|---|
| 1 | 1 | [1,0,0,0]
|
 |
| 2 | 2 | [1,0,2,0] [2,0,3,0]
|
 |
| 3 | 3 | [1,0,2,0] [2,0,3,0] [3,0,4,0]
|
 |
| 4 | 4 | [1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0]
|
 |
| 5 | 6[1] | [1,0,2,0] [2,0,3,0] [3,0,4,0] [4,6,1,5] [4,5,2,6]
|
 |
| 6 | 8[1] | [1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,7,1,6] [5,6,2,7]
|
 |
| 7 | 16[1] | [4,0,3,0] [3,0,4,1] [3,1,3,2] [5,2,4,0] [4,1,4,2] [4,1,3,1] [3,2,5,0][2]
|
 |
| 8 | ≥ 17[1] | [4,0,3,0] [3,0,4,1] [3,1,3,2] [5,2,4,0] [4,1,4,2] [4,1,3,1] [3,2,5,0] [0,0,3,1][2]
|
 |
| 9 | ≥ 17 | [1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,0,6,0] [6,0,7,0] [7,9,1,8] [7,8,2,9] [6,8,3,9]
|
 |
| 10 | ≥ 212[3] |
Analysis
TODO
References
- ↑ 1.0 1.1 1.2 1.3 Yeyito, "BB_WT in Rocq: BB_WT(5) = 6, BB_WT(6) = 8, BB_WT(7) = 16, BB_WT(8) ≥ 17". Github document, November 2026. Accessed 7 November 2026.
- ↑ 2.0 2.1 https://discord.com/channels/960643023006490684/1529586687926210691/1567754354671493152
- ↑ Emmanuel Jeandel, Michaël Rao, "An aperiodic set of 11 Wang tiles". January 2021. Accessed 7 November 2026.