#31: Aperiodic Tiling

Tagged as challenge

Written on 2018-01-30

Wang tiles are a collection of oriented squares with colored edges such that when you place the squares side-by-side with matching colors, the plane will tile aperiodically. That is to say, without rotating or reflecting the tiles, when placed according to the color matching rule, repetitions of tiles cannot occur within contiguous sections of the plane, as soon as the sections are large enough.

Wang tiles are specified by listing their colors starting with the top edge and going clockwise. One set of Wang tiles consists of 13 tiles using 4 colors. The tiles are listed below.

Wang Tiles
----------
RRRG
BRBG          Example Tile: RGBW
RGGG
WBRB                 Red
BBWB                +----+
WWRW                |    | Green
RGBW          White |    |
BWBR                +----+
BRWR                 Blue
GGBR
RWRG

Part 1

Write a program that generates a random $M\times N$ rectangle of Wang tiles.

Part 2

Suppose the centers of the squares are placed in the plane at integer lattice points. Then we can identify each square in the plane by its center.

Write a function (spiral n) which gives the $n$th coordinate of a spiral starting at $(0, 0)$ to $(1, 0)$ and proceeding counterclockwise. The first few values are:

0 => (0, 0)    3 => (0, 1)     6 => (-1, -1)
1 => (1, 0)    4 => (-1, 1)    7 => (0, -1)
2 => (1, 1)    5 => (-1, 0)    8 => (1, -1)

With this, write a function (wang-spiral n) which produces a Wang tiling valid on the coordinates (spiral 0) to (spiral (- n 1)).

Extra Credit

Draw your artwork.

• ← Previous
• Next →