1
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ This is called the "lights out" puzzle. It and its variants are very well studied. See pdfs.semanticscholar.org/dc08/… as a quick reference to the graph version of the problem. $\endgroup$
    – Bob Krueger
    Jun 8, 2017 at 17:39
  • $\begingroup$ "very well studied" might be an overstatement. I have seen active research on the puzzle and its variants, but it is certainly not complete enough to answer all of your questions in the general graph context. $\endgroup$
    – Bob Krueger
    Jun 8, 2017 at 17:43
  • 3
    $\begingroup$ For problem 3, there is never any advantage in flipping a node more than once as two flips returns you to where you started and the flips commute. A solution is just a list of nodes to flip. That means there are a finite number of possible solutions to try, just $2^n-1$ $\endgroup$
    – Ross Millikan
    Jun 8, 2017 at 17:52
  • $\begingroup$ @Bob1123 Ofc I come up with a puzzle that already exists -_-. I will read through that doc you linked but after having a skim it seems awfully confusing. $\endgroup$
    – Andy A
    Jun 8, 2017 at 18:24
  • $\begingroup$ @RossMillikan I was hoping for something with less brute force, and I'm not entirely sure your observation about multiple flips is true but I am yet to come up with an example that goes against this assumption. $\endgroup$
    – Andy A
    Jun 8, 2017 at 18:27

1 Answer 1

Reset to default
0
$\begingroup$

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)

$\endgroup$
3
  • $\begingroup$ As was explained in the comments to your question, part 3 is trivial as there is no need to flip a light more than once. $\endgroup$
    – M. Winter
    Jun 12, 2017 at 10:41
  • $\begingroup$ You can still put a limit of 0 so you can't flip a particular node which would change the answer but I suppose you could just check the solution doesn't flip that node using the answer to part 5. I will update my answer to reflect. $\endgroup$
    – Andy A
    Jun 12, 2017 at 15:17
  • $\begingroup$ @M.Winter also again that you can have higher limits if there are more states which that website above does solve $\endgroup$
    – Andy A
    Jun 12, 2017 at 15:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .