Lights Out Variant – Minimal Number of Moves Needed to Solve

Question

Lights Out was a popular puzzle in which all lights in some device had to be turned off by pressing on them, which turned off all neighbouring lights as well.

We consider instead the same variant introduced in this other question: pressing a light will flip the state of all lights in the same column and the same row. For instance (borrowing the same example from that question) by pressing on X we get:

1 0 0 0         1 0 1 0
0 0 X 0   -->   1 1 1 1  
0 1 0 0         0 1 1 0
0 0 1 0         0 0 0 0

The answers to that question tell us when it is possible to solve this puzzle, but not necessarily in an optimal way.

Given some initial configuration, how can we find the minimal number of moves needed to turn off all the lights?

EDIT: After a little research I found out that this variant was apparently first defined in Araújo, Paulo Ventura. "How to Turn All Lights Out." Elemente der Mathematik 55.4 (2000): 135-141. An investigation into minimal solutions of similar problems is carried out in this paper, which might contain the answer to my question.

EDIT 2: Unfortunately, it doesn't: the minimization results of Section 4 are about another variant. Instead, these lecture notes are about the classical "Lights Out" problem, but investigate the issue of minimization (Section 24.2.4).

EDIT 3: I put on hold the attack outlined in EDIT 2 and investigated using a BFS, as suggested by this homework assignment. Unfortunately the results weren't encouraging: despite the heroic speedup achieved by the answers to this question, that algorithm is too slow for $n > 6$.

EDIT 4: The implementation given in this question works correctly for even $n$, but is too slow for odd $n > 11$.

Answer 1

What you're trying to do is find the vector in the solution space with the minimum Hamming weight. Unfortunately, this problem is equivalent to the minimum distance problem in coding theory, which has been proven to be NP-hard (http://people.math.umass.edu/~hajir/m499c/vardy-complexity.pdf). That said, the implementation you link to can be sped up greatly by using ints as bit arrays and using bitwise operations, effectively parallelizing many of the operations.
Here's the quick-and-dirty Java solution I wrote for the Google Foobar challenge, which runs reasonably quickly and works for n <= 15.

