Toggler is similar to Lights Out, and "Chasing the Lights", a technique mentioned in the solutions, produces, for the 4x4 case an immediate solution in 10 moves--not as good as the 4 moves that is possible.
A brute force search by computer program finds:
0 0 0 0
1 1 1 1
1 0 0 1
1 1 1 1
0 0 0 1
1 1 0 0
1 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
0 0 1 1
1 0 1 1
0 1 0 0
1 0 1 0
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
0 1 0 1
0 0 1 0
1 1 0 1
1 1 0 0
0 1 1 0
0 1 1 0
0 0 0 0
1 0 0 1
0 1 1 1
0 1 0 1
0 1 0 1
0 1 1 1
1 0 0 0
0 0 1 1
0 0 1 1
1 0 0 0
1 0 0 1
0 0 0 0
0 1 1 0
0 1 1 0
1 0 1 0
0 1 0 0
1 0 1 1
0 0 1 1
1 0 1 1
0 1 1 1
1 1 1 0
1 1 0 1
1 1 0 0
1 1 0 1
0 0 1 0
0 1 0 1
1 1 0 1
1 1 1 0
0 1 1 1
1 0 1 1
1 1 1 0
1 0 1 0
1 0 1 0
1 1 1 0
1 1 1 1
1 0 0 1
1 1 1 1
0 0 0 0
where a 1 indicates to toggle that switch and 0 indicates to leave that one alone. There are various rotations/reflections present, but two, reflections of each other, have the minimum 4.
The 5x5, solved by brute force computer program finds only one basic solution and three rotations:
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
A brute force search for 4x4 Triggler does not find any solution. The program is as follows:
DECLARE SUB vary (r%, c%)
DEFINT A-Z
CLEAR , , 4000
DIM SHARED flip(6, 6)
DIM SHARED lit(6, 6)
PRINT "--------"
vary 1, 1
END
SUB vary (r, c)
STATIC sCt
FOR cyc = 1 TO 3
IF r = 4 AND c = 4 THEN
GOSUB checkIt
ELSE
IF c = 4 THEN r1 = r + 1: c1 = 1: ELSE c1 = c + 1: r1 = r
vary r1, c1
END IF
flip(r, c) = 1 + flip(r, c) MOD 6
lit(r, c) = 2 + lit(r, c) MOD 3
lit(r - 1, c) = 1 + lit(r - 1, c) MOD 3
lit(r, c - 1) = 1 + lit(r, c - 1) MOD 3
lit(r + 1, c) = 1 + lit(r + 1, c) MOD 3
lit(r, c + 1) = 1 + lit(r, c + 1) MOD 3
NEXT cyc
EXIT SUB
checkIt:
bad = 0
FOR row = 1 TO 4
FOR col = 1 TO 4
IF lit(row, col) <> 2 THEN bad = 1: EXIT FOR
NEXT
IF bad THEN EXIT FOR
NEXT
IF bad = 0 THEN
FOR i = 1 TO 4
FOR j = 1 TO 4
PRINT flip(i, j);
NEXT
PRINT
NEXT
sCt = sCt + 1: PRINT sCt
IF sCt MOD 7 = 0 THEN DO: LOOP UNTIL INKEY$ > ""
END IF
RETURN
END SUB
It is based on the fact that three times triggering a cell returns that cell and its neighbors to their original positions, so there are only three possibilities for any given cell: do not trigger, trigger once or trigger twice.
The brute force program for Toggler is similar except it has only two states per cell, and can be found in the discussion of Lights Out.
Posted by Charlie on 2004-03-12 14:01:47 |