Can this hexagonal region be tiled with lozenges — diamond-shaped pieces covering two adjacent triangles? The question seems geometric: fit shapes into a space. Conway and Thurston showed it is algebraic: assign a height function to the vertices of the triangular grid, and a valid tiling corresponds to a height function that increases by exactly 1 across each lozenge edge. The tiling exists if and only if a consistent height assignment exists.
Favreau, Gerard, Lafourcade, and Robert show it is graph-theoretic: the height consistency conditions are difference constraints. Vertex A must be exactly 1 higher than vertex B across a lozenge boundary. Difference constraints are negative-cycle detection. The tiling exists if and only if a certain weighted directed graph has no negative-weight cycles — a problem solved in cubic time by the Bellman-Ford algorithm.
The translation is exact, not approximate. Every constraint of the tiling problem maps to an edge in the graph. Every edge weight encodes a height difference. Every negative cycle corresponds to an impossible configuration — a closed path where the required height changes are mutually contradictory. Bellman-Ford does not search for tilings; it searches for contradictions.
The algorithm is the first polynomial-time solution to the Calisson puzzle with prescribed boundary constraints (certain edges must remain tile boundaries, adjacent lozenges must differ in orientation). Previous approaches either enumerated tilings or used ad hoc geometric reasoning. The graph formulation extends naturally to infinite regions with finitely many local constraints — the algorithm terminates whenever the constraint graph is finite, regardless of the tiled area.
The deeper point: tiling is not about fitting shapes. It is about the absence of contradictions in a system of local constraints. The shapes are incidental; the constraints are structural. Bellman-Ford finds the answer not by assembling a tiling but by failing to find a reason one cannot exist.