perplexus.info :: Logic : Lights On Diagonally

Lights On Diagonally (Posted on 2009-07-15)

"Lights Switched" toggles the cell selected and its immediate orthogonal neighbours.
"Lights On Diagonally" does exactly the same except that diagonal neighbours are toggled on or off, ie, if a neighbour is on it is turned off.

Select an "N x N" grid size to display that grid for examination.

Offer a lowest switching sequence for each grid (for the 3 x 3 it takes 5).

See The Solution Submitted by brianjn

Rating: 4.5000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

computer solution

| Comment 3 of 7 |

All solutions appear below, not just the least switching sequence. The toggled switches appear as *'s and the untoggled ones as .'s. Each grid is preceded by its size and followed by the number of toggled switches. So for example the 5x5 shows two different solutions with 11 toggles (the optimum) and one with 19 toggles (non-optimum); no other solutions are possible except for rotations/reflections.

In fact, only 4, 5 and 9 have multiple toggle sets, and of these only 5 and 9 have solution sets that use more than the minimum number of toggles. The solutions for a given size are not sorted by number of toggles, so the lowest might not be first and if there is more than one of the lowest count, they are not necessarily together. The 9x9 is particularly prolific and has 16 of the minimal-count (37 toggles) distinct solutions, mixed with other toggle counts.

 3
 . * .
 * * *
 . * .
 5

 4
 . . . .
 . * * .
 * * * *
 . * * .
 8

 4
 . . . *
 * * . .
 * . * .
 * * * .
 8

 4
 . . * *
 * * . *
 . . * .
 * . * .
 8

 4
 * . . *
 * . . *
 . . . .
 * * * *
 8

 5
 . . . . *
 . * * . .
 * * * * *
 . * * . .
 . . . . *
 11

 5
 . . . * *
 * * . . .
 * . * . *
 . * . . *
 . * . . *
 11

 5
 . * . * *
 * * * . *
 * * * * *
 * * * . *
 . * . * *
 19

 6
 . . * * . .
 . * * * * .
 * * . . * *
 * * . . * *
 . * * * * .
 . . * * . .
 20

 7
 * * . * . * *
 * . * * * . *
 . * . * . * .
 * * * * * * *
 . * . * . * .
 * . * * * . *
 * * . * . * *
 33

 8
 . . * . . * . .
 * * . * * . * *
 * . . * * . . *
 * * * . . * * *
 . . * * * * . .
 * . . * * . . *
 . . . . . . . .
 * * * * * * * *
 34

 9
 . . . . . . . . *
 * * . . * * . . *
 . . . * * * * . *
 . . . . * * . . .
 . * * * * * * * .
 . * . * * . . * .
 . . * * * * . . *
 * . . . * * . * *
 * . * . . . * . .
 37

 9
 . . . . . . . * *
 . * * . . * * . *
 . * . * * . * * *
 . . * . . * . . .
 . . * . * . * . .
 . * . * . . * * .
 . * * . * * . * *
 * . * . . * * * .
 * * * . . . * . .
 37

 9
 . . . . . . * . .
 * * . . * * . * *
 * . * * . * * . .
 . * . . * . . . .
 * * * * * * * * *
 . * . . * . . . .
 * . * * . * * . .
 * * . . * * . * *
 . . . . . . * . .
 37

 9
 . . . . . . * * .
 . * * . . * * * *
 * * * * . . * * .
 . * * . . . . . .
 * . * . * . * . *
 . * . . . . * . .
 * * * . . * * * .
 * * * . . * * * .
 . * . . . . * . .
 37

 9
 . . . . . * . . *
 * * . . * * * . .
 . . . * * . * * *
 * . * . . * * . .
 . . * * * * * . .
 . * * * . . * * *
 . * * . * * . . *
 . . * . * * . * *
 * . * * . . * . .
 41

 9
 . . . . . * . * *
 . * * . . * . . .
 . * . * * * * . *
 * . . . * * * . .
 . * * . * . * * .
 . * * * * . . * *
 . . * * * * . * *
 . . . . . * * * .
 * * * * . . * . .
 41

 9
 . . . . . * * . .
 * * . . * * * * .
 * . * * . . * * .
 * * * . . . * . .
 * . * * * * * . *
 . * * . . . * . *
 * * * . . * * . .
 . * * . * * . * *
 . . . * . . * . .
 41

 9
 . . . . . * * * .
 . * * . . * . * .
 * * * * . * * . .
 * * . . * . * . .
 * * * . * . * * *
 . * * . * . . . *
 * . * * . * * * .
 . * . . . * * * .
 . * . * . . * . .
 41

 9
 . . . . * . . . .
 * * . . * . . * *
 * . * * * * * . *
 . * . . * . . * .
 . * . * * * . * .
 . . . . * . . . .
 . . * * * * * . .
 * * . * * * . * *
 . . * . * . * . .
 37

 9
 . . . . * . * . *
 * * . . * . . . *
 . . . * . * * . .
 . . . . * * . * .
 * * . * * * . * *
 . . . * * . . * .
 * . * * . * . . *
 * . . * * * . * *
 * . . . * . * . .
 37

 9
 . . . . * . * * *
 . * * . . . * . *
 . * . * . . * * .
 . . * . . * . * .
 * . . . * . . . *
 . . . * . . * * .
 * * * . . * . * *
 * . * * . * * * .
 * * . . * . * . .
 37

 9
 . . . . * * * . *
 * * . . * . * . .
 . . . * . . * * .
 * . * . . * * * .
 * . . * * * . . *
 . . * * . . * * *
 * * * . . * . . *
 . . * * * * . * *
 * . . * * . * . .
 41

 9
 . . . . * * * * *
 . * * . . . . . .
 . * . * . * * . .
 * . . . * * * * .
 * * . . * . . * *
 . . * * * . . * *
 * . * * . * . * *
 . . . * . * * * .
 * * . * * . * . .
 41

 9
 . . . * . . . * *
 * * . . . * * . *
 . . . . * . * * *
 . . . . * * * . *
 . * * . * . * * .
 * * * * * . . * .
 . * * . * . . . *
 * . * . . * . * *
 * * * . . * * . .
 41

 9
 . . . * . . * * .
 * * . . . * * * *
 * . * . . . * * .
 . * . . * . * . *
 * * * . * . * * *
 * * * . * . . . .
 * * * . . . * . .
 * * * . . * . * *
 . * . . . * * . .
 41

 9
 . . . * . * . . *
 . * * . * * * . .
 . * . . * . * * *
 * . . . * * . . *
 . * * * * * * * .
 * * . * * . . * *
 . * * . * . . * *
 . . * . * * * * .
 * . * * . * * . .
 45

 9
 . . . * . * . * *
 * * . . . * . . .
 . . . . * * * . *
 * . * . . * . . *
 . . * . * . * . .
 * * . * . . * * *
 . . * * * . . . *
 . . . . . * . * *
 * * * * . * * . .
 37

 9
 . . . * . * * . .
 . * * . * * * * .
 * * * . . . * * .
 * * . . * . . . *
 * * * * * * * * *
 * * . . * . . . *
 * * * . . . * * .
 . * * . * * * * .
 . . . * . * * . .
 45

 9
 . . . * . * * * .
 * * . . . * . * .
 * . * . . * * . .
 * * * . . . . . *
 * . * . * . * . *
 * * . . . . * . *
 * . * * . . * . .
 . * . . . * . * *
 . * . * . * * . .
 37

 9
 . . . * * . . * .
 * * . . . . * * *
 * . * . * . * * *
 . * . . * . * * *
 . * . . * . . * .
 * . * . * . . . .
 . * * . * . * . .
 * * * * . * . * *
 . * * . * * * . .
 41

 9
 . . . * * . * * *
 * * . . . . * . *
 . . . . . . * * .
 . . . . * * * * *
 * * . . * . . * *
 * . * * * . . * .
 * * * . . . . . *
 * . * * . * . * *
 * * . . * * * . .
 41

 9
 . . . * * * * . *
 . * * . * . * . .
 . * . . . . * * .
 * . . . * * . * *
 * * . * * * . * *
 * . . * * . . * *
 * * * . . . . * *
 . . * * * * * * .
 * . . * * * * . .
 45

 9
 . . . * * * * * *
 * * . . . . . . .
 . . . . . * * . .
 * . * . . * . * *
 * . . . * . . . *
 * . . * . . * * *
 * . * * . . . . *
 . . . * . * . * *
 * * . * * * * . .
 37

 9
 . * . . . . . . *
 * * * . . * * . .
 . * . . * * * * *
 . . . . . * * . .
 . . * . * . * . .
 . * * * . . . * .
 . * * * * . . * *
 . . * . . * * * *
 * . * . . . * * .
 37

 9
 . * . . . * . . *
 * * * . . * . . *
 . * . . * . * . *
 * . * . * * . . .
 . * * . * . * * .
 . * . * * . * * *
 . . * . * . . * *
 * . . . . * * * *
 * . * * . . * * .
 41

 9
 . * . . * . * . *
 * * * . . . * . .
 . * . . . * * * .
 . . . . . * * * .
 * . . . * . . . *
 . . * * . . . * .
 * * * * . . . * *
 . . * * . * * * *
 * . . . * . * * .
 37

 9
 . * . . * * * . *
 * * * . . . . . *
 . * . . . . * . .
 * . * . * * . * .
 * * . . * . . * *
 . . . * * . * * *
 * . * . . . . * *
 * . . * . * * * *
 * . . * * . * * .
 41

 9
 . * . * . * . * *
 * * * . * * * . *
 . * . * * * * * *
 * . * . * * * . *
 . * * * * * * * .
 * * * * * . * * *
 . * * * * * . * *
 * . * . * * * * *
 * * * * . * * * .
 61

 9
 . * . * . * * * .
 * * * . * * * * *
 * * * * . * * * .
 * * * . * . * . *
 * * * * * * * * *
 * * * . * . * . *
 * * * * . * * * .
 * * * . * * * * *
 . * . * . * * * .
 61

 9
 . * . * * * * * *
 * * * . * . * . *
 . * . * . * * * .
 * . * . * * * * *
 * * . * * * . * *
 * . * * * . * * *
 * * * * . * . * *
 * . * * * * * * *
 * * . * * * * * .
 61

 9
 * . . . . . * . *
 * . . * * . . . *
 . . . * . * . . *
 . * . * * * . . .
 * * * * * * * * *
 . * . * * * . . .
 . . . * . * . . *
 * . . * * . . . *
 * . . . . . * . *
 37

 9
 * . . . . . * * *
 . . * * . . * . *
 . * . * . . . * *
 . * * * . * . . .
 * . * . * . * . *
 . * . * . * * . .
 . * . . . * . * *
 * . * * . . * . .
 * * . . . . * . *
 37

 9
 * . . . . * * . *
 * . . * * . * . .
 . . . * . . . * *
 * * * * . * * . .
 * . * * * * * . *
 . * * * . * * . *
 . * . . . * . . *
 . . * * * . . . *
 * . . * . . * . *
 41

 9
 * . . . . * * * *
 . . * * . . . . .
 . * . * . * . . *
 * * . * * * * . .
 * * * . * . * * *
 . * * * * * . . *
 . . . * . * . * *
 . . . * . . * . .
 * * . * . . * . *
 41

 9
 * . . . * . . . *
 * . . * * * . . *
 . . . * * * . . .
 . * . * * * . * .
 . * . * * * . * .
 . . . * * * . . .
 * . . * * * . . *
 * . . . * . . . *
 * . * . * . * . *
 37

 9
 * . . * . . * * *
 * . . * . . * . *
 . . . . . . . * *
 . * . * * * * . *
 * * * . * . * * *
 * * * * * * . . .
 . * . . . . . . *
 * . * * . . . . *
 * * . . . * * . *
 41

 9
 * . . * . * * . *
 . . * * * . * . .
 . * . . . . . * *
 * * . * * * . . *
 * * * * * * * * *
 * * . * * * . . *
 . * . . . . . * *
 . . * * * . * . .
 * . . * . * * . *
 45

 9
 * . . * . * * * *
 * . . * . . . . .
 . . . . . * . . *
 * * * * . * . . *
 * . * . * . * . *
 * * . * . * * . *
 . . . * . . . . *
 . . . * . . . . *
 * * . * . * * . *
 37

 9
 * . . * * . . * *
 * . . * . * * . *
 . . . . * . . * .
 . * . * * * * * *
 . * . . * . . * .
 * . * * * * . . .
 * * . . * . . . *
 * . * . . . . . *
 * * * . * * * . *
 41

 9
 * * . * . * * * *
 * . * * * . * . *
 . * . * . * . * *
 * * * * * * * . *
 * * * * * * * * *
 * * * * * * * . *
 . * . * . * . * *
 * . * * * . * . *
 * * . * . * * * *
 61

 10
 * * * * . . * * * *
 * . * . * * . * . *
 * * . * . . * . * *
 * . * * * * * * . *
 . * . * . . * . * .
 . * . * . . * . * .
 * . * * * * * * . *
 * * . * . . * . * *
 * . * . * * . * . *
 * * * * . . * * * *
 64

