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. The first edge-matching puzzles were patented in the U.S. by E. L. Thurston in 1892. 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 British mathematician Percy MacMahon, who published a treatise on edge-colouring of a variety of shapes in 1921. 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. This puzzle can be extended to tiles with permutations of 4 colors, arranged in 10×7. In either case, the squares are