First up apologies if this is the wrong board to post on, there are too many stack exchanges :P This problem comes in 5 parts, the only required part is part 1 but there are plenty of internet cookies available for those that attempt other parts. The extra parts can be done in any order.
Setup:
The rules are simple, you have a graph with n nodes and e edges connecting the nodes together. There wont be any duplicate edges. Each node has a binary state of true or false and each node may start in either state. The aim is to get all nodes set to true however each time you flip the state of a node it also flips any connected nodes. A flip constitutes a move and you may take as many moves as you would like.
Example:
Green is true and red is false
Starting state: View Example 1
This puzzle could be solved in 1 move by flipping the node in the top right.
However for the sake of this example lets say I’m really bad at this puzzle and chose to flip the top left node, it would also flip the top right node and the bottom node:
View Example 2
This puzzle was solvable in just 1 move.
Example 2:
It is however possible to construct a puzzle that is impossible, take the puzzle below as an example. It doesn’t matter how many flips you do as there are only 2 possible states and neither result in the success state.
Example 3 has to be directly linked as I can't post more than 2 links:
i.stack.imgur.com/Es61y.png
Problem 1:
I am looking for an algorithm/equation to determine whether a given graph is possible, just a true or false, that’s it.
Problem 2:
Once you know it’s possible I would line to know the minimum number moves required for the solution.
Problem 3:
If you impose a limit on how many times you may flip a node can you come up with updated solutions to parts 1 and 2
Problem 4:
Similar to part 3, how does your solution change when you can have directional edges that only pass a flip along in a certain direction,
Finally Problem 5:
What are the moves required to solve the puzzle
Conclusion:
I should clarify that I have no idea if the problems above are solvable. They seem like they should be but it’s been too long since I have done graph theory and I don’t have the time to redo the syllabus.
Best of luck to those who give it a go and happy problem solving.
I have a solution for parts 1, 2, 3 and 5. It's not too bad once you get your head around it but would take a lot for me to explain, more than this post can take, and I'm not entirely confident on how it works so think it's just best if you read this.
There is also an applet to show you his solution works, available here
Hopefully the link stays up.
Part 3 is solvable by using the answer to part 5 and simply checking if a node that isn't flippable needs a flip. If you extend the game to have more than 2 states per node then you can do a similar trick with larger limits.
Part 4 is still an open question so I will still be excepting answers (despite how this thread seems dead)