)
An edge-matching puzzle is a type of tiling puzzle involving tiling an area with (typically regular) polygons whose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match.
Edge-matching puzzles are known to be NP-complete, and capable of conversion to and from equivalent jigsaw puzzles and polyomino packing puzzle.[1]
The first edge-matching puzzles were patented in the U.S. by E. L. Thurston in 1892.[2] Percy Alexander MacMahon published a treatise on edge-colouring of a variety of shapes in 1921.[3]
Current examples of commercial edge-matching puzzles include the Eternity II puzzle, TetraVex, Dodek Duo, Kadon Enterprises' range of edge-matching puzzles, and the Edge Match Puzzles iPhone app.
)
The Carcassonne board game employs edge matching to constrain where its square tiles may be placed. The original game has three types of edges: fields, roads and cities.
See also
- Domino tiling
- Serpentiles
- Three-dimensional edge-matching puzzle
- Wang tiles
References
- ^ Erik D. Demaine, Martin L. Demaine. "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity" (PDF). Retrieved 2007-08-12.
- ^ "Rob's puzzle page: Edge Matching". Archived from the original on 2007-10-22. Retrieved 2007-08-12.
- ^ MacMahon, Percy Alexander (1921). New mathematical pastimes. Gerstein - University of Toronto. Cambridge, University Press.
External links
- Erich's Matching Puzzles Collection
- Color- and Edge-Matching Polygons by Peter Esser
- Rob's puzzle page by Rob Stegmann
- Edge matching squares