function W = solver(B)

% gettingBetter3: start with most valuable nets, not highest voltages
% gettingBetter2: multiple nets
% gettingBetter: bring mutiple pins into the network
% wifi2: keep track of voltage to avoid crossings

V=B;    % voltage map

Bv = B(:);
sizeB = size(B);
W = zeros(0,4);

BvNZ = Bv(logical(Bv));   % non-zero elements

pinIDs = sort(unique(BvNZ),'descend');
nIDs = numel(pinIDs);    % there is always a zero in the list

% evaluate total value of each net
for i=1:nIDs
    totalV(i) = sum(Bv(Bv==pinIDs(i)));
end

[totalV,isort] = sort(totalV,'descend');
pinIDs=pinIDs(isort);

if isempty (pinIDs) return; end


% loop over possible nets
for i=1:nIDs

    % start with the highest-valued group (first in the list)
    pinID = pinIDs(i);

    % number of pins in this net
    nPins = sum(BvNZ==pinID);
    if nPins<=1
        continue
    end
    livePins = false(nPins,1);    % true for pins that are connected

    %locations of pins in this net
    pinLocs2D = zeros(nPins,2);

    pinLocs1D = find(Bv==pinID);
%     for j=1:nPins
%         [pinLocs2D(j,1),pinLocs2D(j,2)] = ind2sub(sizeB,pinLocs1D(j));   % this could probably be faster
%     end
    % next 2 lines are indeed MUCH faster than ind2sub
    pinLocs2D(:,2) = floor((pinLocs1D-1)/sizeB(1))+1;
    pinLocs2D(:,1) = pinLocs1D -  (pinLocs2D(:,2)-1)*sizeB(1); 

    % Get the net started
    % Find the pin nearest the centroid, and find something to connect it to

    % find centroid of the prospective net:
    ic=sum(pinLocs2D(:,1))/nPins; 
    jc=sum(pinLocs2D(:,2))/nPins; 

    % distance from each pin to centroid:
    cdist = abs(ic-pinLocs2D(:,1)) + abs(jc-pinLocs2D(:,2));
    
    for k=1:3
        % These 3 attempts to start a net are costly - 50% time increase
        % for a 3% score descrease wrt to a single shot.
        if k==1 % first attempt: pick the pin nearest the centroid of the net
            [cdistMin,iPin] = min(cdist);
        elseif k==2  % 2nd attempt: mid-range
            [cdistMin,iPin] = min(cdist-mean(cdist));
        elseif k==3   % 3rd attempt: outlier
            [cdistMin,iPin] = max(cdist);
        end

        % for the first pin on the list, just find its nearest neighbour and connect them
        % iPin = 1;   % first pin in the net
        %staircase distance from pin1 to every other pin
        dist = sum(abs(pinLocs2D(iPin*ones(nPins,1),:) - pinLocs2D),2);
        dist(iPin) = Inf;
        wLink=[];
        while isempty(wLink) && any(dist<Inf)
            [distMin,iTarget] = min(dist);
            [wLink,V] = pathfinder1(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V);
            dist(iTarget) = Inf;   % don't check last target pin again
        end
        if any(wLink)
            W=[W; wLink];
            livePins(iPin)=1;
            livePins(iTarget)=1;
            break
        end
    end
    
    % now loop over all pins, and for ones that aren't live, try to connect them. 
    
    % compute distance matrix
