Automatically Generating and Solving Eternity II Style Puzzles

Geoffrey Harris, Bruce J Vanstone, Adrian Gepp

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

120 Downloads (Pure)

Abstract

The Eternity II puzzle is an NP-complete problem. Prior researchers have generated data sets that are similar to the Eternity II problem. These data sets can be created in linear time, but this comes at the cost of easing the problem by introducing exploitable statistical features. The first contribution of this paper is a new method to generate data sets that are truly of Eternity II style. The second contribution is an Eternity II specific implementation of a constraint-satisfaction-problem style algorithm. Unlike most other published algorithms, this one has no form of look-ahead, filtering, forward checking, back jumping or k-consistency checks. Instead, it uses knowledge about the structure of the puzzle and the uniform distribution of edge colours. This approach is up to three orders of magnitude faster than previously published attempts
Original languageEnglish
Title of host publicationRecent Trends and Future Technology in Applied Intelligence - 31st International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2018, Proceedings
EditorsMalek Mouhoub, Samira Sadaoui, Otmane Ait Mahomed, Moonis Ali
Place of PublicationCham
PublisherSpringer
Pages626-632
Number of pages7
ISBN (Electronic)978-3-319-92058-0
ISBN (Print)978-3-319-92057-3
DOIs
Publication statusPublished - 30 May 2018
EventThe 31st International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems - Montreal, Canada
Duration: 25 Jun 201828 Jun 2018
Conference number: 31st
http://ieaaie2018.encs.concordia.ca/

Publication series

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

Conference

ConferenceThe 31st International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems
Abbreviated titleIEA-AIE 2018
CountryCanada
CityMontreal
Period25/06/1828/06/18
Internet address

    Fingerprint

Cite this

Harris, G., Vanstone, B. J., & Gepp, A. (2018). Automatically Generating and Solving Eternity II Style Puzzles. In M. Mouhoub, S. Sadaoui, O. Ait Mahomed, & M. Ali (Eds.), Recent Trends and Future Technology in Applied Intelligence - 31st International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2018, Proceedings (pp. 626-632). (Lecture Notes in Computer Science (LNCS); Vol. 10868). Cham: Springer. https://doi.org/10.1007/978-3-319-92058-0_60