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.