TY - CHAP

T1 - Automatically Generating and Solving Eternity II Style Puzzles

AU - Harris, Geoffrey

AU - Vanstone, Bruce J

AU - Gepp, Adrian

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

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

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

ER -