Crack the safe!

Question

Inspired by https://puzzling.stackexchange.com/questions/24334/to-catch-a-thief

You are given an n by n (n itself is optional input) grid filled with 0s and 1s (or any other character of your choice). You aim is to make every cell the same (either 0 or 1). You can make a series of moves as defined below (note dissimilarity with Puzzling SE link):

• Select a cell.
• Every cell in the same row and column (except the cell itself) gets changed into its opposite. 0 to 1 and 1 to 0.

Output the minimum number of moves required to complete the task. If unsolvable, output anything except a non-negative integer. Shortest code wins.

Sample data

1 0 0
0 0 0
0 0 0

-1

1 1 1
1 1 1
1 1 1

0

1 0 1
0 1 0
1 0 1

1

1 1 1 1
0 0 0 0
0 0 0 0
1 1 1 1

2

0 1 0 1
1 0 1 0
1 0 1 0
0 1 0 1

2

Answer 1

Matlab 171 bytes

The input should be a 2d matrix, so you would call it like c([1,1,1,1;0,0,0,0;0,0,0,0;1,1,1,1]) (semicolons start a new row). This function just bruteforces all possible moves, so we get a runtime of O(2^(n^2)).

How it is done

This is done by choosing all possible ways to fill another matrix of the same size with ones and zero, this is basically counting in binary wich where each entry of the matrix represents a certain power of 2.

Then we perform the moves on those cells that are 1, this is done by the sum (mod 2) of two two dimensional convolution with an vector of ones of size 1xn and nx1.

Finally we decide if those moves actually produced the desired result, by computing the standard deviation over all entries. The standard deviation is only zeros if all entries are the same. And whenever we actually found the desired result we compare it with the number of moves of previous solutions. The function will return inf if the given problem is not solvable.

Math?

It is actually worth noting that all those moves together generate an abelian group! If anyone actually manages to calssify those groups please let me know.

Golfed version:

function M=c(a);n=numel(a);p=a;M=inf;o=ones(1,n);for k=0:2^n-1;p(:)=dec2bin(k,n)-'0';b=mod(conv2(p,o,'s')+conv2(p,o','s'),2);m=sum(p(:));if ~std(b(:)-a(:))&m<M;M=m;end;end

Full version (with the output of the actual moves.)

function M = c(a)
n=numel(a);
p=a;
M=inf;                                               %current minimum of number of moves
o=ones(1,n);
for k=0:2^n-1;
    p(:) = dec2bin(k,n)-'0';                         %logical array with 1 where we perform moves
    b=mod(conv2(p,o,'same')+conv2(p,o','same'),2);   %perform the actual moves
    m=sum(p(:));                                     %number of moves;
    if ~std(b(:)-a(:))&m<M                           %check if the result of the moves is valid, and better
        M=m;
        disp('found new minimum:')
        disp(M)                                      %display number of moves of the new best solution (not in the golfed version)
        disp(p)                                      %display the moves of the new best solution                               (not in the golfed version)
    end
end

Answer 2

Perl 5, 498 bytes

This accepts 'n' and the desired result, and outputs the count, or 'X' if none.

For example:

perl ./crack.golf.pl 3 000111111

gives 2. It will only work when n^2 <= 64, so n <= 8. Although it's pretty slow even with n as low as 5. It builds a n^3 bit array, and sorts a 2^(n^2) array beforehand, because why not?

I have wasted a couple of linefeeds here for readability:

$n=shift;$y=shift;$p=$n*$n;@m=(0..$n-1);@q=(0..$p-1);@v=(0..2**$p-1);@d=map{0}(@q);@b=map{$r=$_;map{$c=$_;$d[$r*$n+$_]^=1 for(@m);$d[$_*$n+$c]^=1 for(@m);$j=0;$k=1;
map{$j|=$k*$d[$_];$k<<=1;}@q;@d=map{0}(@q);$j;}@m}@m;for$k(sort{$a->[0]<=>$b->[0]}map{$z=0;map{$z+=$_}split(//,sprintf"%b",$_);[$z,$_]}@v){$l=sprintf"%0${p}b",$k->[1];
@m=map{$_}split(//,$l);$s=0;for(@q){$s^=$b[$_]if$m[$_];}$z=0;map{$z+=$_}split(//,sprintf"%b",$_);if($y eq sprintf"%0${p}b",$s){print"$k->[0]\n";exit 0;}}print"X\n";