Flip the bulbs in minimum number of moves

Question

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)$

Answer 1

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.

Answer 2

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.