lights out游戏（Lights Off，让你的智慧点亮暗淡的灯光）

Lights Off，让你的智慧点亮暗淡的灯光

作为一个益智游戏的代表，Lights Out游戏已然在数代人中流行爆火。它简单却又不失趣味，在数以万计的游戏中脱颖而出。这篇文章，将为您介绍这个成名已久的益智游戏。

1. 游戏规则

Lights Out游戏是一个由一个一个独立的灯泡组成的游戏板。每个灯泡都有两个状态：开和关。玩家需要在一个规定时间内，通过按下灯泡来使得整个游戏板中的所有灯泡均为关闭状态，获得游戏胜利。但按下一个灯泡后，所影响的仅是该灯泡周围的四个方向上的相邻灯泡，这些被按下的灯泡将会翻转它们用来表示状态的属性。在游戏的初期状态，不同的游戏板中灯泡的开关状态是随机分布的。

2. 游戏的源头

Lights Out游戏是由美国的mathematician E. Berlekamp, J.H. Conway et R.K. Guy于1970年在加利福尼亚大学伯克利分校发明的，当时基于手工印刷的游戏板，是一个非常有趣的玩具。比起计算机硬能拓展的纸质算盘，它拥有了公开可见的算法和强的可用性。时至今日，可以在各种各样的平台上玩这个游戏。实际上，在Windows 3.1的计算器小程序，以及Windows Vista系统的游戏集都包含了这个经典的游戏。

3. 游戏的算法

Lights Out是一个NP难问题，所以没有暴力的解决方法。深度优先搜索不可取，因为状态数个数随着灯数增多是O(2n^2)级别的，很容易无法寻找到解。BFS(广度优先搜索)也行不通，空间和时间复杂度都是O(2n^2)，因此效率也很低。但是如果使用矩阵表示状态，最终的转换阵很容易计算，转化为一个异或方程组求解问题，可以在O(n^3)的时间复杂度内求解。细节详见算法分析。

因此，lights out不是一个能够完全的依靠官方题解来解决的难题。

总之，Lights out游戏通过它的算法和理论功力、代表了经典的组合数学问题的难度和创造性。相信这个游戏将会继续在未来的某个时刻完成一个新的神奇的转变。