# Needs alternative algorithm for a graph problem

There is a network of connected electric bulbs each with a unique id. Each bulb has a switch. When the switch is clicked, the colour of the bulb changes and also the colours of connected bulbs change. The order in which the colour-change occurs is green-yellow-red-green. The network of bulbs is a connected graph (but not necesarily a complete graph). I want to find a way by which I can convert all bulbs to green. This could be represnted by sequence of ids of bulbs whose switches can be clicked to get the final outcome.

I tried to solve this by converting the problem to a graph. Each node of the graph representing a state of the network so that two states are different if there is at least one unique bulb which has different colour in those two states. Then by using Dijkstra's shortest path algorithm I tried to find a path to the final state where all bulbs have green colour. (Although in my problem I don't need a shortest path. But this is also one valid solution.) This worked fine for small networks (number of nodes less than 12). But as the number of nodes increased the number of states increased so much that my program was running forever.

-
This is very similar to the well known Lights Out puzzle, except with three states instead of two. The solution method using linear algebra, described by Henning Makholm, is essentially the same for both puzzles. –  Ilmari Karonen Jul 2 '12 at 18:46
Thanks for the pointer, @Ilmari Karonen –  Balkrishna Rawool Jul 2 '12 at 21:15

If the bulbs initially have different colors, and the only possible colors are green, yellow and red, there can be at most 3 nodes in the graph. There are only 4 possible connected graphs with at most 3 nodes, do it seems to be feasible simply to consult a precomputed table of solutions for each possible instance of the problem. (Especially since the answer is always "no" for three of the four possible graphs).

On the other hand, if some of the bulbs are allowed to have the same color initially, then the problem becomes more interesting. The key to improving your search algorithm is to notice that the order in which the buttons are pressed does not matter; the final state of each bulb depends only on its initial color and the number of times some button connected to it was pressed.

Given this (and the lucky coincidence that the number of colors in the cycle is prime), the simplest way to approach the problem is linear algebra: Represent each color an element of $\mathbb F_3$ (the field of integers modulo 3), and a state of the entire network as a vector with entries in $\mathbb F_3$. The actions of each button is another fixed vector (containing only 0's and 1's) that is added to the state vector, and the problem is then to find whether the difference between the initial state and the all-green state is a sum of multiples of button vectors. That is simply a system of $n$ linear equations in $n$ unknowns, where the unknowns are the number of times each button is pressed. This can be solved in $O(n^3)$ time using standard techniques such as Gaussian elimination.

-
I just read first line of your answer and realized my mistake in the problem. I shouldn't have said "Initially all the bulbs have different colours." In fact what I meant to say was "Not all the bulbs have same colour initially". I have removed the misleading sentence from the problem statement. Now that I read your answer further, I see that you have explained the situation I desired as well. Thanks for the explanation and pointer to Gaussian Elimination Technique. –  Balkrishna Rawool Jul 2 '12 at 18:37
I understood your answer except the sentence: "That is simply a system of $n$ linear equations in $n$ unknowns." I get the part that it has $n$ unknowns, but I can't figure out how there are $n$ equations. I can see only one. Currently I am adding another fact that "these unknwons can only be 0, 1 or 2 because pressing a button n times will have the same effect as pressing it n mod 3 times" to the program. This will make my work a lot simpler. –  Balkrishna Rawool Jul 2 '12 at 19:32
@Balkrishna: There is one equation for the final state of each bulb, looking something like $2+x_4+x_5+x_7+x_{13}=0$ for an initially red bulb that is influenced by buttons number 2, 5, 7 and 13. All of these equations together can also be thought of as a single vector equation, but the tradition when speaking about the size of such linear equation systems is to break the equation into scalar equations for each coordinate and count those instead. –  Henning Makholm Jul 2 '12 at 20:37
Also note that "the unknowns can only be 0, 1 or 2" is implicit in considering the entire equation system to live in modulus 3. This is important because Gaussian elimination asks you to divide by various nonzero elements at various points in the procedure. Then, however, every multiple of 3 counts as being "zero", everything that is 1 mod 3 counts as being "one", and everything that is 2 mod 3 counts as being "minus one". In particular, if you find yourself needing to divide by 2, just multiply by 2 instead because $2\times 2\equiv 1\pmod 3$. –  Henning Makholm Jul 2 '12 at 20:41
oh! I see it now. Thanks for the explanation @Henning Makholm. –  Balkrishna Rawool Jul 2 '12 at 20:55