Edge-matching puzzle
Anedge-matching puzzleis a type oftiling puzzleinvolvingtilingan area with (typically regular)polygonswhose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match.
Edge-matching puzzles are known to beNP-complete,and capable of conversion to and from equivalentjigsaw puzzlesandpolyominopacking puzzle.[1]
The first edge-matching puzzles were patented in the U.S. byE. L. Thurstonin 1892.[2]Current examples of commercial edge-matching puzzles include theEternity II puzzle,Tantrix,Kadon Enterprises' range of edge-matching puzzles, and the Edge Match Puzzles iPhone app.
Notable variations
[edit]MacMahon Squares
[edit]
MacMahon Squares is the name given to arecreational mathpuzzle suggested by British mathematicianPercy MacMahon,who published a treatise on edge-colouring of a variety of shapes in 1921.[4]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.[5]
This puzzle can be extended to tiles with permutations of 4 colors, arranged in 10×7.[6]In either case, the squares are a subset of theWang tiles,reducing tiles that are similar under rotation. Solutions number well into the thousands.[7]
MacMahon Squares, along with variations on the idea, was commercialized as Multimatch.
TetraVex
[edit]
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.[8][9]
TetraVex was inspired by "the problem of tiling the plane" as described byDonald Knuthon page 382 ofVolume 1: Fundamental Algorithms,the first book in his seriesThe 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 forWindows Entertainment Pack 3.[10]
TetraVex is also available as an open source game in theGNOME Gamescollection.[11]
The possible number of TetraVex can be counted. On aboard there arehorizontal and vertical pairs that must match andnumbers along the edges that can be chosen arbitrarily. Hence there arechoices of 10 digits, i.e.possible boards.
Deciding if a TetraVex puzzle has a solution is in generalNP-complete.[12]Its computational approach involves theDouglas-Rachford algorithm.[13]
Hexagons
[edit]
Serpentilesare the hexagonal tiles used in variousabstract strategy gamessuch as Psyche-Paths, Kaliko, andTantrix.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.
Three dimensions
[edit]Mathematically, edge-matching puzzles aretwo-dimensional.A 3D edge-matching puzzle is such a puzzle that is not flat inEuclidean space,so involvestilinga three-dimensional area such as the surface of aregular polyhedron.As before,polygonalpieces 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.[2]Current examples of commercial puzzles include theDodek Duo,The Enigma, Mental Misery,[14]and Kadon Enterprises' range of three-dimensional edge-matching puzzles.[15]
Incorporation of edge matching
[edit]
TheCarcassonneboard 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
[edit]References
[edit]- ^Erik D. Demaine,Martin L. Demaine."Jigsaw Puzzles, Edge Matching, and Polyomino Packing: Connections and Complexity"(PDF).Retrieved2007-08-12.
- ^ab"Rob's puzzle page: Edge Matching".Archived fromthe originalon 2007-10-22.Retrieved2007-08-12.
- ^Gardner, Martin (2009).Sphere Packing, Lewis Caroll and Reversi.Cambridge University Press.
- ^MacMahon, Percy Alexander (1921).New mathematical pastimes.Gerstein - University of Toronto. Cambridge, University Press.
- ^Steckles, Katie. Blackboard Bold:MacMahon Squares.Retrieved 10 March 2021.
- ^Guy. Cube Root of 31.Wang Tiles.Retrieved 12 April 2021.
- ^Wade Philpott (credited). Kadon Enterprises.Multimatch.Retrieved 12 April 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.Retrieved2010-05-11.
- ^"License - README".gnome-games.gnome.org. 2011.Retrieved2012-10-02.
- ^Takenaga, Yasuhiko; Walsh, Toby (15 September 2006)."TetraVex is NP-complete".Information Processing Letters.99(5). Information Processing Letters, Volume 99, Issue 5, Pages 171–174: 171–174.doi:10.1016/j.ipl.2006.04.010.S2CID7228681.
- ^Linstrom, Scott B.;Sims, Brailey(2020). Survey: Sixty years of Douglas Rachford. Cambridge University Press.
- ^"Rob's puzzle page: Pattern Puzzles".Retrieved2009-06-22.
- ^"Kadon Enterprises, More About Edgematching".Retrieved2009-06-22.
External links
[edit] | Thiscombinatorics-related article is astub.You can help Wikipedia byexpanding it. |