The patterns were found by the program below, which tried all possibilities for the first row and the leftmost position of the each row. From there on, the sequence was determined by what was needed for the row prior to the one being worked on. If, at the end of any row, the row above was not complete, the sequence was abandoned. And of course the last row had to be on.

The output of this program was then massaged to remove rotations and reflections, and zeros were changed to periods and ones to asterisks.

DECLARE SUB col1 (row!)
DECLARE SUB build (col!)
DECLARE SUB complete (row!)

CLEAR , , 25000

DIM SHARED n, good

OPEN "ltondiag.txt" FOR OUTPUT AS #2

FOR n = 3 TO 10
REDIM SHARED bd(n + 1, n + 1), mv(n, n)
build 1
NEXT n

SUB build (col)
FOR v = 0 TO 1
   bd(1, col) = v
   IF v = 1 THEN
     bd(2, col - 1) = 1 - bd(2, col - 1)
     bd(2, col + 1) = 1 - bd(2, col + 1)
   END IF
   mv(1, col) = v

   IF col < n THEN
      build col + 1
   ELSE
      CALL col1(2)
   END IF

   IF v = 1 THEN
     bd(2, col - 1) = 1 - bd(2, col - 1)
     bd(2, col + 1) = 1 - bd(2, col + 1)
   END IF
