點燈遊戲，又名all-ones problem，最早是由Sutner於1988年提出的論文中所定義的名詞。這個問題假設有一個N×M大小的棋盤狀盤面，一開始是全暗，當我們點其中一格燈泡時，與它上、下、左、右相鄰的鄰居包含自己的狀態會由亮變暗或是由暗變亮，這條規則稱為σ+-rule。此遊戲的目標是找出一組點燈法則使得整個盤面上每一格子都變成全亮。
本論文將先前陳昱璇的論文所提出的縮小線性系統之演算法與陳昶安同學所提出拼圖法之理論作一種結合，使得收集拼圖法所需的基本盤面解能更加快速。成果方面，針對N×M的盤面，N與M為整數，從原本拼圖法N 20且M 1已得到解提升到N 63且M 1都已破解。此外亦證明每個N值都存在一種尺寸為N×P的盤面，任意輸入一組第一列的組合，經過延展到第P列，都能獲得此尺寸為N×P的盤面解。

The lamp lighting game, also known as all-ones problem, was first proposed in 1988 by Sutner. The problem can be described as follows: suppose that there is an N×M chessboard, each square represents a light bulb. When we press on one square, the status of each of its non-diagonal adjacent squares including itself will be changed from lit to unlit or from unlit to lit. This rule is called the σ+-rule. Initially all squares are in unlit status. The goal is to identify a set of squares that need to be pressed in order to turn all lights on.
In this thesis, we combine the reduced linear system proposed by Yu-Xuan Chen and the patching method proposed by Chang-An Chen to reduce the solving time substantially. Then we are able to find all solutions for the chessboards with a size N×M, 1 ≤ N ≤ 63 and 1 ≤ M. We also proved that, for each value of N, there exists a value P such that whatever value we fill in the first row, there will always have a solution for the chessboard with a size N×P.

1. 陳昶安、林順喜，“欄數少於20之點燈遊戲更快速的電腦解法之研究”，師大資工系大四專題研究報告，2009。
2. 蔡明原、林順喜，“一個有趣的益智遊戲「點燈」之電腦解法及分析”，中華民國資訊學會通訊，第一卷第四期，7-13頁，1988。
3. 陳昱璇，“全一問題的改良演算法研究”，國立台灣師大資工所碩士論文，1997。
4. W. Y. C. Chen, X. Li, C. Wang and X. Zhang, “Linear time algorithms to the minimum all-ones problem for unicyclic and bicyclic graphs”, Electronic Notes in Discrete Mathematics, Vol.17, pp.93-98, 2004.
5. J. Goldwasser, W. F. Klostermeyer, and H. Ware, “Fibonacci polynomials and parity domination in grid graphs”, Graphs and Combinatorics, Vol.18, pp.271-283, 2002.
6. O. P. Lossers, “Solution to problem 10197”, American Mathematical Monthly, Vol.100-8, pp.806-807, 1993.
7. K. Sutner, “Problem 88-8”, The Mathematical Intelligencer, Vol.10-3, 1988。
8. K. Sutner, “Linear cellular automata and the garden-of-eden”, The Mathematical Intelligencer, Vol.11-2, pp.49-53, 1989.
9. Jaap’s Puzzle Page,
http://www.geocities.com/jaapsch/puzzles/lights.htm.