Variable Transformation to a 2x2 domain space for Edge Matching Puzzles

This paper investigates combinatorial problem spaces of the worst-case complexity instances of the well-known Edge Matching Puzzle (EMP) problem set, popularized by the Eternity II (E2) challenge. A transformation of the domain space to consider pieces at the 2x2 level is demonstrated to result in search spaces that are orders of magnitude smaller in size at the cost of increasing the total number of elements. Unlike the original domain space, however, which has uniform domain sizes, the transformed space has statistically exploitable features. Two heuristics are proposed and compared to both the original search space and the raw transformed search space. The efficacy of the heuristics is empirically demonstrated along with a physical explanation of how the mapping results in an overall decrease in the number of nodes in the solution search space of the transformed problem.