點亮

點亮（日语：美術館／びじゅつかん^{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.0 ^1.1 「美術館(Akari)」のニコリ公式パズルガイド - WEBニコリ. [2021-07-06]. 原始内容存档于2015-03-18.
^ McPhail, Brandon. Light Up is NP-complete (PDF). 2005-02-28 [2021-07-06]. （原始内容存档 (PDF)于2022-02-08）.
^ Pulles, Bram. Analysis of Akari (PDF). 2021-01-09 [2021-05-27]. （原始内容存档 (PDF)于2022-01-24）.
^ Puzzle Series Vol.12 Museum. [2021-07-06]. 原始内容存档于2007-05-21.
^ 数独と3つのパズル～ニコリのパズルバラエティ～. [2021-07-06]. （原始内容存档于2022-05-06）.

外部連結

Light Up, from Simon Tatham's Portable Puzzle Collection （页面存档备份，存于互联网档案馆）
Nikoli's English page on Light Up （页面存档备份，存于互联网档案馆）
Grilles d'akari （页面存档备份，存于互联网档案馆）
nikoli.comの美術館のおためし問題，存于互联网档案馆
ハドソンのDS用ソフト公式ページ，存于互联网档案馆

[nikoli-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）.

[1]

[2]

[3]

[4]

[5]