Variable Transformation to a 2x2 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×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 languageEnglish
Title of host publicationTrends in Artificial Intelligence Theory and Applications. Artificial Intelligence Practices
Subtitle of host publication33rd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2020, Kitakyushu, Japan, September 22-25, 2020, Proceedings
EditorsH. Fujita, P. Fournier-Viger, M. Ali, J. Sasaki
Place of PublicationCham
PublisherSpringer
Pages210-221
ISBN (Electronic)978-3-030-55789-8
ISBN (Print)978-3-030-55788-1
DOIs
Publication statusPublished - 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

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12144
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

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

  • 1 Presentation

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

Cite this

Aspinall, T., Gepp, A., Harris, G., & Vanstone, B. J. (2020). Variable Transformation to a 2x2 domain space for Edge Matching Puzzles. In H. Fujita, P. Fournier-Viger, M. Ali, & J. Sasaki (Eds.), 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, Kitakyushu, Japan, September 22-25, 2020, Proceedings (pp. 210-221). (Lecture Notes in Computer Science; Vol. 12144). Springer. https://doi.org/10.1007/978-3-030-55789-8_19