0

I have a problem much like the Lights Out game (Lights out game algorithm) but without toggling the lights.

I have an n-by-n grid. When I "activate" a tile in the grid, the activated tile and its adjacent (4, except on the sides of the grid, of course) tiles are "lit." The objective is to light the entire n-by-n grid with as few "activations" as possible.

I have tried brute-forcing (2^(n*n)) with programming to see if patterns stick out, but I run out of memory quickly.

The general pattern is activating in chess-knight-L fashion, but I still don't see a general solution.

Is there an existing developed algorithm for the light game without toggling?

Eric Cochran
  • 8,414
  • 5
  • 50
  • 91
  • Could you clarify what you mean by "without toggling"? Once a square is lit, it stays lit forever? The entire grid is off by default (so the game is "lights on" I suppose)? – ggorlen Feb 15 '21 at 05:19
  • 1
    @ggorlen Yes, exactly. No tiles are ever unlit once lit, unlike in the lights off game, and we're trying to get all the lights on (starting from the off position) – Eric Cochran Feb 15 '21 at 05:38
  • I don't see that there's much to it. There are only three choices to cover the upper left tile. Either click on the tile, or the one to its right, or the one below. Then there are only two choices, either go 2 right 1 down, or 2 down 1 right. Those choices (six possibilities in all) completely define the chess-knight pattern. The only question is which of the six choices leaves the fewest holes along the edges. – user3386109 Feb 15 '21 at 06:59

0 Answers0