Automatically Generating and Solving Eternity II Style Puzzles

Geoffrey Harris; Bruce J Vanstone; Adrian Gepp

doi:10.1007/978-3-319-92058-0_60

Automatically Generating and Solving Eternity II Style Puzzles

Geoffrey Harris, Bruce J Vanstone, Adrian Gepp

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

1 Citation (Scopus)

867 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 language	English
Title of host publication	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
Editors	Malek Mouhoub, Samira Sadaoui, Otmane Ait Mahomed, Moonis Ali
Place of Publication	Cham
Publisher	Springer
Pages	626-632
Number of pages	7
ISBN (Electronic)	978-3-319-92058-0
ISBN (Print)	978-3-319-92057-3
DOIs	https://doi.org/10.1007/978-3-319-92058-0_60
Publication status	Published - 30 May 2018
Event	The 31st International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems - Montreal, Canada Duration: 25 Jun 2018 → 28 Jun 2018 Conference number: 31st http://ieaaie2018.encs.concordia.ca/

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Publisher	Springer
Volume	10868
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	The 31st International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems
Abbreviated title	IEA-AIE 2018
Country/Territory	Canada
City	Montreal
Period	25/06/18 → 28/06/18
Internet address	http://ieaaie2018.encs.concordia.ca/

Access to Document

10.1007/978-3-319-92058-0_60

Automatically Generating and Solving Eternity II Style PuzzlesAccepted author manuscript, 194 KBLicence: Other

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). Springer. https://doi.org/10.1007/978-3-319-92058-0_60

Harris, Geoffrey ; Vanstone, Bruce J ; Gepp, Adrian. / Automatically Generating and Solving Eternity II Style Puzzles. 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. editor / Malek Mouhoub ; Samira Sadaoui ; Otmane Ait Mahomed ; Moonis Ali. Cham : Springer, 2018. pp. 626-632 (Lecture Notes in Computer Science (LNCS)).

@inbook{89a36c3c7e8b479a88cb0daad9495f83,

title = "Automatically Generating and Solving Eternity II Style Puzzles",

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

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

year = "2018",

month = may,

day = "30",

doi = "10.1007/978-3-319-92058-0_60",

language = "English",

isbn = "978-3-319-92057-3",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "626--632",

editor = "Malek Mouhoub and Samira Sadaoui and {Ait Mahomed}, {Otmane } and Moonis Ali",

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

address = "Germany",

note = "The 31st International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems, IEA-AIE 2018 ; Conference date: 25-06-2018 Through 28-06-2018",

url = "http://ieaaie2018.encs.concordia.ca/",

}

Harris, G, Vanstone, BJ & 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. Lecture Notes in Computer Science (LNCS), vol. 10868, Springer, Cham, pp. 626-632, The 31st International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems, Montreal, Quebec, Canada, 25/06/18. https://doi.org/10.1007/978-3-319-92058-0_60

Automatically Generating and Solving Eternity II Style Puzzles. / Harris, Geoffrey; Vanstone, Bruce J; Gepp, Adrian.
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. ed. / Malek Mouhoub; Samira Sadaoui; Otmane Ait Mahomed; Moonis Ali. Cham: Springer, 2018. p. 626-632 (Lecture Notes in Computer Science (LNCS); Vol. 10868).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

TY - CHAP

T1 - Automatically Generating and Solving Eternity II Style Puzzles

AU - Harris, Geoffrey

AU - Vanstone, Bruce J

AU - Gepp, Adrian

N1 - Conference code: 31st

PY - 2018/5/30

Y1 - 2018/5/30

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

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

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

U2 - 10.1007/978-3-319-92058-0_60

DO - 10.1007/978-3-319-92058-0_60

M3 - Chapter

SN - 978-3-319-92057-3

T3 - Lecture Notes in Computer Science (LNCS)

SP - 626

EP - 632

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

A2 - Mouhoub, Malek

A2 - Sadaoui, Samira

A2 - Ait Mahomed, Otmane

A2 - Ali, Moonis

PB - Springer

CY - Cham

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

Y2 - 25 June 2018 through 28 June 2018

ER -

Harris G, Vanstone BJ, Gepp A. Automatically Generating and Solving Eternity II Style Puzzles. In Mouhoub M, Sadaoui S, Ait Mahomed O, Ali M, editors, 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. Cham: Springer. 2018. p. 626-632. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-3-319-92058-0_60

Automatically Generating and Solving Eternity II Style Puzzles

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

The Effect of Sentiment on Stock Price Prediction

Cite this

Automatically Generating and Solving Eternity II Style Puzzles

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Related Research Outputs

The Effect of Sentiment on Stock Price Prediction

Cite this