IntroductionDecoding the GameFinding a SolutionWorks CitedIntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 1 of 11Go BackFull ScreenCloseQuitLights OutReed WillistonNoah Flemens12/17/2010IntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 1 of 11Go BackFull ScreenCloseQuitAbstractThe game Lights Out is played on a 5 × 5 grid. This set up makes it easy tomodel the game using vectors and matricies. In this paper we will discuss how tomodel and manipulate the game using linear algebra. We will discuss how to determinewhether or not a given configuration can be solved and how to find the solution tothat configuration. This paper contains all the tools necessary to analyze and solve thegame of Lights Out.IntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 1 of 11Go BackFull ScreenCloseQuitIntroductionLights out is an electronic game consisting of a 5 × 5 array of nodes. A node is repre-sented by a button that toggles a light on and off with each press. Each node can bein one of two states at a given time. In the first state the node is lit, signifying it ison. When the node is unlit, it is considered to be in the second state: off. A typicalconfiguration of a Lights Out game is represented by Figure 1. When a node is pressed,its state and the state of all nodes adjacent to the node that has been pressed, arechanged to their opposite state. This can be seen in Figures 2 , 3 and 4. This effect isstrictly limited to the touching squares. That is to say, there isn’t a wrap around effectwhen a node is pressed. There are versions of the game that are played on a toroid, soactivating a node in the top right corner of the board will also activate the nodes in thebottom right and top left corners of the board. The game that we will be analyzing isone that uses the standard set of rules that does not allow the wrap around effect.The game begins with some configuration of the 25 nodes in each state. In orderfor a game to be solved, all of the nodes must be switched to the off state. Not allconfigurations are solvable. However, the game only uses solvable configurations forIntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 2 of 11Go BackFull ScreenCloseQuitFigure 1: Orange squares are in the on state whereas grey squares are in the off state.Figure 2: Pressing a corner button toggles adjacent cells.IntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 3 of 11Go BackFull ScreenCloseQuitFigure 3: Pressing an edge button toggles adjacent cells.Figure 4: Pressing an interior button toggles adjacent cells.IntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 4 of 11Go BackFull ScreenCloseQuitthe sake of practicality. This paper will explore what constitutes a solvable array ofnodes and what makes particular combinations of nodes unsolvable.Decoding the GameThere are two observations that can be made about finding a solution to a game. Thefirst observation is that a node need only be toggled once during the course of a game.Toggling a node once changes its state, pressing it again places the node in its initialstate. Toggling a node a third time is the same as toggling it once. Thus, toggling anode an even number of times is equivalent to no change in state. While activating astate change an odd number of times is the same as if the node has been changed once.This fact, and the fact that there are only two possible states a node can be in meansthat all of the calculations we make must be in modulo two. The second observationis that the order in which the nodes are activated does not result in a unique outcome.This is because the adjacent nodes are going to be toggled an equal number of timesregardless of the order in which each node experiences a change in state. These twoobservations are key to the way in which linear algebra is used to find a solution to agiven configuration of node states.To describe the game, we will use the notation bijto indicate the position of a nodein the ith row and jth column. This can be seen in Figure 5 and the correspondingmatrix is below.b11b12b13b14b15b21b22b23b24b25b31b32b33b34b35b41b42b43b44b45b51b52b53b54b55An element of this matrix is 1 if the corresponding node is on and 0 if the node isIntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 5 of 11Go BackFull ScreenCloseQuitb11b12b13b14b15b21b22b23b24b25b31b32b33b34b35b41b42b43b44b45b51b52b53b54b55b11b12b13b14b15Figure 5: Each cell contains its name as it is represented in the vector b.off. By arranging these entries into a 25 × 1 column vector by stripping off each of therow of this matrix, the configuration can be denoted by:b = (b11, b12, b13· · · b21, b22· · · b55)TNow that we have our configuration vector b we will begin developing the notion ofa vector that represents a strategy for solving this given configuration. We’ll call thisvector x, where x is a 25 × 1 column vector. We use the same notation as in Figure 5.It is an important point to note that a solution x will solve a given configuration, andwill also create that configuration from a solved state.x = (x11, x12, x13· · · x21, x22· · · x55)TAn element xijis 1 if the corresponding node bijneeds to be activated to effectivelysolve the configuration. An element is 0 if the corresponding node need not be activatedIntroductionWorks CitedHome PageTitle PageJJ IIJ IPage 6 of 11Go BackFull ScreenCloseQuitto solve the configuration. To see how a node is effected during game play, the adjacentnodes have to be taken into consideration. So the node b11is effected by the strategyelements x11, x12, and x21. Take note that these calculations are done in modulo two.For each time an adjacent node is pressed, b11changes state. So if x11= 1, signifyingthat it has been pressed, then b11is toggled on. However, if x12is pressed as well, thenthe sum of x11and x12is two, which in modulo two is equal to zero. So these twomoves do not change the state of b11. It follows that the state of b11is the sum of thepresses on the adjacent nodes: x11, x12, and x21.b11= x11+ x12+ x21Similarly, b12is effected by the strategy elements x11, x12, x13, and x22. Its state is thesum of the presses of these adjacent nodes. For example, if we toggle the nodes x12,x13, and x22, their sum will be three which is one in modulo two. Thus, b12will betoggled. So the equation pertaining to the state of b12will be:b12= x11+ x12+ x13+ x22The equations for the rest of the nodes follow from the previous examples. These arethe