function W = solver(B)
%set(0,'RecursionLimit',10000)
%W = zeros(0,4);

%first let's find all pin pairs
[pin_value, pin1sub, pin2sub, minscore]  = list_pin_pairs(B);

%define a null_value 
null_value = -(max(unique(pin_value)) + 1);

i = 1;
map = B;
B_filled = B;
while i <= length(minscore) && minscore(i) < 0
    [mapout,success,npins] = grow_path(map,pin1sub(i,1),pin1sub(i,2),pin2sub(i,1),pin2sub(i,2),null_value,0);
    if success
        if (npins - 1) < (B_filled(pin1sub(i,1),pin1sub(i,2)) + B_filled(pin2sub(i,1),pin2sub(i,2)))
            %this move improved score so we keep it
            map(mapout == -pin_value(i)) = pin_value(i);
            B_filled(pin1sub(i,1),pin1sub(i,2)) = 0;
            B_filled(pin2sub(i,1),pin2sub(i,2)) = 0;
        end
    end
    i = i+1;
end
W = list_edges(map);

   
function [pin_value, pin1sub, pin2sub, minscore]  = list_pin_pairs(B)

pin_value = [];
pin1idx = [];
pin2idx = [];
minscore = [];
npairs = 0;


pins_unique = unique(B(B>0));
npins_unique = length(pins_unique);
pin_count = pins_unique*0;
for i = 1:length(pins_unique)
    a = find(B(:) == pins_unique(i));
    pin_count(i) = length(a);
    for pin1 = 1:pin_count(i) - 1
        for pin2 = pin1 + 1: pin_count(i)
            npairs = npairs + 1;
            pin_value(npairs,1) = B(a(pin1));
            pin1idx(npairs,1) = a(pin1);
            pin2idx(npairs,1) = a(pin2);
        end
    end
end
[x,y] = ind2sub(size(B),pin1idx);
pin1sub = [x y];
[x,y] = ind2sub(size(B),pin2idx);
pin2sub = [x y];
d = sum(abs(pin1sub - pin2sub),2);
minscore = d - 2*pin_value;
[a,ai] = sort(minscore,'ascend');

minscore = minscore(ai);
pin_value = pin_value(ai);
pin1sub = pin1sub(ai,:);
pin2sub = pin2sub(ai,:);



function [map,success,npins,rdepth] = grow_path(map,i0,j0,i1,j1,null_value,rdepth)

if rdepth == 499
    map(i0,j0) = null_value;
    success = 0;
    npins = 0;
    return
else
    rdepth = rdepth + 1;
end
[ni,nj] = size(map);
dj = j1 - j0; %the distance from source to target in j
di = i1 - i0; % the distance from source to target in i



%we try stepping left or right, or up or down trying to get in the
%direction of the target

n = map(i0,j0);
stepj = sign(dj+.1);
stepi = sign(di+.1);
npins = 0;
map(i0,j0) = -n; %prevent backtracking and looping
if dj == 0 && di == 0
    success = 1;
    npins = sum(map(:) == -n);
    return;
