Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What is your question? –  Calvin Lin Feb 7 at 12:45
    
@CalvinLin i want minimum moves to switch OFF all the bulbs –  user3001932 Feb 7 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? –  Thomas J Rivera Feb 7 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 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 at 13:03

2 Answers 2

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.

share|improve this answer
    
@JJ Yeah it was a good thinking.But the question demands for minimum moves which this approach cant ensure –  user3001932 Feb 7 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 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 at 13:21
    
But the approach is really appreciable..:) –  user3001932 Feb 7 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 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.

share|improve this answer
    
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 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 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 at 12:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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