TY - JOUR
T1 - Puzzle and Dragons is hard
AU - Guo, Jun Yi
AU - Yu, Po Chun
N1 - Publisher Copyright:
© 2024 Elsevier B.V.
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 - http://www.scopus.com/inward/record.url?scp=85186696633&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85186696633&partnerID=8YFLogxK
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 -