Wang Tiles

Wang tiles are square tiles whose four edges are assigned colors (or, more generally, constraints). Two tiles may be placed adjacent to one another only when the colors on their shared edge match. Despite these simple local rules, Wang tiles can produce remarkably complex global patterns.

The example below shows a tileset consisting of two tiles and three edge colors (orange, blue, and red).

Finding a valid tiling can be formulated as a constraint satisfaction problem (CSP). Each position in the grid is a variable whose domain consists of the available Wang tiles, while the constraints require neighboring tiles to have matching edge colors.

Solver Design

Rather than placing tiles individually, the solver operates on complete rows. For a fixed row width N, it first enumerates every horizontally valid row that can be formed from the tileset. Each row becomes a node in a directed graph, with an edge connecting two rows whenever they can be stacked while satisfying every vertical edge constraint.

This transforms the original CSP into a graph search problem. A path through the graph corresponds to constructing a valid tiling one row at a time, while cycles represent patterns that can continue indefinitely. Before searching, the graph is reduced by computing its strongly connected components (SCCs), eliminating dead ends and retaining only rows that can participate in infinite tilings.

Weisfeiler–Leman Graph Reduction

The resulting graph is further compressed using Weisfeiler–Leman (WL) refinement. This algorithm repeatedly relabels each node according to the structure of its neighborhood, producing a structural fingerprint for every row. Nodes with equivalent fingerprints can be merged or pruned, substantially reducing the search space while preserving all valid tilings.

The graph below was generated for the example tileset above using a row width of N = 9.

Traversing this graph produces the following infinite tiling. Additional examples can be found at Anniversary Gallery .