Constraint satisfaction

Why you need this

A tileset comes with rules: water only touches sand or water, a cliff top sits above a cliff face, a door needs wall on both sides. Filling a grid so that every rule holds everywhere is a constraint satisfaction problem. Wave Function Collapse, the main fill technique for top-down tilesets in this cluster, is a constraint solver with a random tie-breaker bolted on. Once you see how domains shrink and what a contradiction is, WFC stops looking like magic.

The idea

A constraint satisfaction problem has three parts.

• Variables: the unknowns. In a map, one variable per cell.
• Domains: for each variable, the set of values it may still take. A cell's domain starts as every tile in the tileset and shrinks as you learn things.
• Constraints: rules that say which combinations of values are allowed. Most map constraints are binary, meaning they mention exactly two variables, and those two are neighbors on the grid (see Graphs and grids).

Formally, write the variables as $c_1, c_2, \dots, c_n$, the domain of $c_i$ as $D_i$, and a binary constraint between $c_i$ and $c_j$ as a set of allowed pairs $R_{ij}$. A solution assigns a value $v_i \in D_i$ to each variable such that $(v_i, v_j) \in R_{ij}$ for every constrained pair.

With small numbers: three cells $c_1, c_2, c_3$ in a row, each with domain $\{\text{grass}, \text{sand}, \text{water}\}$, and one rule between each adjacent pair: water only touches sand or water. Equivalently, grass and water are never side by side. The allowed pairs are:

Left	Right allowed
grass	grass, sand
sand	grass, sand, water
water	sand, water

Three variables, three values each, so $3^3 = 27$ raw combinations, of which 17 have no grass next to water and are solutions. The solver's job is to find one without trying all 27.

Constraint propagation

Propagation means: whenever one domain shrinks, look at every constraint touching that variable and remove values from the neighboring domains that no longer have any partner. Doing this until nothing changes makes the problem arc consistent. An arc is one direction of one binary constraint, and it is consistent when every value in the first domain has at least one compatible value in the second. Propagation never guesses; it only deletes values that cannot appear in any solution given what is already known, so it is safe to run as often as you like.

Backtracking search

Propagation alone rarely finishes the job. When every domain is arc consistent but some still hold more than one value, the solver picks a variable and fixes it to one value from its domain, then propagates again. If that leads to a contradiction, meaning some domain becomes empty, the solver backtracks: it undoes the last choice, removes that value from the domain it came from, and tries the next one. If a variable runs out of values, back up one more level. Backtracking is complete, so if a solution exists it will find one given enough time. The cost is bookkeeping: every domain must be restorable to how it was before a choice.

Worked example

Take the three-cell row above, with two extra facts from the layout stage: $c_1$ borders a lake, so it is pinned to water, and $c_3$ borders a village, so it is pinned to grass.

Step	$D_1$	$D_2$	$D_3$	What happened
0	grass, sand, water	grass, sand, water	grass, sand, water	Start.
1	water	grass, sand, water	grass	Apply the pins.
2	water	sand, water	grass	Arc $c_1 \to c_2$: water's partners are sand and water, so grass leaves $D_2$.
3	water	sand	grass	Arc $c_3 \to c_2$: grass's partners are grass and sand, so water leaves $D_2$.

Every domain has one value and every constraint holds: (water, sand, grass). Propagation solved it without a single guess.

Now a case that needs search. Four cells $c_1 \dots c_4$, same rule, $c_1$ pinned to water and $c_4$ pinned to grass.

Step	$D_1$	$D_2$	$D_3$	$D_4$
Pins	water	grass, sand, water	grass, sand, water	grass
Arc $c_1 \to c_2$	water	sand, water	grass, sand, water	grass
Arc $c_4 \to c_3$	water	sand, water	grass, sand	grass

Check the middle arc $c_2 \to c_3$: sand pairs with grass or sand, water pairs with sand, so every value in $D_2$ has a partner. The reverse arc $c_3 \to c_2$ holds too. The problem is arc consistent and two domains still have two values. Time to guess.

Pick $c_2$ and fix it to water. Propagate: arc $c_2 \to c_3$ removes grass from $D_3$, leaving $\{\text{sand}\}$, and sand next to $c_4 =$ grass is allowed. Solution: (water, water, sand, grass). Had you picked $c_2 =$ sand instead, $D_3$ would stay $\{\text{grass}, \text{sand}\}$ and one more guess would finish it. This problem has exactly three solutions: (water, sand, grass, grass), (water, sand, sand, grass), and (water, water, sand, grass).

A contradiction

