I'm implementing an algorithm using branch and bound to find a solution for the game lights out. I can't find the way to relax the restrictions of the game in order to find the bounds. How can I relax the problem?
1 Answers
You can get a quick but poor quality lower bound by dividing the number of lights on by five and rounding up -- each press turns off at most five lights.
Related