Browsing by Author "Yu, Po-Chun"

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