Consider a 3x3 array of lighted buttons:
[O][O][O]
[O][O][O]
[O][O][O]
If any one of these buttons is pressed, it and all of its directly adjacent neighbors will toggle their status on/off. (Diagonals do not change.)
The goal is to get all of the lights to be off. Which buttons must be pressed to accomplish this?
Which buttons would accomplish this goal in the minimum number of presses for 4x4, 5x5, 6x6, 7x7, 8x8, and 9x9 arrays?
A nice site with the game from 3 x 3 up to 8 x 8 is here.
The resulting pattern of lights will depend solely on which combination of buttons is pressed, not on their order, so in devising the method, we might as well go in reading order: top-to-bottom and left-to-right.
The way to proceed is in fact dictated by the combination pressed in the first row. There are a total of 2^s ways of choosing buttons to press in the first row, where s is the size of a side of the square. Any one of these ways will leave some lights on and some off in that row. The combination of buttons you then press in the second row gives you the only chance to turn those lights in the first row that were left on or returned to on, back off, so this set is dictated by the choices in the first row. Likewise, this then leaves some lights in the second row lit, which can be rectified by a combination of button hits in the third row, which is thereby dictated by the previous choices. This inevitability holds all the way down to the bottom row. If the bottom row itself then has any lights that are on in the final position, then we know that the initial choice of combination to hit in the first row will not work, as there are no further rows to fix up the last one, and we'd rely on a different one of the 2^s ways of choosing buttons to hit in that original row.
The program, for each of the sizes 3 to 9, tries each of the 2^s ways of toggling the first row, and follows the dictated combinations down to the bottom row to see if the set constitutes a solution. If so, the original version checked to see if the number of presses was lower than the lowest for that size grid, and at the end the lowest numbers were printed out. Once that was done, these numbers were placed into the program (the goal array in the listing at bottom), so that only those solutions with the fewest presses would be printed.
In the following diagrams, 1 means press the button, 0 means don't. The number below the diagram is the number of button presses. As mentioned, only the minimum is shown.
1 0 1
0 1 0
1 0 1
5
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
4
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
4
The above 2 for 4x4 are mirror images.
1 1 0 0 0
1 1 0 1 1
0 0 1 1 1
0 1 1 1 0
0 1 1 0 1
15
1 0 1 1 0
0 1 1 1 0
1 1 1 0 0
1 1 0 1 1
0 0 0 1 1
15
0 1 1 0 1
0 1 1 1 0
0 0 1 1 1
1 1 0 1 1
1 1 0 0 0
15
0 0 0 1 1
1 1 0 1 1
1 1 1 0 0
0 1 1 1 0
1 0 1 1 0
15
The above four are rotations; there are no reflections as there is an axis of symmetry.
1 0 1 1 0 1
0 1 1 1 1 0
1 1 1 1 1 1
1 1 1 1 1 1
0 1 1 1 1 0
1 0 1 1 0 1
28
1 1 0 1 0 1 1
1 1 1 0 1 1 1
0 1 1 0 1 1 0
1 0 0 1 0 0 1
0 1 1 0 1 1 0
1 1 1 0 1 1 1
1 1 0 1 0 1 1
33
1 1 0 0 0 0 1 1
1 1 0 1 1 0 1 1
0 0 1 1 1 1 0 0
0 1 1 1 1 1 1 0
0 1 1 1 1 1 1 0
0 0 1 1 1 1 0 0
1 1 0 1 1 0 1 1
1 1 0 0 0 0 1 1
40
0 0 1 1 0 0 1 0 0
1 0 1 1 0 0 0 0 1
0 1 0 0 0 1 0 0 0
1 0 1 0 0 0 0 1 0
0 0 0 0 1 0 0 0 0
0 1 0 0 0 0 1 0 1
0 0 0 1 0 0 0 1 0
1 0 0 0 0 1 1 0 1
0 0 1 0 0 1 1 0 0
25
0 0 1 0 0 1 1 0 0
1 0 0 0 0 1 1 0 1
0 0 0 1 0 0 0 1 0
0 1 0 0 0 0 1 0 1
0 0 0 0 1 0 0 0 0
1 0 1 0 0 0 0 1 0
0 1 0 0 0 1 0 0 0
1 0 1 1 0 0 0 0 1
0 0 1 1 0 0 1 0 0
25
0 1 0 1 0 0 0 1 0
0 0 1 0 0 1 0 0 0
1 1 0 1 0 0 0 0 1
1 1 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 1 1
1 0 0 0 0 1 0 1 1
0 0 0 1 0 0 1 0 0
0 1 0 0 0 1 0 1 0
25
0 1 0 0 0 1 0 1 0
0 0 0 1 0 0 1 0 0
1 0 0 0 0 1 0 1 1
0 0 1 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0
1 1 0 0 0 0 1 0 0
1 1 0 1 0 0 0 0 1
0 0 1 0 0 1 0 0 0
0 1 0 1 0 0 0 1 0
25
The above four are also basically the same due to rotation/reflection.
1 0 0 1 0 0 0 0 1
0 0 0 0 0 1 1 0 0
0 1 1 0 0 1 1 0 0
0 1 1 0 0 0 0 0 1
0 0 0 0 1 0 0 0 0
1 0 0 0 0 0 1 1 0
0 0 1 1 0 0 1 1 0
0 0 1 1 0 0 0 0 0
1 0 0 0 0 1 0 0 1
25
1 0 0 0 0 1 0 0 1
0 0 1 1 0 0 0 0 0
0 0 1 1 0 0 1 1 0
1 0 0 0 0 0 1 1 0
0 0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0 1
0 1 1 0 0 1 1 0 0
0 0 0 0 0 1 1 0 0
1 0 0 1 0 0 0 0 1
25
The above two are reflected; radial symmetry makes them their own rotations.
DEFDBL A-Z
DATA 5, 4, 15, 28, 33, 40, 25
FOR i = 3 TO 9: READ goal(i): NEXT
OPEN "ltswtchd.txt" FOR OUTPUT AS #2
FOR sz = 3 TO 9
minbp(sz) = 9999999
FOR line1 = 0 TO INT(2 ^ sz - 1 + .5)
REDIM bd(10, 10), hit(9, 9)
l = line1
bp = 0
FOR col = 1 TO sz
q = l \ 2: r = l MOD 2
hit(1, col) = r: bp = bp + r
IF r THEN
bd(1, col - 1) = 1 - bd(1, col - 1)
bd(1, col) = 1 - bd(1, col)
bd(1, col + 1) = 1 - bd(1, col + 1)
bd(2, col) = 1 - bd(2, col)
END IF
l = q
NEXT col
FOR row = 2 TO sz
FOR col = 1 TO sz
IF bd(row - 1, col) = 0 THEN
hit(row, col) = 1: bp = bp + 1
bd(row, col - 1) = 1 - bd(row, col - 1)
bd(row, col) = 1 - bd(row, col)
bd(row, col + 1) = 1 - bd(row, col + 1)
bd(row - 1, col) = 1 - bd(row - 1, col)
bd(row + 1, col) = 1 - bd(row + 1, col)
END IF
NEXT
NEXT
good = 1
FOR col = 1 TO sz
IF bd(sz, col) = 0 THEN good = 0: EXIT FOR
NEXT
IF good THEN
IF bp = goal(sz) THEN
FOR row = 1 TO sz
FOR col = 1 TO sz
PRINT hit(row, col);
PRINT #2, hit(row, col);
NEXT
PRINT
PRINT #2,
NEXT
PRINT bp
PRINT #2, bp
IF bp < minbp(sz) THEN minbp(sz) = bp
END IF
END IF
NEXT line1
NEXT sz
FOR i = 3 TO 9: PRINT minbp(i); : NEXT
|
|
Posted by Charlie
on 2009-06-03 16:50:45 |
computer solution
