TY - CHAP

T1 - Variable transformation to a 2×2 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 - The Eternity II (E2) challenge is a well-known instance of the set of Edge Matching Puzzles (EMP), which are examples of combinatorial problem spaces of the worst-case complexity. Transformation of the domain space to consider pieces at the $$2$$ level increases the total number of elements but is shown to result in orders of magnitude smaller search spaces. While the original domain space has uniform cardinality, the transformed space exhibits 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 two heuristics is empirically demonstrated. An explanation of how the mapping results in an overall decrease in the number of nodes in the solution search space of the transformed problem is outlined.

AB - The Eternity II (E2) challenge is a well-known instance of the set of Edge Matching Puzzles (EMP), which are examples of combinatorial problem spaces of the worst-case complexity. Transformation of the domain space to consider pieces at the $$2$$ level increases the total number of elements but is shown to result in orders of magnitude smaller search spaces. While the original domain space has uniform cardinality, the transformed space exhibits 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 two heuristics is empirically demonstrated. An explanation of how the mapping results in an overall decrease in the number of nodes in the solution search space of the transformed problem is outlined.

U2 - 10.1007/978-3-030-55789-8_19

DO - 10.1007/978-3-030-55789-8_19

M3 - Chapter

SN - 978-3-030-55788-1

T3 - Lecture Notes in Computer Science

SP - 210

EP - 221

BT - Trends in Artificial Intelligence Theory and Applications. Artificial Intelligence Practices - 33rd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2020, Proceedings

A2 - Fujita, H.

A2 - Fournier-Viger, P.

A2 - Ali, M.

A2 - Sasaki, J.

PB - Springer

CY - Germany

ER -