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

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

doi:10.1007/978-3-030-55789-8_19

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 proceeding › Chapter › Research › peer-review

160 Downloads (Pure)

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
Title of host publication	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
Subtitle of host publication	33rd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2020, Kitakyushu, Japan, September 22-25, 2020, Proceedings
Editors	H. Fujita, P. Fournier-Viger, M. Ali, J. Sasaki
Place of Publication	Cham
Publisher	Springer
Pages	210-221
Number of pages	12
ISBN (Electronic)	978-3-030-55789-8
ISBN (Print)	978-3-030-55788-1
DOIs	https://doi.org/10.1007/978-3-030-55789-8_19
Publication status	Published - Sept 2020
Event	The 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems - Kitakyushu, Japan Duration: 22 Sept 2020 → 25 Sept 2020 Conference number: 33 https://jsasaki3.wixsite.com/ieaaie2020

Publication series

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

Conference

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

Access to Document

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

Variable Transformation to a 2x2 domain space for Edge Matching PuzzlesAccepted author manuscript, 1.09 MBLicence: Other

Cite this

Aspinall, T., Gepp, A., Harris, G., & Vanstone, B. J. (2020). Variable transformation to a 2×2 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, Proceedings: 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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12144 LNAI). Springer. https://doi.org/10.1007/978-3-030-55789-8_19

Aspinall, Thomas ; Gepp, Adrian ; Harris, Geoffrey et al. / Variable transformation to a 2×2 Domain Space for Edge Matching Puzzles. 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. editor / H. Fujita ; P. Fournier-Viger ; M. Ali ; J. Sasaki. Cham : Springer, 2020. pp. 210-221 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{9179cf6b7dab43a2b786c0f1b98e593a,

title = "Variable transformation to a 2×2 Domain Space for Edge Matching Puzzles",

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.",

author = "Thomas Aspinall and Adrian Gepp and Geoffrey Harris and Vanstone, {Bruce J}",

year = "2020",

month = sep,

doi = "10.1007/978-3-030-55789-8_19",

language = "English",

isbn = "978-3-030-55788-1",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "210--221",

editor = "H. Fujita and P. Fournier-Viger and M. Ali and J. Sasaki",

booktitle = "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",

address = "Germany",

note = "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",

url = "https://jsasaki3.wixsite.com/ieaaie2020",

}

Aspinall, T, Gepp, A, Harris, G & Vanstone, BJ 2020, Variable transformation to a 2×2 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, Proceedings: 33rd International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2020, Kitakyushu, Japan, September 22-25, 2020, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12144 LNAI, Springer, Cham, pp. 210-221, The 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems, Kitakyushu, Japan, 22/09/20. https://doi.org/10.1007/978-3-030-55789-8_19

Variable transformation to a 2×2 Domain Space for Edge Matching Puzzles. / Aspinall, Thomas; Gepp, Adrian; Harris, Geoffrey et al.
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. ed. / H. Fujita; P. Fournier-Viger; M. Ali; J. Sasaki. Cham: Springer, 2020. p. 210-221 (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 proceeding › Chapter › Research › peer-review

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 - Conference code: 33

PY - 2020/9

Y1 - 2020/9

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

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

UR - http://www.scopus.com/inward/record.url?scp=85091303168&partnerID=8YFLogxK

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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

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 - Cham

T2 - The 33th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems

Y2 - 22 September 2020 through 25 September 2020

ER -

Aspinall T, Gepp A, Harris G, Vanstone BJ. Variable transformation to a 2×2 Domain Space for Edge Matching Puzzles. In Fujita H, Fournier-Viger P, Ali M, Sasaki J, editors, 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. Cham: Springer. 2020. p. 210-221. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-55789-8_19

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

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

Cite this

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Related Research Outputs

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

Cite this