A finite Wang tile puzzle asks for a matching arrangement inside a bounded region. Unlike the infinite domino problem, a puzzle can be checked directly: inspect each horizontal and vertical contact and confirm that its two colors agree. Finding the arrangement can still demand substantial search.
What exactly is the puzzle?
There are several common models. A protoset puzzle provides unlimited copies of each type. An inventory puzzle supplies a fixed multiset. Some puzzles prescribe colors around the boundary; others leave outside edges free. Rotation may be forbidden, optional, or the only move. These distinctions matter: they change which placements are equivalent and which deductions are sound.
Commercial edge-matching puzzles often use a fixed inventory and richer symbols, while theoretical Wang tilings use unlimited translated copies. Both are constraint-satisfaction problems. A cell is a variable, each oriented tile is a candidate value, and every shared edge contributes a compatibility constraint.
Human solving techniques
- Start with constrained cells. Corners are not automatically constrained on an open board, but fixed boundary colors, walls, and already placed neighbors reduce choices.
- Index edge signatures. Group candidates by top, right, bottom, and left color rather than scanning the whole palette.
- Propagate immediately. A placement changes candidate lists in neighboring cells; a singleton candidate is forced.
- Respect inventory. With finite copies, using the last tile of a type can eliminate candidates far away.
- Backtrack deliberately. When guessing is unavoidable, choose the cell with the fewest candidates and remember the branch.
How software solves them
Backtracking becomes effective when combined with constraint propagation and a minimum-remaining-values heuristic. Exact-cover formulations, SAT solvers, integer programming, and transfer-matrix methods are also useful. The best representation depends on whether the task is to find one solution, count all solutions, prove impossibility, or test periodic boundary conditions.
Finite rectangular Wang tiling variants are computationally hard in general, and the infinite-plane question is undecidable. That contrast is important: a particular 15 × 15 puzzle is finite and decidable, even though no algorithm can settle every possible protoset’s ability to tile the whole plane.
What makes a satisfying puzzle?
A good puzzle is not merely solvable. It should avoid a long sequence of arbitrary choices, expose deductions gradually, and use its special rules meaningfully. Uniqueness can help, but a puzzle with several solutions may still be excellent if all roads require insight. Difficulty also depends on presentation: showing candidate hints transforms the experience, while mental-placement rules make every commitment consequential.
Wang World separates the reusable protoset from the board rules and measures search effort with a deterministic complexity model. See how to play, the complete rules, and how Complexity is measured.
Sources
- Hao Wang (1961), the original logical framework.
- Robert Berger (1966), undecidability of the domino problem.
- Solomon W. Golomb, Polyominoes, and Branko Grünbaum & G. C. Shephard, Tilings and Patterns, provide broader context for finite tiling and matching problems.