提升點燈遊戲之拼圖法搜尋速度

Abstract

點燈遊戲，又名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.