1
$\begingroup$

You paint the grid green, one square at a time. You can only paint a square green if it shares an edge with 1 or 3 yellow squares (diagonals don't count). What's the maximum number of squares you can color?

Starting Grid## ##

I knew the answer was 24 because I played a handled puzzle game called "lights out" as a kid. It had the same rules as applied here, except every square you hit that wasn't lit would light up, and every square you hit that was lit would go dark. In addition, every square that shared an edge with the square that you hit would invert its state (again, diagonals don't count). Thus if the square above the one you touched was off, it would turn on and vice versa.

There were hundreds of pre-progrmmaed starting configurations, the goal being to get all the lights out, then there was a mode that you could set the starting lights yourself and try to solve. After many tries I realized it was impossible to begin with every square lit and get them all to go out. There would always be one...

I'd like to see an algorithm that can accomplish this in plug & play fashion. I suspect the developers knew one, as there were so many pre-programmed puzzles.

Note: obviously you can't do 25 because the last tile won't share an edge with any other yellow tiles

EDIT: The rules for the handheld game "lights out" are a bit different in that you can hit any square, and all the squares that share an edge invert their state (on/off). Every "level of the game starts with a different combination of lights on, that require an increasing number of steps to turn off. Is there an algorithm or equation that can be used to find various combinations of starting states (i.e. Which lights are on and which ones are off) that can all be solved?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

A brute force algorithm is in fact going to get the best results:

for i=1..5, j=1..5 
    if (i,j) light is on 
        count adjacent lights
        if adjacent lights = 1 or 3
           turn light off
           start again with i=1 and j=1

This closes the lights $2,1,4,3,5$ in every line and the lights $1,2,3,4$ of the last line

$\endgroup$
2
  • $\begingroup$ Thanks for that. I guess as a follow on question (I'll edit to add this to the original) would be is there an equation or some kind of algorithm that can be used to determine "starting lights" of the puzzle game that can be solved so all lights go off? The rules of the lights put game are a bit different but curious how you could automate a method to get new starting combinations that can be solved. $\endgroup$
    – Hanzy
    Jun 23, 2017 at 15:29
  • $\begingroup$ @RossMillikan I said that every time it turns a light off it starts from the beginning. In fact its 21435 instead of 24135. I'll fix it now $\endgroup$
    – Thanos Darkadakis
    Jun 23, 2017 at 16:19

You must log in to answer this question.

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