TY - CONF

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

AU - Aspinall, Thomas

AU - Gepp, Adrian

AU - Harris, Geoffrey

AU - Vanstone, Bruce J

N1 - The 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems, IEA/AIE 2020 ; Conference date: 22-09-2020 Through 25-09-2020

PY - 2020/9/1

Y1 - 2020/9/1

N2 - 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.

AB - 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.

M3 - Paper

ER -