点亮

点亮（日语：美術館／びじゅつかん^{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]