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^*

^*此作品的通信作者

數學系

研究成果: 雜誌貢獻 › 期刊論文 › 同行評審

1 引文斯高帕斯（Scopus）

摘要

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.

原文	英語
文章編號	114477
期刊	Theoretical Computer Science
卷	994
DOIs	https://doi.org/10.1016/j.tcs.2024.114477
出版狀態	已發佈 - 2024 5月

ASJC Scopus subject areas

理論電腦科學
一般電腦科學

存取文件

10.1016/j.tcs.2024.114477

其它文件與鏈接

Link to publication in Scopus

引用此

@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

摘要

ASJC Scopus subject areas

存取文件

其它文件與鏈接

指紋

引用此