[Help] Variation on Lights Out problem


I would highly appreciate any hint on the following problem. I assume there must exist a solution that doesn’t involve linear algebra (or backtracking).

Problem statement:

A house consists of n × m rooms (n, m ∈ N, n, m ≥ 2) and is represented by a matrix with n lines and m columns. All rooms, except those on the first line (i = 0) and those on the first column (j = 0) have a switch.

Switching a light in one of the rooms produces the following effect: the room with the switch (i,j), the room above the switch (i-1, j), the room on the left of switch (i,j-1) and the room on the upper-left diagonal of the switch (i-1, j-1) will have their lights turned off if they were on and will have their lights turned on if they were off.

Write a function that receives a matrix of 0s and 1s and returns 1 if there is a subset of rooms such that switching the lights in every room of this subset, results in all the rooms in the house having their lights turned off. Otherwise return 0.


For the following matrix, 1 represents a room with a light that is turned on and 0 represents a room with a light that is turned off:

0 1 1 0
0 1 0 1
0 0 1 1
0 0 0 0
0 0 0 0

By switching the lights in rooms: { {1,2}, {2,3} } all lights in the house are turned off. So there is at least one solution.

Thanks a lot! Again, any hint is appreciated.

Is this from a live contest?, if not, then provide the problem link

it’s from an admission exam from 2017 and this is a translation of the problem from Romanian. Is there anything that is not clear? Maybe I can rephrase.

Nope, it’s correct, was just wondering if it’s from a live contest.

For this problem a basic brute force would work, looping i from 1 to n-1 and j from 1 to m-1, at each point check if it’s 1 then XOR these 4 places:- current position, 1 place down, 1 place right, 1 diagonal right-down.

In the end, if all elements are 0, return 1, else 0.

1 Like

Thanks a lot. This makes a lot of sense. Is it safe to assume that when the xor operation returns 1 we can immediately break the loop and return 0?

Even the sample test case isn’t satisfying ur assumption.