Beta 1


Title Analysis of restricted edge-matching problems
Author Ebbesen, Martin
Supervisor Fischer, Paul (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Witt, Carsten (Algorithms and Logic, Department of Informatics and Mathematical Modeling, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2011
Abstract Edge-matching puzzles were invented as a toy more than 100 years ago. These puzzles can range from the simple to the extremely difficult, as exemplified by the as-of-yet unsolved Eternity II puzzle for which a large prize was offered. One variant of edge-matching was recently (2007) shown to be NP-Complete. This report will formalize a more general notion of edge-matching and show that some variations are equivalent in complexity. Properties like the expected number of solutions for different edge-matching variants are discussed and visualizations of the phase transition for edge-matching is presented. A main theme of the report is a variant of edge-matching which is restricted to 1D, for which some variants are shown to be solvable in polynomial time, and in fact equivalent to the Eulerian path problem, while other variants of 1D edge-matching are shown to be NP-Complete just like the general 2D case. Finally this report will work with a restricted variant of edge-matching where individual pieces can rotate but not move, and show that this variant is, in the 1D case, solvable in polynomial time. As part of the project, an application for experimenting with edge-matching was developed – this is discussed in an the appendices.
Imprint Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Series IMM-M.Sc.-2011-08
Fulltext
Original PDF ep11_08_A4.pdf (2.18 MB)
Admin Creation date: 2011-02-23    Update date: 2011-02-23    Source: dtu    ID: 275156    Original MXD