Flip the bulbs in minimum number of moves

We are given a $n \times m$ rectangular matrix in which every cell there is a light bulb, together with the information whether the bulb is ON or OFF.

Now i am required to switch OFF all the bulbs but i can perform only one operation that is as follows:

• I can simultaneously flip all the bulbs from ON to OFF and vice versa in any submatrix.

I need to switch OFF all the bulbs in a minimum number of moves and tell the number of moves needed as well as the moves themselves. Is there an efficient algorithm for this?

EXAMPLE: Let us assume $n=2$ and $m=3$ .The initial grid is as follow if $0$ stands for OFF and $1$ for ON:

$$\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1 \end{matrix}$$

Now we can switch OFF all bulbs in 2 moves which are as follow :

Move 1: Flip bulbs in subarray from $(1,1)$ to $(1,1)$

Move 2: Flip bulbs in subarray from $(1,2)$ to $(2,3)$

-
What is your question? – Calvin Lin Feb 7 '14 at 12:45
@CalvinLin i want minimum moves to switch OFF all the bulbs – user3001932 Feb 7 '14 at 12:49
The minimum number of moves will clearly depend on the original position of the on/off lights and therefore you cant have a general minimum number of moves only a worst case minimum or worst case maximum. Still it seems like too difficult a problem to ask in passing like this. Have you tried to solve it? – h4nusGT Feb 7 '14 at 12:50
@ThomasJRivera i am given the original position of the grid like here it was {1 1 1,0 1 1} – user3001932 Feb 7 '14 at 13:02
@ThomasJRivera I tried solving it,I think solving the largest submatrix of 1s first can help in this problem – user3001932 Feb 7 '14 at 13:03

I don't know of an efficient algorithm that produces the minimal number of moves, but there's an algorithm that gives pretty good results.

The algorithm is based on the following observation: From the original $m \times n$ matrix construct a derived matrix of size $m+1 \times n+1$ by considering all $2\times2$ submatrices of the original matrix (imagine a border of zeros around it) and marking $0$ if the $2 \times 2$ submatrix has an even number of $1$s and $1$ if it has an odd number of $1$s. Now in the derived matrix a move on the original matrix corresponds to a move that switches just the four corners of a rectangle.

This all is best explained by an example. For your original matrix $$\begin{matrix}1 & 1 & 1 \\ 0 & 1 & 1\end{matrix}$$ the derived matrix would be $$\begin{matrix}1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1\end{matrix}$$ After the first move it becomes $$\begin{matrix}1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0\end{matrix}$$ and after the second one it is cleared.

The algorithm then looks for rectangles in the derived matrix with as many corners $1$ as possible and removes them in a greedy fashion. This is not optimal, but leads to quite good results.

Note in particular, that it follows that we must make at least $u/4$ moves, where $u$ is the number of $1$s in the derived matrix.

-
@JJ Yeah it was a good thinking.But the question demands for minimum moves which this approach cant ensure – user3001932 Feb 7 '14 at 13:14
You could probably still use this approach together with a search if the matrix is not too big, since the approach gives a lower bound for the number of moves you need to make. (Number of $1$s in the derived matrix divided by $4$). – J. J. Feb 7 '14 at 13:18
Yeah But suppose we have a 200*200 grid .Then result can vary to a large extent by this approach – user3001932 Feb 7 '14 at 13:21
But the approach is really appreciable..:) – user3001932 Feb 7 '14 at 13:24
I'm not sure if $200 \times 200$ is still applicable for $A^*$ or not. Anyway, good luck with the problem. I've seen it before and thought about it for considerable time, and this is the best I've got. :) – J. J. Feb 7 '14 at 13:24

There are $n={N+1\choose 2}{M+1\choose2}$ ways to pick a submatrix, each corresponding to a vector $v_i\in\mathbb F_2^{NM}$, $1\le i\le n$. You are looking for a solution of $\sum c_iv_i=A$ that minimizes the weight $w(c)$ (i.e. the number of $i$ with $c_i=1$)

Proposition: Among all minimum-weight solutions there exists one where no tow of the chosen submatrices share a corner.

Proof: Among all minimum weight solutions let $c$ minimize $\sum_{c_i=1}w(v_i)$. Assume two submatrices $v_iv_j$ with $c_i=c_j=1$ share a corner. Wlog. it is their top left corner, say say $v_i$ covers $(a,b)$ to $(c,d)$ and $v_j$ covers $(a,b)$ to $(e,f)$ with $a\le c$, $b\le d$, $a\le e$, $b\le f$.

• If $c< e$ and $d< f$, we could flip $(a,d+1)$ to $(c,f)$ and $(c+1,b)$ to $(e,f)$ instead
• If $c<e$ and $d=f$, we could flip $(c+1,b)$ to $(e,f)$ instead
• If $c<e$ and $d>f$, we could flip $(a,f+1)$ to $(c,d)$ and $(c+1,b)$ to $(e,f)$ instead
• All remaining cases can be treated similarly (use symmetry)

Since this replaces overlapping rectangles with disjoint rectangles the sum of rectangle weights decreases, contradicting its minimality. $_\square$

EDIT: This proposition may be helpful to devise an algorithm to find the answer by dynamic programmming, though I am not sure yet how to do so without requiring lots of memory. Thanks to Christoph Pregel that my original corallary of the proposition was trivial. Indeed we already find a better simple general estimate as follows: A row (or column) of $N$ light bulbs with $n$ separate intervals of on-bulbs (so $N\ge 2n-1$) can easily be cleared with $n$ moves. Thus for even $N$ we need at most $\frac12NM$ moves to clear the whole matrix; the same holds for even $M$; and if both $N$ and $M$ ore odd, it takes at most $\frac{N+1}{2}$ moves to reduce to the case of even $M$, i.e. we need at most $\lceil\frac{NM}2\rceil$ moves in general. In fact one can verify by exhaustive search that any $4\times 4$ matrix can be cleared in at most $5$ moves; this shows that $\le 5\cdot \lceil \frac N4\rceil\cdot \lceil \frac M4\rceil\approx \frac{5}{16}NM$ moves suffice. Again, this does not solve the problem itself, but it may give a helpful heuristic estimate for "distance" in a suitable algorithm.

-
I think the proposition is false in the case $\begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{matrix}$. Here the minimal solution is two moves, but they share a corner. Also the fact that we need at most $NM$ moves is quite trivial: just turn the bulbs one by one. – J. J. Feb 7 '14 at 16:38
The corollary isn't really a corollary is it? It's pretty obvious we need at most $NM$ moves to switch off at most $NM$ light bulbs, even if we just switch one at a time. – Christoph Feb 7 '14 at 16:58
@J.J Hm, that i not the corner-sharing I had in mind. Draw the lines around the ractangles; the do overlap by a $1\times 1$ rect. - In the light of Christoph's comment it seems I suffered from tunnel vision anyway :) – Hagen von Eitzen Feb 8 '14 at 12:20