龍族拼圖是艱難的遊戲

Abstract

Candy Crush Saga 是一款非常受歡迎的遊戲,在 2012 年發布後,隔了三年,在2014 年被證明屬於 NP-完備。華容道(又稱 15-拼圖)是經典的滑塊遊戲,也同樣被證明為 NP-完備。將這兩款遊戲結合,即誕生了龍族拼圖這款在 2014 發佈的遊戲。在龍族拼圖中,玩家像華容道一樣滑動起手珠,滑動的軌跡會將珠子重新排列,離手時,有大於等於三個珠子相連成一線就會消掉,就像 Candy Crush Saga 一樣。消除珠子的組數越多,得到的分數越多。這篇論文中,改善了過去用 2/2/4-SAT 證明華容道為NP-困難的方法,並提供了一個完成至少一組三消的多項式演算法。最後,我們提供了一個,在限制條件下,龍族拼圖為 NP-完備的證明,而我們利用的是 1-in-3-positive-SAT。

Candy Crush Saga is a famous game since it was published in 2012, and it has been shown NP-Complete in 2014. The 15-puzzle is a classic reconfiguration puzzle that has been shown NP-Complete, too. By combing these two puzzles, Puzzle and Dragons(PAD) was born in 2014. In PAD, you can slide the stone and switch the position you pass through like 15-puzzle, and dissolve the stones by match-three like Candy Crush Saga. The more three-matches you make, the more points you get. We provide a way to find the shortest path to make at least one three-match in polynomial time. Also, we try to modify the proof of Hardness of (n2 − 1)-puzzle by simplifying the reduction from 2/2/4-SAT problem. Moreover, We provide a way to show that PAD is NP-Complete by reduction from the 1 in 3 positive Boolean satisfiability problem.