How To Make Wang Tiles Rotatable
Everyone who cares about aperiodic tilings knows Wang tiles, they are pretty neat.
However, I seem to be a rare kind of person who is really annoyed by the fact that the tiles cannot be rotated. I found a paper that presents a simple encoding of Wang tiles into rotatable hexagonal tiles. However, if all you want is making the rather abstract Wang tiles more geometric, i.e. make them rotatable, flippable and remove the need for colors – it is actually pretty easy to do, even though I have not seen the construction presented explicitly.
It looks like the few needed tricks are folklore knowledge in the field that might be considered trivial and is not discussed too much when used in more involved constructions. So in this short post, I will explicitly present a simple way how to do it.
Adding More Colors
First let us understand what it actually means that Wang tiles are “not rotatable” – it simply means that we assume that left sides always connect to right sides and top sides to bottom sides, given that their color matches. So we have to transform the tiles in such a way that rotating them cannot allow to accidentally match sides of two tiles that are not supposed to be matched. In the first step, we enforce the distinction between horizontal (E/W) and vertical (N/S) sides, by duplicating each color[1], e.g. we need to distinguish between “vertical blue” and “horizontal blue” by recoloring the tile sides along one of the axes.
The set of Wang tiles above uses red ($R$), green ($G$), blue ($B$) and white ($W$), so we can add magenta ($M$), yellow ($Y$), cyan ($C$) and black ($K$) and simply recolor the vertical sides to the respective assigned “twin color” using the mapping $R \to M$, $G \to Y$, $B \to C$, $W \to K$. This ensures that horizontal and vertical sides cannot be matched anymore.
Adding Color Charge
In the next step, we need to ensure the remaining part of the constraint, e.g. we still need to prevent the matching of two top sides of a Wang tile. Therefore we need to somehow distinguish between the two opposing tile sides. To do that, we introduce a charge (+/-) to the colored sides and change the constraints from being symmetrical (i.e., two colors match if they are equal) to being complementary (i.e., two equal colors only match if they have opposite charge).
In our example, we will charge N/E sides with $+$, and S/W sides with $-$, matching the typical orientation of axes in the 2D plane. The resulting Wang-tiles with charged color constraints then look as follows:
From Charged Colors To Geometric Constraints
We could stop here – the tiles in the new tileset, with the modified colors and matching rules, can now be freely rotated and the forbidden pairings are now excluded by the new constraints. However, while constraints such as edge colors can be really useful for designing tiles with desired properties, ultimately the most pure and elegant kind of tile is one that does not have any additional extra information attached to its edges. The shape of the tiles should already suffice to express matching rules, like in a jigsaw puzzle.
For each distinct matching pair of charged colors $X_{\pm}$ we need to substitute the corresponding straight line segments by a unique curve or path of multiple line segments. One aspect to consider here is whether we want or need to prevent flipping of tiles, i.e. whether we want to make it impossible to match two tiles with opposite chirality. To make cross-chiral matchings impossible, it suffices to ensure that the curve or path is not palindromic in a geometric sense, i.e. the boundaries of flipped tiles must not be equal to any boundary of an unflipped tile.
All of this is easily realized if we substitute each color pair $X_{\pm}$ by two paths that match like a lock and key. The key and lock correspond to $X_+$ and $X_-$, respectively, and the paths are constructed from the original single straight line segments by adding bumps to the key and complementary dents to the lock. To ensure chirality, we can simply w.l.o.g. use only the second half of the key boundary to add bumps (i.e. equally, only first half of a lock boundary for the dents), leaving the respective other half of the boundary as-is, i.e. a straight line. If such a tile is flipped, the first and second halves of all boundary paths switch places, accidental matching of two opposite-handed tiles is prevented by design – you will not be able to tile the plane without gaps if you try matching any tiles with opposite chirality.[2]
There are many ways to create a family of complementary paths satisfying the requirements above. Here we will use maybe not the most aesthetic, but conceptually simple and consistent approach – we simply identify each color with a number, i.e., we can assume that the used charged colors are all of the form $i_{\pm}$ with $1 \leq i \leq n$ for some $n \in \mathbb{N}$[3]. Then we derive the complementary paths from the binary encoding of the respective number. We use a fixed number of bits that is enough to represent all numbers up to $n$, e.g. if $n=30$, then $13 = 01101_2$. The bits which are set to 1 determine the location of bumps on the key path (for $+$) and dents on the matching lock path (for $-$).
Even though there are many little details that could be further discussed and formalized, I think this is a great example of a case where one picture is worth a thousand words and the following sketch makes the transformation clearer than anything I could write in addition to the provided high-level description:
As you can easily see, the resulting tileset still works the same way as before, but now it does not need any auxiliary edge labels or colors, and the same approach can also be used for other regular polygon tiles (i.e. triangular and hexagonal tiles).
That’s it! I hope you also find this interesting, and maybe even useful. Now you should be able to easily design your own Wang tile jigsaw puzzle. Happy tiling!
-
If a color is only used on only vertical/horizontal side and not both, we do not need to duplicate it, but to keep it simple, let us assume nothing about how colors are used in a given tile set, as we need to duplicate all of the colors in the worst case anyway. ↩
-
Of course, this kind of construction is not new, and there are many different ways to do it. One very general recipe of a similar kind is used to derive the spectre tile from the hat tile. ↩
-
Note that we do not use the number 0 to encode a color, because, as you will see, in our encoding it would result in a path without any bumps or dents, which is problematic for multiple reasons related to the symmetries of the resulting tile. ↩