public class GridZero 
{
    public static int[][] returnn3()
    {
        final int[][] n3={{284}, {149}, {78}, {63}};
        return n3;
    }
    public static int[][] returnn5()
    {
        final int[][] n5= {{17284592}, {8659223}, {4329627}, {2164829}, {1082430}, {1015839}, {31775}, {1023}};
        return n5;
    }
    public static int[][] returnn7()
    {
        final int[][] n7={{-2130838537, 122816}, {1082196484, 4191}, {541098242, 2159}, {270549121, 1143}, {135274560, 66171}, {67637280,  33149}, {33818640, 16638}, {33292288, 127}, {260096, 127}, {2032, 127}, {15, 114815}, {0, 16383}};
        return n7;
    }
    public static int[][] returnn9()
    {
        final int[][] n9={{-2143297553, -134480386, 130816}, {1075843080, 67240192, 
              65919}, {537921540, 33620096, 33215}, {268960770, 16810048, 
                  16863}, {134480385, 8405024, 8687}, {67240192, -2143281136, 
                  4599}, {33620096, 1075843080, 2555}, {16810048, 537921540, 
                  1533}, {8405024, 268960770, 1022}, {8372224, 0, 511}, {16352, 0, 
                  511}, {31, -268435456, 511}, {0, 267911168, 511}, {0, 523264, 
                  511}, {0, 1022, 511}, {0, 1, 131071}};
        return n9;
    }
    public static int[][] returnn11()
    {
        final int[][] n11= {{-2146435585, -1074266369, -537133185, 31456256}, {1074266368, 
              537133184, 268566592, 1050111}, {537133184, 268566592, 134283296, 
                  526079}, {268566592, 134283296, 67141648, 264063}, {134283296, 
                  67141648, 33570824, 133055}, {67141648, 33570824, 16785412, 
                  67551}, {33570824, 16785412, 8392706, 34799}, {16785412, 8392706, 
                  4196353, 18423}, {8392706, 4196353, 2098176, 16787451}, {4196353, 
                  2098176, -2146434560, 8394749}, {2098176, -2146434560, 1074266368, 
                  4198398}, {2096128, 0, 0, 2047}, {1023, -2147483648, 0, 2047}, {0, 
                  2146435072, 0, 2047}, {0, 1048064, 0, 2047}, {0, 511, -1073741824, 
                  2047}, {0, 0, 1073217536, 2047}, {0, 0, 524032, 2047}, {0, 0, 255, 
                  29362175}, {0, 0, 0, 4194303}};
        return n11;
    }
    public static int[][] returnn13()
    {
        final int[][] n13={{-2147221537, -16779265, -1073872913, -8389633, -536936456, 
              0}, {1073872912, 8389632, 536936456, 4194816, 268468235, 
                  511}, {536936456, 4194816, 268468228, 2097408, 134234125, 
                  511}, {268468228, 2097408, 134234114, 1048704, 67117070, 
                  511}, {134234114, 1048704, 67117057, 524352, 33558543, 
                  255}, {67117057, 524352, 33558528, -2147221472, 16779279, 
                  383}, {33558528, -2147221472, 16779264, 1073872912, 8389647, 
                  447}, {16779264, 1073872912, 8389632, 536936456, 4194831, 
                  479}, {8389632, 536936456, 4194816, 268468228, 2097423, 
                  495}, {4194816, 268468228, 2097408, 134234114, 1048719, 
                  503}, {2097408, 134234114, 1048704, 67117057, 524367, 
                  507}, {1048704, 67117057, 524352, 33558528, -2147221457, 
                  509}, {524352, 33558528, -2147221472, 16779264, 1073872927, 
                  510}, {524224, 0, 0, 0, 15, 511}, {63, -33554432, 0, 0, 15, 
                  511}, {0, 33550336, 0, 0, 15, 511}, {0, 4095, -2147483648, 0, 15, 
                  511}, {0, 0, 2147221504, 0, 15, 511}, {0, 0, 262112, 0, 15, 
                  511}, {0, 0, 31, -16777216, 15, 511}, {0, 0, 0, 16775168, 15, 
                  511}, {0, 0, 0, 2047, -1073741809, 511}, {0, 0, 0, 0, 1073610767, 
                  511}, {0, 0, 0, 0, 131071, 511}};
        return n13;
    }
    public static int[][] returnn15()
    {
        final int[][] n15={{-2147418115, -262153, -1048609, -4194433, -16777729, -67110913,
            -268443648, 0}, {1073774593, 131076, 524304, 2097216, 8388864, 
                  33555456, 134230015, 1}, {536887296, -2147418110, 262152, 1048608, 
                  4194432, 16777728, 67123199, 1}, {268443648, 1073774593, 131076, 
                  524304, 2097216, 8388864, 33569791, 1}, {134221824, 
                  536887296, -2147418110, 262152, 1048608, 4194432, 16793087, 
                  1}, {67110912, 268443648, 1073774593, 131076, 524304, 2097216, 
                  8404735, 1}, {33555456, 134221824, 536887296, -2147418110, 262152, 
                  1048608, 4210559, 1}, {16777728, 67110912, 268443648, 1073774593, 
                  131076, 524304, 2113471, 1}, {8388864, 33555456, 134221824, 
                  536887296, -2147418110, 262152, 1064927, 1}, {4194432, 16777728, 
                  67110912, 268443648, 1073774593, 131076, 540655, 1}, {2097216, 
                  8388864, 33555456, 134221824, 536887296, -2147418110, 278519, 
                  1}, {1048608, 4194432, 16777728, 67110912, 268443648, 1073774593, 
                  147451, 1}, {524304, 2097216, 8388864, 33555456, 134221824, 
                  536887296, -2147401731, 1}, {262152, 1048608, 4194432, 16777728, 
                  67110912, 268443648, 1073790974, 1}, {131076, 524304, 2097216, 
                  8388864, 33555456, 134221824, 536903679, 0}, {131068, 0, 0, 0, 0, 0,
                   16383, 1}, {3, -524288, 0, 0, 0, 0, 16383, 1}, {0, 524272, 0, 0, 0,
                   0, 16383, 1}, {0, 15, -2097152, 0, 0, 0, 16383, 1}, {0, 0, 2097088,
                   0, 0, 0, 16383, 1}, {0, 0, 63, -8388608, 0, 0, 16383, 1}, {0, 0, 0,
                   8388352, 0, 0, 16383, 1}, {0, 0, 0, 255, -33554432, 0, 16383, 
                  1}, {0, 0, 0, 0, 33553408, 0, 16383, 1}, {0, 0, 0, 0, 
                  1023, -134217728, 16383, 1}, {0, 0, 0, 0, 0, 134213632, 16383, 
                  1}, {0, 0, 0, 0, 0, 4095, -536854529, 1}, {0, 0, 0, 0, 0, 0, 
                  536870911, 1}};
        return n15;
    }


