All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
Lights switched (Posted on 2009-06-03) Difficulty: 4 of 5
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.

No Solution Yet Submitted by Jer    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer solution | Comment 1 of 5

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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information