主講人：郭君逸 博士(國立臺灣師範大學數學系)

題  目：神魔之塔好難Tower of Saviors is (Computationally) Hard

日  期：114年9月30日（星期二）

時  間：下午14:00 ~ 15:00

地  點：科學館S433

摘要Abstract:

Candy Crush Saga是一款非常受歡迎的遊戲，在2012年發佈後，隔了三年，在2014年被證明屬於NP-完備。15-拼圖(或稱華容道)也是經典的滑塊遊戲，也同樣被證明為NP-完備。將這兩款遊戲結合，即誕生了龍族拼圖這款在2014發佈的遊戲。後來神魔之塔的誕生，把此類遊戲發揚光大。在神魔之塔中，玩家滑動某一顆珠子(滑塊)，滑動的軌跡會將珠子重新排列，離手時，有大於等於三個珠子相連成一線就會像Candy Crush Saga一樣消除，剩下的珠子會依重力落下。此論文中，改善了過去用2/2/4-SAT證明華容道為NP-困難的方法，並利用1-in-3-positive SAT證明了神魔之塔為NP-完備。

Candy Crush Saga is a popular game, released in 2012, and three years later, in 2014, it was proven to be NP-complete. The 15-puzzle is another classic sliding block game, which has also been shown to be NP-complete. By combining these two games, Puzzle & Dragons was released in 2014. Subsequently, the emergence of Tower of Saviors further popularized this genre. In Tower of Saviors, the player slides a particular orb (or block), and the trajectory of the slide rearranges the orbs. When the player releases the orb, if three or more orbs are aligned in a straight line, they disappear just like in Candy Crush Saga, and the remaining orbs fall. In this paper, we improve previous methods that used 2/2/4-SAT to prove the NP-hardness of the sliding puzzle, and instead utilize 1-in-3-positive SAT to prove that Tower of Saviors is NP-complete.

備  註：本業務與聯合國永續發展目標SDG4優質教育連結

ESG+AI=∞  AI+SDGs=∞