10
$\begingroup$

The following two 5x5 Lights-Out puzzles are not solvable. Is there a way to find out why, without trying to solve them?

 
  [1, 0, 0, 1, 0]
  [1, 1, 1, 1, 0]
  [1, 1, 1, 0, 0]
  [0, 0, 1, 0, 0]
  [1, 1, 1, 1, 1]

  [1, 1, 1, 0, 1]
  [1, 0, 0, 1, 0]
  [0, 1, 0, 1, 0]
  [0, 1, 0, 1, 1]
  [0, 1, 1, 1, 1]

(These are just two examples.)

$\endgroup$
0

1 Answer 1

19
$\begingroup$

To test if a 5x5 Lights Out pattern is solvable, you need to check two things. First look at the top, middle and bottom rows, at the first two and last two lights - the 12 lights bolded here:

  [1, 0, 0, 1, 0]    [1, 0, ., 1, 0]
  [1, 1, 1, 1, 0]    [., ., ., ., .]
  [1, 1, 1, 0, 0]    [1, 1, ., 0, 0]
  [0, 0, 1, 0, 0]    [., ., ., ., .]
  [1, 1, 1, 1, 1]    [1, 1, ., 1, 1]

If there are an odd number of lights lit up, then the puzzle is unsolvable. In this case 8 of them are lit, which is even, so that does not prove anything yet.

The second test is the same but looking at the first, middle and last columns instead, again only the first two and last two lights:

  [1, 0, 0, 1, 0]    [1, ., 0, ., 0]
  [1, 1, 1, 1, 0]    [1, ., 1, ., 0]
  [1, 1, 1, 0, 0]    [., ., ., ., .]
  [0, 0, 1, 0, 0]    [0, ., 1, ., 0]
  [1, 1, 1, 1, 1]    [1, ., 1, ., 1]

This time 7 of them are lit up. This is odd, proving this pattern to be unsolvable.

If a pattern passes both tests (i.e. both totals are even numbers) then the pattern can be solved.

To read more about why this works, you can look at my Mathematics of Lights Out page.

$\endgroup$
6
  • $\begingroup$ Thanks a lot @Jaap Scherphuis. This looks fantastic. I haven't upvoted though your answer yet, because I have a question: In the 2nd test (columns), why is the middle row removed, i.e. not taken into consideration? (The test just says "looking at the first, middle and last columns".) Do I miss something that other people didn't? $\endgroup$
    – Apostolos
    Commented Nov 4, 2023 at 10:06
  • $\begingroup$ @Apostolos The second subset of lights to test is the same as the first subset, except rotated a quarter turn. As for why exactly this subset, it ultimately is because if you were to press those 12 buttons, there is no effect on the lights. $\endgroup$ Commented Nov 4, 2023 at 10:26
  • $\begingroup$ But you haven't mentioned rotation anywhere. If this is the case, shouldn't you have mentioned it as part of the test-rule? Instead, and I will repeat, your test-rule is "look at the first, middle and last columns". That's all. Moreover, if it was about a rotation, the left board (in the 2nd test) should be the "rotated" board. But it is the original one. Which means that we pass from it to the subset. So, my question about the "empty middle row" in the second test still applies. Well, until you ammend the description of your method. Please do. $\endgroup$
    – Apostolos
    Commented Nov 4, 2023 at 10:46
  • $\begingroup$ @Apostolos, notice that the second test is a rotation of the first. $\endgroup$
    – JDL
    Commented Nov 4, 2023 at 11:18
  • $\begingroup$ @Jaap, I'm back. I checked again and I realized that in the 2nd test I was looking at the whole columns because I forgot to look only the first two and last two cells! My bad. There's no rotation whatsoever. The 2nd subset is obtained directly from the original board, as in the first test, only looking at the columns instead of the rows. That is, as you have exactly described it, both in words and schematically. I have upvoted you this time, of course, 👍 and I thank you a lot! $\endgroup$
    – Apostolos
    Commented Nov 4, 2023 at 12:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.