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

 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

 Search: Search body:
Forums (0)