Light Up遊戲一致性問題之研究

Abstract

Light Up（點燈遊戲）是一個從日本發跡並已推廣至世界各地，造成相當流行的一種“paper-and-pencil puzzles”類型的遊戲，在2005年時由Brandon McPhail證明了Light Up一致性問題 -- 「給定一個Light Up的盤面，判定此盤面是否存在合理的解？」的難度是NP-complete。目前探討本議題的相關論文並不多，因此在本論文中，首先提出了將盤面縮小至一維的盤面，並發現一維的Light Up盤面能夠在線性時間內以一個決定性的有限狀態機（DFA）判斷出盤面是否一致，即1×n Light Up一致性問題複雜度為P。

接著我們將Light Up盤面限定為一個2×n的盤面，即一個二維的盤面但其中一個維度限制為2，發現這個問題同樣地能被克服。我們設計了一個有限狀態機，同樣能在線性時間內判斷出一個2×n Light Up盤面是否一致，即2×n Light Up一致性問題複雜度亦為P。