Variable transformation to a 2×2 Domain Space for Edge Matching Puzzles

Thomas Aspinall, Adrian Gepp*, Geoffrey Harris, Bruce J Vanstone

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterResearchpeer-review

Abstract

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\times 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.

Original language English 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 33rd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2020, Kitakyushu, Japan, September 22-25, 2020, Proceedings H. Fujita, P. Fournier-Viger, M. Ali, J. Sasaki Cham Springer 210-221 12 978-3-030-55789-8 978-3-030-55788-1 https://doi.org/10.1007/978-3-030-55789-8_19 Published - Sep 2020 The 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems - Kitakyushu, JapanDuration: 22 Sep 2020 → 25 Sep 2020Conference number: 33https://jsasaki3.wixsite.com/ieaaie2020

Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 12144 LNAI 0302-9743 1611-3349

Conference

Conference The 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems IEA/AIE 2020 Japan Kitakyushu 22/09/20 → 25/09/20 https://jsasaki3.wixsite.com/ieaaie2020

Fingerprint

Dive into the research topics of 'Variable transformation to a 2×2 Domain Space for Edge Matching Puzzles'. Together they form a unique fingerprint.
• Variable Transformation to a 2x2 domain space for Edge Matching Puzzles

Aspinall, T., Gepp, A., Harris, G. & Vanstone, B. J., Sep 2020, (Unpublished).

Research output: Contribution to conferencePresentationResearchpeer-review

File