Math major Nathon Harris to present at national conference on undergraduate research
An edge-matching puzzle is a type of tiling puzzle involving tiling an area with (typically regular) polygons whose edges are distinguished with colors 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 puzzles. The first edge-matching puzzles were patented in the U.S. by E. L. Thurston in 1892.Edge-matching puzzles have recently enjoyed resurgence in popularity with the 2007 release of Eternity II, a 16×16 edge-matching puzzle with a 2 million dollar prize for its solution. Due to the number of possible solutions, the puzzle is not solvable using computer methods in any reasonable amount of time. Possible methods of reducing search time as well as pattern matching methods were attempted in this paper.