Minimize the sum of solution of linear equation

Question

Let x(i,j) be a variable. All variables and constants can only have value of 0 or 1. Also, sum of two variables x(i,j) and x(k,l) is equal to (x(i,j)+x(k,l)) % 2 For a given equation of the following format, what algorithm can be used to find a solution to all x(i,j) such that sum of all x(i,j) is minimized:

x(0,0)  +x(0,1)  +x(0,2)  +x(1,0)  +0       +0       +x(2,0)  +0       +0       = 0
x(0,0)  +x(0,1)  +x(0,2)  +0       +x(1,1)  +0       +0       +x(2,1)  +0       = 0
x(0,0)  +x(0,1)  +x(0,2)  +0       +0       +x(1,2)  +0       +0       +x(2,2)  = 1
x(0,0)  +0       +0       +x(1,0)  +x(1,1)  +x(1,2)  +x(2,0)  +0       +0       = 0
0       +x(0,1)  +0       +x(1,0)  +x(1,1)  +x(1,2)  +0       +x(2,1)  +0       = 0
0       +0       +x(0,2)  +x(1,0)  +x(1,1)  +x(1,2)  +0       +0       +x(2,2)  = 1
x(0,0)  +0       +0       +x(1,0)  +0       +0       +x(2,0)  +x(2,1)  +x(2,2)  = 1
0       +x(0,1)  +0       +0       +x(1,1)  +0       +x(2,0)  +x(2,1)  +x(2,2)  = 1
0       +0       +x(0,2)  +0       +0       +x(1,2)  +x(2,0)  +x(2,1)  +x(2,2)  = 1

The above equation can also be seen as:

x(0,0)  +x(0,1)  +x(0,2)  +x(1,0)  +x(2,0)  = 0
x(0,0)  +x(0,1)  +x(0,2)  +x(1,1)  +x(2,1)  = 0
x(0,0)  +x(0,1)  +x(0,2)  +x(1,2)  +x(2,2)  = 1
x(0,0)  +x(1,0)  +x(1,1)  +x(1,2)  +x(2,0)  = 0
x(0,1)  +x(1,0)  +x(1,1)  +x(1,2)  +x(2,1)  = 0
x(0,2)  +x(1,0)  +x(1,1)  +x(1,2)  +x(2,2)  = 1
x(0,0)  +x(1,0)  +x(2,0)  +x(2,1)  +x(2,2)  = 1
x(0,1)  +x(1,1)  +x(2,0)  +x(2,1)  +x(2,2)  = 1
x(0,2)  +x(1,2)  +x(2,0)  +x(2,1)  +x(2,2)  = 1

For example, the given equation can have following two solutions:

1. x(0,2)=x(1,0)=x(1,1)=1 and all x(i,j) = 0. In this case sum of all x(i,j) = 3
2. x(2,2)=1 and all x(i,j)=0. In this case sum of all x(i,j) is 1

What algorithm can be used to find later solution. I have tried using gausian elimination, but the result is not consistent.

More explanation: More explanation on how the equation was obtained: https://math.stackexchange.com/a/441588/299278

EDIT1: I implemented a BFS for this but it is very inefficient for variables till x(15,15).

Answer 1

Here is my suggestion for the game as specified in your link. I use a Mixed Integer Program (MIP) to model the problem. This can be solved using any MIP solver.

Basically we count the number of switches in the same row and column and require that the final state is even (to make it dark). (Note: the sum is over the whole column and the over the whole row, so we double count the element itself -- this is repaired by the subtraction). Even means 2 times an arbitrary integer. I said earlier to use a dummy objective. We can however even minimize the number of switches.

I use the initial state $s0$:

The model can be compactly written as:

The even constraint is basically what you described in your question. My $s_{i,j}$ is your $x_{i,j}$. In the model we use a binary variable $s_{i,j}$ which can only assume values 0 or 1. The integer variable $y_{i,j}$ is used only to make sure the final state is $0,2,4,...$.

When I solve this I see one would need to apply the following switches:

----     37 VARIABLE s.L  switch state

            c1          c2          c3          c4

r1           1                                   1
r2           1           1           1
r3                       1                       1
r4                                   1           1

Note: you can solve MIP models like this remotely on NEOS. The complete GAMS model is here. (GAMS is the modeling language I used to express the model).