2
$\begingroup$

Suppose you have an $m \times n$ array which can hold boolean values. It is initially empty, full of uniform $0$s.

The only way to change the array is by supplying two pairs of coordinates, defining a rectangular area within the array; every bit in that area is then flipped. A first such move would give you something like this:

diagramA

(I'm not sure of the ideal notation for that, but it's (2,4)-(8,15) by my reckoning, defining opposite inclusive corner coordinates.)

However, observe what happens when you play a second move, (4,4)-(6,17):

diagramB

Being an exclusive-or, the middle bits flip back to $0$ while the overhang on the right flips to $1$. Naively, one could look at this second picture and conclude that three moves were necessary to reach that configuration if starting from all zeros, one move for each rectangle. As we've seen, this was done with only two.

This is a straightforward example, but when you combine even a handful of overlapping moves together, it appears to become extremely difficult to disentangle. If I'm not mistaken, this is not the case with an analogous one-dimensional array, where it's simple to derive the optimal series of moves (that is, XORing line segments) to recreate a configuration in $O(n)$ time. This is because every unequal adjacent pair implies an XOR segment with an endpoint between that pair.

The goal is to calculate the minimum number of moves needed to recreate any given final configuration, starting with an empty array. I'll consider my question answered if someone can tell me whether an efficient algorithm is known for this or something similar, can sketch one themselves, or can provide an informed opinion on why such an algorithm is or is not likely to exist. By efficient algorithm, I mean one that runs in polynomial time in the general case.

(I realize this is arguably a CS question, but I'm trying here first.)


Confirmed RobPratt's nice solution.

For future reference, this Mathematica code will run a test with random parameters and give you output as in the screenshot below.

a[i_, j_, i1_, j1_, i2_, j2_] := Boole[i1 <= i <= i2 && j1 <= j <= j2]
x[coords_] := Boole@MemberQ[rects, coords]
m = Table[0, 9, 13];
randrect := Module[{x1, y1, x2, y2},
   {x1, x2} = Sort[RandomInteger[{1, Length@First@m}, 2]];
   {y1, y2} = Sort[RandomInteger[{1, Length@m}, 2]];
   {y1, x1, y2, x2}
   ];
rects = Table[randrect, RandomInteger[{1, 13}]]
Do[
  m[[rect[[1]] ;; rect[[3]], rect[[2]] ;; rect[[4]]]] = 
    1 - m[[rect[[1]] ;; rect[[3]], rect[[2]] ;; rect[[4]]]];
  , {rect, rects}];
ArrayPlot[m, Mesh -> True]
t = Minimize[{Sum[
     x[{i1, j1, i2, j2}], {i2, Length@m}, {j2, Length@First@m}, {i1, 
      i2}, {j1, j2}], 
    And @@ Flatten@
      Table[y[i, j] \[Element] Integers && y[i, j] >= 0 && 
        Sum[a[i, j, i1, j1, i2, j2] x[{i1, j1, i2, j2}], {i2, 
           Length@m}, {j2, Length@First@m}, {i1, i2}, {j1, j2}] == 
         2 y[i, j] + m[[i, j]], {i, Length@m}, {j, Length@First@m}]}, 
   Flatten[Table[y[i, j], {i, Length@m}, {j, Length@First@m}]]];
TextGrid[{{Length@rects, "rectangles drawn"}, {First[t], 
   "rectangles calculated"}}]
ArrayPlot[Partition[Last /@ Last@t, Length@First@m], Mesh -> True]

Example output:

solution screenshot

$\endgroup$
4
  • 1
    $\begingroup$ It would be a good idea not to use "effective" as a synonym for "polynomial-time". The term "effective" commonly appears in the literature in terms like "effective procedure" which just means "computable function". It is also not the case that algorithms that are worse than polynomial-time are not effective in the informal sense that they are useful in practice. If you mean polynomial-time, say polynomial-time. And I think you will do better with this question on the theoretical computer science stack exchange forum. $\endgroup$
    – Rob Arthan
    Oct 6, 2021 at 22:35
  • $\begingroup$ I wanted to grumble at your pedantry, but you're completely right of course. Fixed. And yep, I will try there next if I get no bites here. $\endgroup$
    – Trevor
    Oct 6, 2021 at 22:39
  • 1
    $\begingroup$ Sorry to be pedantic and thanks for fixing the question (and being gracious rather than grumbly): it really does cause confusion to use effective in an informal sense. My hunch would be that there is no polynomial time algorithm, but that's just a hunch. Good luck with your question. $\endgroup$
    – Rob Arthan
    Oct 6, 2021 at 22:48
  • 1
    $\begingroup$ The corresponding decision problem is "Can the grid be created in $\leq n$ moves?" and this decision problem is clearly in NP. Don't know if this will actually help or not. $\endgroup$ Oct 6, 2021 at 23:01

1 Answer 1

1
$\begingroup$

As in the Lights Out game, you can solve the problem via Gaussian elimination mod 2, which is $O(k^3)$ for a $k \times k$ matrix. See How can I solve a vector equation in Z2?


Suppose the given $m\times n$ matrix has entries $B_{i,j}\in\{0,1\}$. Let binary decision variable $x_{i_1,j_1,i_2,j_2}$ indicate whether the rectangular submatrix with top-left corner $(i_1,j_1)$ and bottom-right corner $(i_2,j_2)$ is selected. Let $a_{i,j,i_1,j_1,i_2,j_2}\in\{0,1\}$ indicate whether entry $(i,j)$ is in the rectangular matrix defined by $(i_1,j_1)$ and $(i_2,j_2)$. With Iverson bracket notation, $$a_{i,j,i_1,j_1,i_2,j_2}=[i_1 \le i \le i_2][j_1 \le j \le j_2].$$

The problem is to minimize $$\sum_{i_1,j_1,i_2,j_2} x_{i_1,j_1,i_2,j_2}$$ subject to the $mn$ equations $$\sum_{i_1,j_1,i_2,j_2} a_{i,j,i_1,j_1,i_2,j_2} x_{i_1,j_1,i_2,j_2} \equiv B_{i,j} \pmod2 \quad \text{for all $i,j$} \tag1$$

You can reformulate $(1)$ with linear equations by introducing nonnegative integer decision variables $y_{i,j}$ and replacing $$\equiv B_{i,j} \pmod2$$ with $$= 2y_{i,j} + B_{i,j}$$ Then call an integer linear programming solver.

$\endgroup$
1
  • $\begingroup$ I'm sorry, I'm trying to figure out how to apply that to this but I'm not seeing it. Could you give me a simple example or point me in the right direction on how to set up the system in my case? $\endgroup$
    – Trevor
    Oct 9, 2021 at 6:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .