Candy Crush is NP-hard

2014/03/08 by Toby Walsh, Walsh, Toby · 2 voices · 5 citations
Computer Science · Economics, Econometrics and Finance · #Algorithms and Data Compression #Artificial Intelligence in Games #Computational Complexity (cs.CC) #F.2.0 #FOS: Computer and information sciences #Sports Analytics and Performance #cs.CC

paper · pdf · doi:10.48550/arxiv.1403.1911

arxiv created 2014/03/08 · openalex publication_date 2014/03/08 · arxiv published 2014/03/08 · arxiv updated 2014/03/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that playing Candy Crush to achieve a given score in a fixed number of swaps is NP-hard.

Cited by

• TrackMania is NP-complete
• On A Generalization of "Eight Blocks to Madness"
• The Computational Complexity of Portal and Other 3D Video Games
• The Computational Complexity of Fire Emblem Series and similar Tactical Role-Playing Games
• Complexity of n-Queens Completion

Discussions

• Candy Crush is NP-hard [hn, 2 points, 1 comments]
• Candy crush is NP-Hard [hn, 1 points, 0 comments]

Related

• Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard
• NP-Hardness of a 2D, a 2.5D, and a 3D Puzzle Game
• Misere Hackenbush is NP-Hard
• Bust-a-Move/Puzzle Bobble is NP-Complete
• Candy-passing Games on General Graphs, II