Contradictions come from guessing before propagation has had its say, or, on a real grid, from propagation being local: arc consistency compares neighboring pairs only and cannot see that choices far apart have painted the solver into a corner.

The small version: in the first example, suppose the solver fixes $c_2 =$ water right after seeing $c_1 =$ water, without propagating from $c_3$ first. Arc $c_2 \to c_3$ now says $D_3$ may hold only sand or water, but $D_3$ was pinned to $\{\text{grass}\}$. Intersect the two and $D_3 = \{\}$. Empty domain, contradiction. Two responses are in common use.

• Backtrack. Undo $c_2 =$ water, delete water from $D_2$, and continue. $D_2$ is now $\{\text{sand}\}$ and propagation finishes. Exact, but you must keep a history of every domain change.
• Restart with a new seed. Throw the grid away and start again with a different random sequence. Wasteful in theory, trivial to code, and on tile-adjacency problems a fresh attempt usually succeeds within a handful of tries. Most Wave Function Collapse implementations do this.

One solution versus a random solution

A plain backtracking solver picks variables and values in a fixed order. On the four-cell problem it always returns (water, sand, grass, grass), the first solution in dictionary order. Correct, and useless for a map generator: every level would be identical and the first tile in your tileset would dominate every map.

A random solver picks which variable to fix next by a rule plus a random tie-break, and which value by drawing from a seeded generator (see Pseudo-random numbers), weighted so common tiles appear often and rare ones rarely. Same seed, same guesses, same map. Different seed, a different member of the 17 (or three) solutions. Both solvers respect the constraints; only the random one samples from the set of solutions.

Wave Function Collapse is exactly this recipe: propagation, plus a random choice of which cell to fix next and what to fix it to, plus restart on contradiction. It chooses the next cell by lowest entropy, which for equal weights means the smallest remaining domain, because a cell with two options is the least likely to cause a contradiction later.

In a map generator

• Catalog. The tileset's edge signatures (see Tilemaps and autotiling) are the constraints: two tiles may sit side by side when their touching edges carry matching labels. WFC can also learn the allowed pairs by recording which tiles were adjacent in a small hand-painted example.
• Layout. Pins. "This chunk is forest" means every cell in the chunk starts with the forest subset as its domain, and a chunk border pins its cells to whatever the neighboring chunk already chose, so seams match.
• Fill. The solver itself, in Wave Function Collapse, and its probabilistic cousin Markov random fields, where "allowed or not" becomes "likely or unlikely".
• Export. A solved grid is one tile id per cell, which is the tile layer format.

Common mistakes

• Constraints that are too strict. "Sand is exactly one tile wide" forces long chains of dependency and the solver contradicts constantly. Symptom: many restarts, or generation never finishes on large grids.
• Forgetting the reverse arc. You propagate from $c_1$ to $c_2$ but never from $c_2$ to $c_1$. Symptom: rule-breaking tiles next to pinned cells, always on one side.
• Propagating only one step. After removing a value from $D_2$, re-check every arc touching $c_2$, not just the one that caused the removal. Symptom: contradictions found deep in the search that could have been caught immediately.
• Fixed variable order. Filling left to right, top to bottom gives diagonal streaks, because every choice has rich information on one side and none on the other. Pick the most constrained cell instead.
• Choosing values uniformly. Every tile becomes equally common, so a four-tile "rare flower" set covers a quarter of the meadow. Weight the value choice.
• No restart limit. An unsatisfiable layout loops forever. Cap the restarts and report the failure up to the layout stage.

Cost

Let $n$ be the number of variables (cells), $d$ the largest domain size (tiles in the set), and $e$ the number of binary constraints (about $2n$ on a von Neumann grid, one edge to the right and one below per cell). One full pass of arc consistency costs $O(e \cdot d^2)$ time, since each arc compares every pair of values once, and $O(n \cdot d)$ memory for the domains. Backtracking is $O(d^n)$ in the worst case, exponential, which is why nobody runs it to completion on a $64 \times 64$ grid; in practice propagation prunes almost everything and restarts replace deep backtracking. It starts to hurt when $d$ passes a few hundred tiles, because the $d^2$ pair table per arc gets large. Precompute it once per tileset, not once per cell.

Going further

• Wave Function Collapse, the technique this page was built to support.
• Entropy, for how WFC ranks which cell to fix next when tile weights differ.
• The AC-3 algorithm, the standard worklist version of arc consistency.
• Sudoku as a constraint satisfaction problem: 81 variables, domain 1 to 9, "all different" on rows, columns, and boxes.
• Minimum remaining values and forward checking, the textbook names for "pick the smallest domain" and "propagate after every choice".