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

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

Research output: Contribution to conferencePresentationResearchpeer-review

1 Downloads (Pure)

Abstract

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.
Original languageEnglish
Publication statusUnpublished - Sep 2020
EventThe 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems - Kitakyushu, Japan
Duration: 22 Sep 202025 Sep 2020
Conference number: 33
https://jsasaki3.wixsite.com/ieaaie2020

Conference

ConferenceThe 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems
Abbreviated titleIEA/AIE 2020
CountryJapan
CityKitakyushu
Period22/09/2025/09/20
Internet address

Related Research Outputs

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

Aspinall, T., Gepp, A., Harris, G. & Vanstone, B. J., Sep 2020, 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. Fujita, H., Fournier-Viger, P., Ali, M. & Sasaki, J. (eds.). Cham: Springer, p. 210-221 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12144 LNAI).

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

  • Cite this

    Aspinall, T., Gepp, A., Harris, G., & Vanstone, B. J. (2020). Variable Transformation to a 2x2 domain space for Edge Matching Puzzles. The 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems, Kitakyushu, Japan.