The SIGMA and SIGMA+ Games

We begin by choosing a directed graph, call it G, and we let the vertices of G take two different states (0 and 1 say). A configuration is an assignment of states to all the vertices. A move in the game consists of choosing a particular vertex in G. When a vertex v is chosen, the states of all the vertices u which are adjacent to v in G (i.e. all vertices u which are such that there is an arrow from v to u) are toggled. The aim of the game is to make a series of moves that transform the graph from an original configuration S (often chosen randomly) to a target configuration T (in Lights Out T is the configuration which is such that all vertices are in state 0).

The SIGMA+ game is defined similarly to the SIGMA game, except that in this case, choosing a vertex v also toggles the state of v.

We can now illustrate this by considering Lights Out. The graph shown on the left is the graph we would use for a game of Lights Out played on a 3x3 grid, with the vertices corresponding to the buttons. Each button can be in one of two states (on or off). The starting configuration S is randomly chosen by the machine. A move consists of choosing a button and pressing it. This then toggles the state of all the buttons which are vertical and horizontal neighbours of that button (as well as of the button itself). The aim of the game is to make a series of moves which eventually turns all the lights out - i.e. to move from S to T where T is the "all-zeroes" configuration.

Now in the graph we have here, we can see that each vertex is connected by an arrow to all of its horizontal and vertical neighbours, and not to any others. Therefore we can see that 3x3 Lights Out simulates the SIGMA+ game on this graph.

Many of the Lights Out variants differ only from Lights Out by playing the SIGMA+ game on a different graph. This includes Lights Out Cube, Torus Lights Out, Orbix (well, some of the Orbix puzzles at any rate) and Merlin's Magic Square. The graphs for most of these games are much less pleasant to draw (and not particularly enlightening anyway), however the graph for Merlin's Magic Square is quite nice and so is shown below.

Not all of the Lights Out variants that we list here can be described in this way. However, there is usually a SIGMA or SIGMA+ game (or at least a minor variation) lurking underneath somewhere, and this is what gives all of these games the Lights Out "feel".

Of course it almost goes without saying that if there is any mathematical analysis of the SIGMA+ game that we can do in general, it will apply to any of the simple Lights Out variants. There will be some pages up about this soon!!!