Edge-matching puzzle

File:MacMahon Squares solution.png

MacMahon Squares is the name given to a recreational math puzzle suggested by British mathematician Percy MacMahon, who published a treatise on edge-colouring of a variety of shapes in 1921.{{Cite book|last=MacMahon|first=Percy Alexander|url=https://archive.org/details/newmathematicalp00macmuoft|title=New mathematical pastimes|date=1921|publisher=Cambridge, University Press|others=Gerstein - University of Toronto}} 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.Steckles, Katie. Blackboard Bold: [https://aperiodical.com/2012/03/macmahon-squares/ MacMahon Squares]. Retrieved 10 March 2021.

This puzzle can be extended to tiles with permutations of 4 colors, arranged in 10×7.Guy. Cube Root of 31. [http://www.cr31.co.uk/stagecast/wang/puzzle.html Wang Tiles]. Retrieved 12 April 2021. In either case, the squares are a subset of the Wang tiles, reducing tiles that are similar under rotation. Solutions number well into the thousands.Wade Philpott (credited). Kadon Enterprises. [http://www.gamepuzzles.com/edgemtch.htm Multimatch]. Retrieved 12 April 2021.

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

File:GNOME Tetravex screenshot.png.]]

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 into 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.Whittum, Christopher (2013). Energize Education Through Open Source. pg 32.Gagné, Marcel (2006). Moving to Ubuntu Linux.

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.{{cite web |url=http://www.forestmoon.com/BIRTHofVB/BIRTHofVB.html |title=The Birth of Visual Basic |publisher=Forestmoon.com |date= |accessdate=2010-05-11}}

TetraVex is also available as an open source game in the GNOME Games collection.{{cite web |title=License - README |work=gnome-games |publisher=gnome.org |year=2011 |url=http://wiki.gnome.org/Apps/Tetravex |accessdate=2012-10-02}}

The possible number of TetraVex positions can be counted. On a $n\backslash 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.{{cite journal |url=http://dx.doi.org/10.1016/j.ipl.2006.04.010 | title=TetraVex is NP-complete |publisher=Information Processing Letters, Volume 99, Issue 5, Pages 171–174 |date= 15 September 2006| doi=10.1016/j.ipl.2006.04.010 | last1=Takenaga | first1=Yasuhiko | last2=Walsh | first2=Toby | journal=Information Processing Letters | volume=99 | issue=5 | pages=171–174 | s2cid=7228681 }} Its computational approach involves the Douglas-Rachford algorithm.Linstrom, Scott B.; Sims, Brailey (2020). Survey: Sixty years of Douglas Rachford. Cambridge University Press.

File:Serpentile 021 3C 0-GR-B.svg

Serpentiles are the hexagonal tiles used in various abstract strategy games such as Psyche-Paths, Kaliko, and Tantrix. Within each serpentile, the edges are paired, thus restricting the set of tiles in such a way that no edge color occurs an odd number of times within the hexagon.

{{main|Three-dimensional edge-matching puzzle}}

Mathematically, edge-matching puzzles are two-dimensional. A 3D edge-matching puzzle is such a puzzle that is not flat in Euclidean space, so involves tiling a three-dimensional area such as the surface of a regular polyhedron. As before, polygonal pieces have distinguished edges to require that the edges of adjacent pieces match.

3D edge-matching puzzles are not currently under direct U.S. patent protection, since the 1892 patent by E. L. Thurston has expired. Current examples of commercial puzzles include the Dodek Duo, The Enigma, Mental Misery,{{cite web |url=http://home.comcast.net/~stegmann/pattern.htm#em3d |title=Rob's puzzle page: Pattern Puzzles |accessdate=2009-06-22}} and Kadon Enterprises' range of three-dimensional edge-matching puzzles.{{cite web |url= http://www.gamepuzzles.com/moredge.htm|title= Kadon Enterprises, More About Edgematching|accessdate=2009-06-22}}

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.

• Domino tiling
• Tiling puzzle
• Wang dominoes

• [https://web.archive.org/web/20070320055301/http://www.stetson.edu/~efriedma/rubik/match/index.html Erich's Matching Puzzles Collection]
• [https://web.archive.org/web/20071022103557/http://home.comcast.net/~stegmann/pattern.htm Rob's puzzle page] by Rob Stegmann
• [http://puzzlesland.com/puzzles/squares/squares.htm Edge matching squares]

Category:Tiling puzzles

Category:NP-complete problems

{{combin-stub}}