Please use this identifier to cite or link to this item:
Reducing the Solving Time of the Patching Method for All-Ones Problem
reduced linear system
lamp lighting problem
本論文將先前陳昱璇的論文所提出的縮小線性系統之演算法與陳昶安同學所提出拼圖法之理論作一種結合，使得收集拼圖法所需的基本盤面解能更加快速。成果方面，針對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.
|Appears in Collections:||學位論文|
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.