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


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


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


  • 3
    \$\begingroup\$ What to do in case the puzzle is unsolvable? E.g. 1000 (rearranged as a square, doesn't matter how). \$\endgroup\$
    – orlp
    Dec 4, 2015 at 15:08
  • 2
    \$\begingroup\$ Related. \$\endgroup\$ Dec 4, 2015 at 15:42
  • \$\begingroup\$ @orlp Any output that is not a number will do. \$\endgroup\$ Dec 4, 2015 at 15:43
  • \$\begingroup\$ Do we need to parse the input or can it be any already filled array datatype? \$\endgroup\$
    – coredump
    Dec 4, 2015 at 16:11
  • 1
    \$\begingroup\$ What is the solution to the first test case? I'm getting no solutions for it. \$\endgroup\$ Dec 4, 2015 at 23:09

2 Answers 2


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.


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)
M=inf;                                               %current minimum of number of moves
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
        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)

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;
@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";

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.