點亮

由Nikoli出版的邏輯謎題

點亮(日語:美術館びじゅつかん Bijutsukan */?、明かり,英語:Light Up),又稱作數燈點燈遊戲,是由Nikoli英語Nikoli (publisher)出版的二進制邏輯益智遊戲。首次出現於解謎刊物《謎題通訊Nikoli日語パズル通信ニコリ》2001年第95期的〈製作有趣解謎遊戲〉(『オモロパズルのできるまで』)單元,並從第102期開始定期發布[1]

中等難度的點亮謎題(解答

遊戲規則

 
初等難度的點亮謎題(解答

在由白色與黑色格子組成的矩形網格上進行遊戲。玩家將燈泡(用圓圈標記)填入白格中,確保兩個燈泡不會相互照射,直到整個網格都被點亮(每個謎題皆為唯一解)。燈泡只會往水平與垂直方向發射光線,照亮整個行和列,除非它的光線被黑格擋住。黑格上可能有從0到4的數字,表示與其四條邊鄰接的白格共有若干個燈泡。[1]

例如:帶有4的黑格周圍必須有四個燈泡,表示每側一個。帶有0的黑格的任一側都不能有燈泡。一個未編號的黑格可能有任意數量的燈泡與之相鄰,或者沒有。與有編號的黑格對角相鄰放置的燈泡不影響燈泡計數。

複雜度

可以將電路可滿足性問題英語Circuit satisfiability problem多項式時間歸約到點亮謎題。由於電路可滿足性問題已知為NP完全,這可用來證明點亮謎題的可解性問題亦為NP完全[2]。也可考慮僅得某一個特定數字(0、1、2、3、4之一)的黑格和空黑格的特殊情況。若只有數字n和空黑格,則該變體稱為點亮-n(Akari-n)。同樣,通過從電路可滿足性問題的多項式時間歸約可以證明點亮-1、點亮-2及點亮-3為NP完全,而點亮-4與沒有任何數字的變體謎題則為P,點亮-0截至2020年末尚未分類[3]

電腦遊戲

Hudson Soft於2007年3月8日以任天堂DS益智遊戲系列日語パズルシリーズ》Vol.12〈美術館〉發布[4]。2011年6月2日,點亮益智遊戲(即〈美術館〉)被收錄在該公司發布的《數獨+3 ~nikoli 益智集錦~》中[5]

參考文獻

  1. ^ 1.0 1.1 「美術館(Akari)」のニコリ公式パズルガイド - WEBニコリ. [2021-07-06]. 原始內容存檔於2015-03-18. 
  2. ^ McPhail, Brandon. Light Up is NP-complete (PDF). 2005-02-28 [2021-07-06]. (原始內容存檔 (PDF)於2022-02-08). 
  3. ^ Pulles, Bram. Analysis of Akari (PDF). 2021-01-09 [2021-05-27]. (原始內容存檔 (PDF)於2022-01-24). 
  4. ^ Puzzle Series Vol.12 Museum. [2021-07-06]. 原始內容存檔於2007-05-21. 
  5. ^ 数独と3つのパズル ~ニコリのパズルバラエティ~. [2021-07-06]. (原始內容存檔於2022-05-06). 

外部連結