Edge-matching puzzle

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] Current examples of commercial edge-matching puzzles include the Eternity II puzzle, Tantrix, Kadon Enterprises' range of edge-matching puzzles, and the Edge Match Puzzles iPhone app.

Notable variations

MacMahon Squares

MacMahon Squares is the name given to a recreational math puzzle suggested by Percy MacMahon, who published a treatise on edge-colouring of a variety of shapes in 1921.^[3] This particular puzzle uses 24 tiles consisting of all permutations of 3 colors for the edges of a square. The tiles must be arranged into a 6×4 rectangular area such that all edges match and, furthermore, only one color is used for the outside edge of the rectangle.^[4]

MacMahon Squares, along with variations on the idea, was commercialized as Multimatch.

TetraVex

TetraVex is a computer game that presents the player with a square grid and a collection of tiles, by default nine square tiles for a 3×3 grid. Each tile has four single-digit numbers, one on each edge. The objective of the game is to place the tiles in the grid in the proper position, completing this puzzle as quickly as possible. The tiles cannot be rotated, and two can be placed next to each other only if the numbers on adjacent edges match.^[5]^[6]

TetraVex was inspired by "the problem of tiling the plane" as described by Donald Knuth on page 382 of Volume 1: Fundamental Algorithms, the first book in his series The Art of Computer Programming. It was named by Scott Ferguson, the Development Lead and an architect of the first version of Visual Basic, who wrote it for Windows Entertainment Pack 3.^[7]

TetraVex is also available as an open source game in the GNOME Games collection.^[8]

The possible number of TetraVex can be counted. On a $n\times {}n$ board there are $n(n-1)$ horizontal and vertical pairs that must match and $4n$ numbers along the edges that can be chosen arbitrarily. Hence there are $2n(n-1)+4n=2n(n+1)$ choices of 10 digits, i.e. $10^{2n(n+1)}$ possible boards.

Deciding if a TetraVex puzzle has a solution is in general NP-complete.^[9] Its computational approach involves the Douglas-Rachford algorithm.^[10]^[11]

Hexagons

Serpentiles are the hexagonal tiles used in various games such as Psyche-Paths, Kaliko, and Tantrix.

Three dimensions

There are many 3D edge-matching puzzles as well.

Games that incorporate edge matching

File:Carcassonne-meeple.jpg

Part of a Carcassonne game showing matching edges

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.

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.
^ Steckles, Katie. Blackboard Bold: MacMahon Squares. Retrieved 10 March 2021
^ Whittum, Christopher (2013). Energize Education Through Open Source. pg 32.
^ Gagné, Marcel (2006). Moving to Ubuntu Linux.
^ "The Birth of Visual Basic". Forestmoon.com. Retrieved 2010-05-11.
^ "License - README". gnome-games. gnome.org. 2011. Retrieved 2012-10-02.
^ "TetraVex is NP-complete". Information Processing Letters, Volume 99, Issue 5, Pages 171–174. 15 September 2006.
^ Bansal, Pulkit(2010). "Code for solving Tetravex using Douglas–Rachford algorithm". Retrieved 10 March 2021.
^ Linstrom, Scott B.; Sims, Brailey(2020). Survey: Sixty years of Douglas Rachford. Cambridge University Press.

External links

Erich's Matching Puzzles Collection
Color- and Edge-Matching Polygons by Peter Esser ^{[dead link]}
Rob's puzzle page by Rob Stegmann
Edge matching squares

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

[Demaine-1] Erik D. Demaine, Martin L. Demaine. "Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity" (PDF). Retrieved 2007-08-12.

[2] "Rob's puzzle page: Edge Matching". Archived from the original on 2007-10-22. Retrieved 2007-08-12.

[3] MacMahon, Percy Alexander (1921). New mathematical pastimes. Gerstein - University of Toronto. Cambridge, University Press.

[4] Steckles, Katie. Blackboard Bold: MacMahon Squares. Retrieved 10 March 2021

[5] Whittum, Christopher (2013). Energize Education Through Open Source. pg 32.

[6] Gagné, Marcel (2006). Moving to Ubuntu Linux.

[7] "The Birth of Visual Basic". Forestmoon.com. Retrieved 2010-05-11.

[8] "License - README". gnome-games. gnome.org. 2011. Retrieved 2012-10-02.

[9] "TetraVex is NP-complete". Information Processing Letters, Volume 99, Issue 5, Pages 171–174. 15 September 2006.

[10] Bansal, Pulkit(2010). "Code for solving Tetravex using Douglas–Rachford algorithm". Retrieved 10 March 2021.

[11] Linstrom, Scott B.; Sims, Brailey(2020). Survey: Sixty years of Douglas Rachford. Cambridge University Press.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]