end
if abs(dj) >= abs(di) %try move in j first
    %try moving in j direction
    if (j0 + stepj > 0 && j0 + stepj <= nj) &&...
            (map(i0,j0 + stepj) == 0 || map(i0,j0 + stepj) == n)
        %this is a valid step
        map(i0,j0 + stepj) = n;
        [map,success,npins,rdepth] = grow_path(map,i0,j0 + stepj,i1,j1,null_value, rdepth);
        if success, return, end
    end
    %the j failed, try the i
    if (i0 + stepi > 0 && i0 + stepi <= ni) &&...
            (map(i0 + stepi,j0) == 0 || map(i0 + stepi,j0) == n)
        %this is a valid step
        map(i0 + stepi,j0) = n;
        [map,success,npins,rdepth] = grow_path(map,i0 + stepi,j0,i1,j1,null_value, rdepth);
        if success, return, end
    end
    % the i step failed, so let's try the negative i
    stepi = -stepi;
    if (i0 + stepi > 0 && i0 + stepi <= ni) &&...
            (map(i0 + stepi,j0) == 0 || map(i0 + stepi,j0) == n)
        %this is a valid step
        map(i0 + stepi,j0) = n;
        [map,success,npins,rdepth] = grow_path(map,i0 + stepi,j0,i1,j1,null_value, rdepth);
        if success, return, end
    end
    %the negative i step failed, so finally let's try the negative j
    stepj = - stepj;
    if (j0 + stepj > 0 && j0 + stepj <= nj) &&...
            (map(i0,j0 + stepj) == 0 || map(i0,j0 + stepj) == n)
        %this is a valid step
        map(i0,j0 + stepj) = n;
        [map,success,npins,rdepth] = grow_path(map,i0,j0 + stepj,i1,j1,null_value, rdepth);
        if success, return, end
    end
    %all routes from here are failures, so mark this square as a failure
    map(i0,j0) = null_value;
    success = 0;
    return
else
    %the i direction has the farthest to go, so let's try that
    if (i0 + stepi > 0 && i0 + stepi <= ni) &&...
            (map(i0 + stepi,j0) == 0 || map(i0 + stepi,j0) == n)
        %this is a valid step
        map(i0 + stepi,j0) = n;
        [map,success,npins,rdepth] = grow_path(map,i0 + stepi,j0,i1,j1,null_value, rdepth);
        if success, return, end
    end
    %the i step failed, try moving in j direction
    if (j0 + stepj > 0 && j0 + stepj <= nj) &&...
            (map(i0,j0 + stepj) == 0 || map(i0,j0 + stepj) == n)
        %this is a valid step
        map(i0,j0 + stepj) = n;
        [map,success,npins,rdepth] = grow_path(map,i0,j0 + stepj,i1,j1,null_value, rdepth);
        if success, return, end
    end
    %the j failed, try the negative j step
    stepj = - stepj;
    if (j0 + stepj > 0 && j0 + stepj <= nj) &&...
            (map(i0,j0 + stepj) == 0 || map(i0,j0 + stepj) == n)
        %this is a valid step
        map(i0,j0 + stepj) = n;
        [map,success,npins,rdepth] = grow_path(map,i0,j0 + stepj,i1,j1,null_value, rdepth);
        if success, return, end
    end

    % the negative j step failed, so finally let's try the negative i
    stepi = -stepi;
    if (i0 + stepi > 0 && i0 + stepi <= ni) &&...
            (map(i0 + stepi,j0) == 0 || map(i0 + stepi,j0) == n)
        %this is a valid step
        map(i0 + stepi,j0) = n;
        [map,success,npins,rdepth] = grow_path(map,i0 + stepi,j0,i1,j1,null_value, rdepth);
        if success, return, end
    end
    %all routes from here are failures, so mark this square as a failure
    map(i0,j0) = null_value;
    success = 0;
    return
end


function W = list_edges(map)
W = zeros(0,4);
pins_unique = unique(map(map(:) ~= 0));

for i = 1:length(pins_unique)
    map_temp = map;
    map_temp(map(:) ~= pins_unique(i)) = 0;
    W_i = list_edges_n(map_temp,pins_unique(i));
    W = [W; W_i];
end


function W = list_edges_n(map,n)
[imax,jmax] = size(map);
W = zeros(0,4);
pin_idx = find(map(:) == n);

for i = 1: (length(pin_idx)-1)
    [i0,j0] = ind2sub([imax,jmax], pin_idx(i));
    %check pin below this pin
    if i0 + 1 <= imax && map(i0+1,j0) == n
        W = [W; [i0 j0 i0+1 j0]];
    end
    %check pin to the right
    if j0 + 1 <= jmax && map(i0,j0+1) == n
        W = [W; [i0 j0 i0 j0+1]];
    end
end