Minimal number of moves needed to solve a "Lights Out" variant
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;
}
}