Wang Tiles: Difference between revisions
Jump to navigation
Jump to search
m →Busy Beaver function: proper subscript |
Elgan65536 (talk | contribs) Add text notation for champions 7, 8, and 9 |
||
| Line 53: | Line 53: | ||
|7 | |7 | ||
|≥ 11 | |≥ 11 | ||
| | |<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] [4,6,3,7]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 7.png|alt=The best known champion for the largest valid square patch (11 by 11) made by a set of 7 Wang tiles.|border|center|frameless]] | |[[File:BusyBeaverWangTiles CurrentChampion 7.png|alt=The best known champion for the largest valid square patch (11 by 11) made by a set of 7 Wang tiles.|border|center|frameless]] | ||
|- | |- | ||
|8 | |8 | ||
|≥ 14 | |≥ 14 | ||
| | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,0,6,0] [6,8,1,7] [6,7,2,8] [5,7,3,8]</code> | ||
|[[File:BusyBeaverWangTiles CurrentChampion 8.png|alt=The best known champion for the largest valid square patch (14 by 14) made by a set of 8 Wang tiles.|border|center|frameless]] | |[[File:BusyBeaverWangTiles CurrentChampion 8.png|alt=The best known champion for the largest valid square patch (14 by 14) made by a set of 8 Wang tiles.|border|center|frameless]] | ||
|- | |- | ||
|9 | |9 | ||
|≥ 17 | |≥ 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]] | |[[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]] | ||
|- | |- | ||
Revision as of 16:14, 3 October 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,0,2,0] [2,0,3,0] [3,0,4,0] [4,6,1,5] [4,5,2,6]
|
 |
| 6 | ≥ 8 | [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 | ≥ 11 | [1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,7,1,6] [5,6,2,7] [4,6,3,7]
|
 |
| 8 | ≥ 14 | [1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0] [5,0,6,0] [6,8,1,7] [6,7,2,8] [5,7,3,8]
|
 |
| 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 |
Analysis
TODO