Wang Tiles: Difference between revisions
Jump to navigation
Jump to search
Created page |
→Busy Beaver function: Added champions |
||
| Line 11: | Line 11: | ||
Then BB_WT(n) = the maximum score over all n-tile sets. | Then BB_WT(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> | |||
{| class="wikitable" | {| class="wikitable" | ||
|+ | |+ | ||
| Line 19: | Line 21: | ||
|1 | |1 | ||
|1 | |1 | ||
| | |<code>[0,0,0,0]</code> | ||
|- | |- | ||
|2 | |2 | ||
|2 | |2 | ||
| | |<code>[1,0,2,0] [2,0,3,0]</code> | ||
|- | |- | ||
|3 | |3 | ||
|3 | |3 | ||
| | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0]</code> | ||
|- | |- | ||
|4 | |4 | ||
| | |4 | ||
| | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,0,5,0]</code> | ||
|- | |- | ||
|5 | |5 | ||
|≥ 6 | |≥ 6 | ||
| | |<code>[1,0,2,0] [2,0,3,0] [3,0,4,0] [4,6,1,5] [4,5,2,6]</code> | ||
|- | |- | ||
|6 | |6 | ||
|≥ 8 | |≥ 8 | ||
| | |<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> | ||
|} | |} | ||
Revision as of 20:01, 11 August 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 BB_WT(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 |
|---|---|---|
| 1 | 1 | [0,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]
|