function W = solver(B)
W = [];
W = squareWalk(W,B);
W = sortrows(unique(W,'rows')); %Remove "duplicate" connections
W = walkTheLine(W,B);
%bestScore = grade(B,W)

%Avoid errors
if(isempty(W))
    W = [1 1 1 1];
end
end

function W = squareWalk(W,B);
groups = unique(B(:));
groups(groups==0)  = [];

for g=1:length(groups)
    [x,y] = find(B == groups(g));
    for i=1:length(x)-1
        ylen = y(i+1)-y(i);
        if(ylen>0)
            W = [W; ones(ylen,1)*x(i) y(i)+(0:ylen-1)' ones(ylen,1)*x(i) y(i)+(1:ylen)'];
        elseif(i<length(x)-2)
            ylen = y(i+2)-y(i);
            W = [W; ones(ylen,1)*x(i) y(i)+(0:ylen-1)' ones(ylen,1)*x(i) y(i)+(1:ylen)'];
        end
    end 
    [y,x] = find(B == groups(g));
    for i=1:length(x)-1
        ylen = y(i+1)-y(i);
        if(ylen>0)
            W = [W; y(i)+(0:ylen-1)' ones(ylen,1)*x(i)  y(i)+(1:ylen)' ones(ylen,1)*x(i) ];
        end
    end

    [x,y] = find(B == groups(g));
    for i=1:length(x)-1
        ylen = y(i+1)-y(i);
        if(ylen>0)
            W = [W;  ones(ylen,1)*x(i+1) y(i+1)-(1:ylen)' ones(ylen,1)*x(i+1) y(i+1)-(0:ylen-1)'];
        end
    end
    [y,x] = find(B == groups(g));
    for i=1:length(x)-1
        ylen = y(i+1)-y(i);
        if(ylen>0)
            W = [W;   y(i+1)-(1:ylen)' ones(ylen,1)*x(i+1) y(i+1)-(0:ylen-1)' ones(ylen,1)*x(i+1)];
        end
    end
end
end

function W = cleanup(W,B)
while(1)
    remove = [];
    idx = sub2ind(size(B),W(:,1),W(:,2));
    idx2 = sub2ind(size(B),W(:,3),W(:,4));
    holes = find(B ~= 0);

    idxtot = [idx;idx2;holes];
    for i=1:length(idx)'
        if( sum(idxtot==idx(i)) == 1)
            remove = [remove i];
        end
        if( sum(idxtot==idx2(i)) == 1)
            remove = [remove i];
        end
    end
    W(remove,:) =[];
    
    if(isempty(remove))
        break;
    end
end
end

function W = cleanup2(W,B)
i=0;
bestScore = grade(B,W);
while i<size(W,1)
    i=i+1;
    W2 = W;
    W2(i,:) = [];
    score = grade(B,W2);
    if( score < bestScore )
        bestScore = score;
        W = W2;
    end
end
end


function groupsInOrder = getGroupsInOrder(B)
groups = unique(B(:));
groups(groups==0)= [];

sums = zeros(size(groups));
for i=1:length(groups(:))
    sums(i) =sum( B(B(:)==groups(i)) );
end

groupsInOrder = sortrows([groups sums],-2);
groupsInOrder = groupsInOrder(:,1);
end





function W_best = walkTheLine(W,B)

groups = getGroupsInOrder(B);

W_best =[];
W_orig = W;
B_orig = B;
remove = zeros(size(W,1),1);
for maxgroup=groups'
    W = W_orig;
    remove = zeros(size(W,1),1);
    for i=1:size(W,1)
        move = W(i,:);
        group = B(move(1),move(2));
        target = B(move(3),move(4));

        %Remove direct connections between different pins
        %     if(target ~= group && target>0 && group>0)
        %         remove = [remove i];
        %     end

        %Remove connections to other that maxgroup
        if((target ~= maxgroup && target ~= 0) || (group ~= maxgroup && group ~= 0) )
            remove(i) = 1;
        end
    end
    
    W(remove==1,:) =[];
    W = cleanup(W,B_orig);
    %W = cleanup2(W,B_orig);
    
        conns = size(W,1);
        gain = sum(B(B(:)== maxgroup));
        if(gain*0.8 >= conns)
            W_best = [W_best; W];
            for i=1:size(W,1)
                move = W(i,:);
                B(move(1),move(2)) = maxgroup;
                B(move(3),move(4)) = maxgroup;
            end
        end

end
%W_best = cleanup2(W_best,B_orig);
%W_best = cleanup(W_best,B_orig);

end