    public static int answer(int[][] matrix)
    {
        int[][] tm = toggleGen(matrix.length,matrix);
        int[][] mat = rref(tm);
        int zeroRow = mat.length;
        for (int i = mat.length - 1; i >=0; i--)
        {
            int status = 0;
            for (int j = 0; j < mat[0].length - 1; j++)
            {
                if (mat[i][j] == 1)
                {
                    status = 1;
                    break;
                }
            }
            if (status == 1) 
            {
                zeroRow = i+1;
                break;
            }
            else if (mat[i][mat[0].length-1] == 0) continue;
            else return -1;
        }
            int offset = 0;
            int changecheck = 0;
            int zeroRowcopy = zeroRow;
            for (int r = 0; r < zeroRowcopy; r++)
            {
                if (mat[r][r+offset] == 1) continue;
                else
                {
                    changecheck = 1;
                    mat[zeroRow++][r + offset] = 1;
                    offset++;   
                }
            }
        if (changecheck == 1) mat = rref(mat);


        int len = mat.length/32 + 1;
        if (mat.length % 32 == 0) len--;
        final int[] sol = new int[len];
        int weight = 0;
        for (int i = 0; i < mat.length; i++)
        {
            int val = mat[i][mat[0].length-1];
            sol[i/32] = (sol[i/32] << 1) | val;
            weight += val;
        }


        if (matrix.length % 2 == 0) return weight;
        final int[][] kernel;
        switch (matrix.length)
        {
        case 3: kernel = returnn3();
                break;
        case 5: kernel = returnn5();
                break;
        case 7: kernel = returnn7();
                break;
        case 9: kernel = returnn9();
                break;
        case 11: kernel = returnn11();
                break;
        case 13: kernel = returnn13();
                break;
        case 15: kernel = returnn15();
                break;
        default:
            kernel = returnn3();
        }
        int max = 1 << (2*(matrix.length-1));

        int minweight = weight;
        int res[] = new int[sol.length];
        for (int i = 1; i < max; i++)
        {
            int hamming = basisweighter(kernel,i,sol,res);
            if (hamming < minweight)
            {
                minweight = hamming;
            }

        }



        return minweight;

    }
    public static int basisweighter(final int[][] kernel, int weights, final int[] sol, int[] res)
    {
        int changes = weights ^ (weights-1);
        int changeint;
        int i = 0;

        while ((changeint = (changes >> i)) > 0)
        {
            if ((changeint & 1) == 1)
            {
                for (int k = 0; k < res.length; k++)
                {
                    res[k] ^= kernel[i][k];

                }
            }
            i++;
        }
        int weight = 0;
        for (int j = 0; j < sol.length; j++)
        {
            weight += NumberOfSetBits(res[j]^sol[j]);
        }
        return weight;

    }
    public static int NumberOfSetBits(int i)
    {
         i = i - ((i >>> 1) & 0x55555555);
         i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
         return (((i + (i >>> 4)) & 0x0F0F0F0F) * 0x01010101) >>> 24;
    }
    public static int[][] toggleGen(int n, int[][] mat)
    {
        int[][] ret = new int[n*n][n*n+1];
        for (int i = 0; i < n*n; i++)
        {
            int[] row = new int[n*n+1];
            for (int j = 0; j <= n*n; j++)
            {
                if (j == n*n)
                    row[j] = mat[i/n][i%n];
                else if (i/n == j/n)
                    row[j] = 1;
                else if (i%n == j%n)
                    row[j] = 1;
                else
                    row[j] = 0;
            }
            ret[i] = row;
        }
        return ret;
    }
    public static int[][] rref(int[][] mat)
    {
        int[][] rref = new int[mat.length][mat[0].length];
        int startRow = 0;
        for (int r = 0; r < rref.length; ++r)
        {
            for (int c = 0; c < rref[r].length; ++c)
            {
                rref[r][c] = mat[r][c];
            }
        }

        for (int c = 0; c < rref[0].length; ++c)
        {
            int pivotRow = -1;
            for (int r = startRow; r < rref.length; ++r)
            {
                if (rref[r][c] == 1)
                {
                    pivotRow = r;
                    break;
                }
            }
            if (pivotRow == -1) continue;
            if (pivotRow != startRow)
            {
                int[] temp = rref[pivotRow];
                rref[pivotRow] = rref[startRow];
                rref[startRow] = temp;
            }
            for (int r = 0; r < rref.length; r++)
            {
                if (r == startRow) continue;
                if(rref[r][c] == 1)
                {
                    for (int i = 0; i < rref[0].length; i++)
                    {
                        rref[r][i] ^= rref[startRow][i];
                    }
                }
            }
            startRow++;


        }

        return rref;
    }

}