Imagine there is a 7x7 grid of lights, and only the
middle in the grid is on.
The lights are wired such that when you flip the switch for one light (from on to off or off to on) the others next to it (not diagonally) flip as well.
Using this weird wiring of lights, what is the fewest number of switch changes it takes to turn all the lights off, and which lights should you switch?
Note: Assume all the switches work in the manner explained, and there is one switch for each of the lights.
(In reply to
comment by Steven Lord)
There are actually only 2^n sets to choose from, not 2^(n^2). The program need only try out all switch/don't-switch possibilities for the first line. Thereafter, the switches to toggle on the next line merely echo the resulting on-lights that came from the preceding row (except for the opposite in the row below the middle, in the middle position). The whole set is determined by the first row. If the last row then comes out all off, then it was a good first row; otherwise it's on to the next first row.
Using this quicker method, I got even 17x17 and 19x19:
size 17
1 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0
0 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 0
1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 1 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 1 1 0 1 0 1 0 1 1 0 0 0 1 1 0 1
0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1
1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 1
1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0
1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1
0 1 1 1 0 1 1 1 0 0 0 1 1 0 1 0 1
103
size 19
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0
0 1 0 1 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0
1 1 1 0 0 0 1 1 1 0 1 1 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0
1 1 1 0 0 0 1 1 1 0 1 1 1 0 1 1 1 0 0
0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0
0 0 1 1 0 1 1 0 0 0 0 0 1 1 0 1 0 1 1
0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0
93
|
|
Posted by Charlie
on 2022-11-11 22:01:34 |
Faster Method -- here's 17 and 19
