全一問題(All-Ones Problem)是由Klaus Sutner於1988年提出。這個問題假設有一個n×m大小的棋盤狀盤面，當我們點其中一格”燈泡”時，與它上、下、左、右相鄰的鄰居包含自己的狀態會由亮變暗或是由暗變亮，而最終目標是找出一組點燈法則使得整個盤面由全亮變成全暗。提出這個問題的Sutner於1989年利用Cellular Automata證明了任意n×m的盤面都必存在至少一組解法，進而提出了最小全一問題(Minimum All-Ones Problem)並証明其為一NP-Complete問題。另外Lossers也利用線性代數證明了任意大小盤面都有解的事實，其解法的時間複雜度甚高，為Ο(n3×m3)。本校蔡明原學長與林順喜教授提出了一種搜尋演算法能夠有效率的找出較小盤面的解法，並已找出20×20以下所有盤面的解答。本論文中將提出一種更有效率的演算法能夠更快速的找出任意大小盤面的解法，只需Ο(n×m+n3)的時間即可找出一組解答。

[1] 蔡明原、林順喜, 一個有趣的益智遊戲「點燈」之電腦解法及分析, 中華民國資訊學會通訊, 第一卷第四期, 頁7-13, 1998

[2] 許介彥, 巴斯卡三角形的幾個性質, 科學教育, 275期, 頁20-28, 2004

[3] D. W. Bolton, “The multinomial theorem”, The Mathematical Gazette, Vol.52-382, pp.336-342, 1968

[4] F. Galvin, “Solution to problem 88-8”, The Mathematical Intelligencer, Vol.11-2, pp.31-32, 1989

[5] G.. Kallos, “A generalization of Pascal's triangle using powers of base numbers”, Annales Mathematiques Blaise Pascal, Vol.13, pp.681-682, 2006

[6] H. Eriksson, K. Eriksson and J. Sjostrand, “Note on the lamp lighting problem”, Advances in Applied Mathematics, Vol.27, pp.357-366, 2001

[7] H. Zeitier, “Trinomial formula, Pascal and Sierpinski pyramid”, International Journal of Mathematical Education in Science and Technology, Vol.33- 2, pp.256-266, 2002

[8] J. F. Putz, “The Pascal polytope: an extension of Pascal's triangle to N-dimensions”, The College Mathematics Journal, Vol.17-2, pp.144-155, 1986

[9] J. Goldwasser, W. F. Klostermeyer, and G. E. Trapp, “Characterizing switch-setting problems”, Linear and Multilinear Algebra, Vol.43, pp.121-135, 1997

[10] 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

[11] J. Goldwasser and W. F. Klostermeyer, “Maximization versions of Lights Out games in grids and graphs”, Congressus Numerantium, Vol.126, pp.99-111, 2002

[12] K. Sutner, “Problem 88-8“, The Mathematical Intelligencer, Vol.10-3, 1988

[13] K. Sutner, “Linear cellular automata and the garden-of-eden”, The Mathematical Intelligencer, Vol.11-2, pp.49-53, 1989

[14] K. Sutner, “σ-Automata and Chebyshev-polynomials”, The Oretical Computer Science, Vol.230, pp.49-73, 2000

[15] M. Anderson and T. Feil, “Turning Lights Out with linear algebra”, Mathematics Magazine, Vol. 71-4, pp.300-303, 1998

[16] O. P. Lossers, “Solution to problem 10197”, American Mathematical Monthly, Vol.100-8, pp.806-807, 1993

[17] O. Martin-Sanchez and C. Pareja-Flores, “Two reflected analyses of Lights Out”, Mathematics Magazine, Vol.74, pp.295-304, 2001

[18] R. Cowen, S. H. Hechler, J. W. Kennedy, and A. Ryba, “Inversion and neighborhood inversion in graphs”, Graph Theory Notes of New York, Vol.37, pp.38-42, 1999

[19] R. L. Keeney and J. F. Ramaley, “On the trinomial coefficients”, Mathematics Magazine, Vol. 42-4, pp.210-213, 1969

[20] 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

[21] Y. Caro, “Simple proofs to three parity theorems”, Ars Combinatoria, Vol.42, pp.175-180, 1996

[22] Jaap’s Puzzle Page
http://www.geocities.com/jaapsch/puzzles/lights.htm