Puzzle and Dragons is hard

Jun Yi Guo; Po Chun Yu

doi:10.1016/j.tcs.2024.114477

Puzzle and Dragons is hard

Jun Yi Guo
, Po Chun Yu^*

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Candy Crush Saga (CCS) is a mobile game released in 2012. Based on a specific game-play, it was proven to be NP-complete in 2014. The 15-slide puzzle is also a classic game that has been proven to be NP-complete. In 2012, a brand new ball-spinning game called Puzzle and Dragons emerged. Puzzle and Dragons (PAD) combines the three-elimination game-play of Candy Crush Saga and the 15-puzzle. This study developed a construction and proved that under certain rules, PAD can be reduced to a one-in-three positive Boolean satisfiability problem (1-3-SAT⁺), which also proves that PAD is NP-Hard.

Original language	English
Article number	114477
Journal	Theoretical Computer Science
Volume	994
DOIs	https://doi.org/10.1016/j.tcs.2024.114477
Publication status	Published - 2024 May

Keywords

NP-complete
NP-hard

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2024.114477

Cite this

@article{9bf5201f8ad549f8904d8311de600aad,

title = "Puzzle and Dragons is hard",

abstract = "Candy Crush Saga (CCS) is a mobile game released in 2012. Based on a specific game-play, it was proven to be NP-complete in 2014. The 15-slide puzzle is also a classic game that has been proven to be NP-complete. In 2012, a brand new ball-spinning game called Puzzle and Dragons emerged. Puzzle and Dragons (PAD) combines the three-elimination game-play of Candy Crush Saga and the 15-puzzle. This study developed a construction and proved that under certain rules, PAD can be reduced to a one-in-three positive Boolean satisfiability problem (1-3-SAT+), which also proves that PAD is NP-Hard.",

keywords = "NP-complete, NP-hard",

author = "Guo, \{Jun Yi\} and Yu, \{Po Chun\}",

note = "Publisher Copyright: {\textcopyright} 2024 Elsevier B.V.",

year = "2024",

month = may,

doi = "10.1016/j.tcs.2024.114477",

language = "English",

volume = "994",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier BV",

}

TY - JOUR

T1 - Puzzle and Dragons is hard

AU - Guo, Jun Yi

AU - Yu, Po Chun

PY - 2024/5

Y1 - 2024/5

N2 - Candy Crush Saga (CCS) is a mobile game released in 2012. Based on a specific game-play, it was proven to be NP-complete in 2014. The 15-slide puzzle is also a classic game that has been proven to be NP-complete. In 2012, a brand new ball-spinning game called Puzzle and Dragons emerged. Puzzle and Dragons (PAD) combines the three-elimination game-play of Candy Crush Saga and the 15-puzzle. This study developed a construction and proved that under certain rules, PAD can be reduced to a one-in-three positive Boolean satisfiability problem (1-3-SAT+), which also proves that PAD is NP-Hard.

AB - Candy Crush Saga (CCS) is a mobile game released in 2012. Based on a specific game-play, it was proven to be NP-complete in 2014. The 15-slide puzzle is also a classic game that has been proven to be NP-complete. In 2012, a brand new ball-spinning game called Puzzle and Dragons emerged. Puzzle and Dragons (PAD) combines the three-elimination game-play of Candy Crush Saga and the 15-puzzle. This study developed a construction and proved that under certain rules, PAD can be reduced to a one-in-three positive Boolean satisfiability problem (1-3-SAT+), which also proves that PAD is NP-Hard.

KW - NP-complete

KW - NP-hard

UR - https://www.scopus.com/pages/publications/85186696633

UR - https://www.scopus.com/pages/publications/85186696633#tab=citedBy

U2 - 10.1016/j.tcs.2024.114477

DO - 10.1016/j.tcs.2024.114477

M3 - Article

AN - SCOPUS:85186696633

SN - 0304-3975

VL - 994

JO - Theoretical Computer Science

JF - Theoretical Computer Science

M1 - 114477

ER -

Puzzle and Dragons is hard

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this