%     D = abs (repmat(pinLocs2D(:,1),[1 nPins]) - repmat(pinLocs2D(:,1)',[nPins 1])) + ...
%         abs (repmat(pinLocs2D(:,2),[1 nPins]) - repmat(pinLocs2D(:,2)',[nPins 1])) ; 
%     D = abs ( pinLocs2D(:,ones(1,nPins)) - pinLocs2D(:,ones(1,nPins))' ) + ...
%         abs ( pinLocs2D(:,2*ones(1,nPins)) - pinLocs2D(:,2*ones(1,nPins))' ) ; 
    
%     D(~livePins,:) = Inf;
%     D(:,~livePins) = Inf;
    D(logical(eye(nPins)))=Inf;
    
    % THIS IS SLOW
    if any(livePins)    % For now, only do this if we've already succeeded on the first connection (but that's STUPID).
        for k=1:4  % multiple passes may help
            for iPin=1:nPins
                if livePins(iPin)
                    continue
                end
                % staircase distance to all other pins
                dist = sum(abs(pinLocs2D(iPin*ones(nPins,1),:) - pinLocs2D),2);
                dist(iPin) = Inf;
                dist(~livePins)=Inf;
                [distMin,iTarget] = min(dist);
%                 [wLink,V] = pathfinder1(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V);
        wLink=[];
        while isempty(wLink) && any(dist<Inf)
            [distMin,iTarget] = min(dist);
            [wLink,V] = pathfinder1(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V);
            dist(iTarget) = Inf;   % don't check last target pin again
        end

                if any(wLink)
                    W=[W; wLink];
                    livePins(iPin)=1;
                    livePins(iTarget)=1;  % this shouldn't be necessary
                end
            end
        end
    end
end


return


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [W,V] = pathfinder1(loc1,loc2,V);

% return a series of moves (links) from loc1 to loc2 on the board B
% this is pathfinder 1 - looks for simple horiz and vert paths only

i1=loc1(1);
j1=loc1(2);
i2=loc2(1);
j2=loc2(2);

W=[];

v = V(i1,j1);  % "voltage"
V0 = V;
V0(V==v) = 0;    % zero out locations at the same voltage we are at - we can safely run wires through them

% check for very special case - pins are adjacent
if abs(i1-i2)+abs(j1-j2)==1   
    W = [i1 j1 i2 j2]; 
    V = updateV(V,W,v);
    return
end

% less special - on the same row
if i1==i2
    if j2<j1
        t=j1; j1=j2; j2=t;          t=i1; i1=i2; i2=t;  
        %[j2,j1]=copyVar(j1,j2); [i2,i1]=copyVar(i1,i2);
    end
    if sum(V0(i1,j1+1:j2-1)) == 0    % clear path between them
        L = ones(j2-j1,1);   % length of path
        W = [ i1*L (j1:j2-1)' i2*L (j1+1:j2)' ];
        V = updateV(V,W,v);
        return
    else
        return
    end
end

% less special - on the same column
if j1==j2
    if i2<i1
        t=j1; j1=j2; j2=t;          t=i1; i1=i2; i2=t;  
        %         [j2,j1]=copyVar(j1,j2); [i2,i1]=copyVar(i1,i2);
    end
    if sum(V0(i1+1:i2-1,j1)) == 0    % clear path between them
        L = ones(i2-i1,1);   % length of path
        W = [ (i1:i2-1)' j1*L (i1+1:i2)' j2*L ];
        V = updateV(V,W,v);
        return
    else
        return
    end
end

% if we get this far, pins are not on the same row or col. 
% Try the 2 possible routes around the sides of a rectangle, using this function
% recursively to get to the corner.

if ~V0(i1,j2)
    [W1,V1] = pathfinder1([i1 j1],[i1 j2],V);
    if any(W1)
        [W2,V2] = pathfinder1([i1 j2],[i2 j2],V1);
        if any(W2)
            W=[W1; W2];
            V = V2;
            return
        end
    end
elseif ~V0(i2,j1)
    [W1,V1] = pathfinder1([i1 j1],[i2 j1],V);
    if any(W1)
        [W2,V2] = pathfinder1([i2 j1],[i2 j2],V1);
        if any(W2)
            W=[W1; W2];
            V =V2; %= updateV(V,W,v);
            return
        end
    end
end

% if we get this far, we've failed

return % end of pathfinder1
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



function V = updateV(V,W,v)
% Update the voltage map with a new set of connectors.
n = size(W,1);
%v = V(W(1,1),W(1,2));

V(W(1,1),W(1,2))=v;
% this loop could be faster
for i=1:n;
    V(W(i,3),W(i,4)) = v;
end

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function[b1,b2] = copyVar(a1,a2)
b1=a1;
b2=a2;
return