NEXT
END SUB

SUB col1 (row)
FOR v = 0 TO 1
mv(row, 1) = v
IF v = 1 THEN
    bd(row, 1) = 1 - bd(row, 1)
    bd(row - 1, 2) = 1 - bd(row - 1, 2)
    bd(row + 1, 2) = 1 - bd(row + 1, 2)
END IF

complete row

IF v = 1 THEN
    bd(row, 1) = 1 - bd(row, 1)
    bd(row - 1, 2) = 1 - bd(row - 1, 2)
    bd(row + 1, 2) = 1 - bd(row + 1, 2)
END IF
NEXT
END SUB

SUB complete (row)
good = 1
FOR col = 2 TO n
        mv(row, col) = 1 - bd(row - 1, col - 1)
        IF mv(row, col) = 1 THEN
         bd(row - 1, col - 1) = 1 - bd(row - 1, col - 1)
         bd(row - 1, col + 1) = 1 - bd(row - 1, col + 1)
         bd(row, col) = 1 - bd(row, col)
         bd(row + 1, col - 1) = 1 - bd(row + 1, col - 1)
         bd(row + 1, col + 1) = 1 - bd(row + 1, col + 1)
        END IF
NEXT

IF bd(row - 1, n) = 0 THEN
   good = 0
ELSE
   IF row = n THEN
    FOR c = 1 TO n
      IF bd(row, c) = 0 THEN good = 0: EXIT FOR
    NEXT
    IF good THEN
     PRINT n: pct = 0
     PRINT #2, n
     FOR r = 1 TO n: FOR c = 1 TO n
       PRINT mv(r, c);
       PRINT #2, mv(r, c);
       pct = pct + mv(r, c)
     NEXT: PRINT : PRINT #2, : NEXT
     PRINT pct: PRINT
     PRINT #2, pct: PRINT #2,
     'DO: LOOP UNTIL INKEY$ > ""
    END IF
   ELSE
    col1 row + 1
   END IF
END IF

FOR col = 2 TO n
        IF mv(row, col) = 1 THEN
         bd(row - 1, col - 1) = 1 - bd(row - 1, col - 1)
         bd(row - 1, col + 1) = 1 - bd(row - 1, col + 1)
         bd(row, col) = 1 - bd(row, col)
         bd(row + 1, col - 1) = 1 - bd(row + 1, col - 1)
         bd(row + 1, col + 1) = 1 - bd(row + 1, col + 1)
        END IF
NEXT

END SUB

Posted by Charlie on 2009-07-15 19:01:00

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 (5)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info