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。

Description

Keywords

Light Up, 一致性問題

Citation

Collections