||Analysis of restricted edge-matching problems
||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)
||Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
||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.
||Technical University of Denmark (DTU) : Kgs. Lyngby, Denmark
Creation date: 2011-02-23
Update date: 2011-02-23