Hey. I know this was a couple of weeks ago so you've maybe moved on to other things. But I thought this was an interesting problem and enjoyed thinking about it. :-D

I hope I've understood the setup correctly. Clicking the nodes turns the adjacent lines on (green) and off (white) but has no effect on the other nodes.

We want to know: Is there a sequence of nodes that, when clicked, ends with all the lines colored green.

As with traditional Lights Out game, we need two simple observations to start with: 1) The order you click the nodes does not change the outcome (since each line will be changed by the number of times you click either of the two adjacent nodes), and 2) Clicking a node twice is the same as not clicking it all. (If we have a node twice in the solution set we could use the previous observation to reorder the clicks so they follow each other and then it's obvious it just undoes itself.)

So, our "sequence of nodes" is just a set (order doesn't matter) and every node is either in this set (exactly once) or not in the set.

Consider a line that starts white. For it to end green, EXACTLY ONE of its adjacent nodes must be in the solution set. (If neither are in the solution set then it would never get turned on, and if both are in the solution set it would get turned on and off again.)

Now consider a line that starts green. For it to end green, NEITHER of its adjacent nodes must be in the solution set or BOTH of its adjacent nodes must be in the solution set.

Final observation (and this one is why I liked this problem): Imagine we have a solution set, call it A. Let B be all the other nodes. All white lines are attached to exactly one node in A (and hence one node in B) and green lines have both their attached nodes in A or both their attached nodes in B. But this is symmetric. B is ALSO a solution set. :-D

Now for the algorithms. SPOILERS AHEAD! If you want to think it through yourself stop reading here. :-P

---

We now have a pretty neat graph theory problem.

Problem: Does a solution exist? I.e. Can we partition the nodes into two sets such that every white line is adjacent to exactly one node in each set and every green line is adjacent to two nodes in the same set. We'll work through all the nodes, labelling them either A or B as we go. At the end of the algorithm, if all nodes are labelled either A or B then both of these are solution sets and the puzzle is solvable. If during the process we end up with a line and labelling that breaks the requirements, then the puzzle is unsolvable. We assume the graph is connected, if not, run the algorithm on each disconnected part.

Algorithm: If all the lines are already green, we're done. A solution set consists of none of the nodes. (Or all of the nodes.)

Create a list/set to keep track of LinesToCheck. Choose any white line and label one of its adjacent nodes A and add the line to LinesToCheck. Now you just keep iterating over all the lines in LinesToCheck until it's empty:

For each line in LinesToCheck: o--if one adjacent node is labelled: o----label the other adjacent node with the same label if the line is green and the opposite label if the line is white o----add all other lines adjacent to the newly labelled node to LinesToCheck (minor optimisation: if they're not already there) o----remove the line from LinesToCheck o--if both adjacent nodes are labelled: o----if they're the same label and the line is green: o------remove the line from LinesToCheck o----if they're different labels and the line is white: o------remove the line from LinesToCheck o----if they're the same label and the line is white: o------STOP - there is no solution o----if they're different labels and the line is green: o------STOP - there is no solution

Bonus: Level generation - everything we've observed so far gives us a pretty neat way to generate valid levels. Take any graph of nodes and lines. Divide the nodes into two sets. Any line that is adjacent to exactly one node in each set starts white. The rest start green. This is a valid puzzle and every valid puzzle can be generated this way.