function W = solver(B)

% gettingBetter13: maze for initiation
% gettingBetter11: terminate pathfinder1 routes if we run into a live line
% gettingBetter10: "voltage" is only on when pins are part of a net
% gettingBetter9: better maze search - cut corners
% gettingBetter8: maze search to bring more points into net
% gettingBetter7: no maze. submitted as      the same, only more so
% 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 - voltage that location has IF it's connected - i.e. unwired pins have value
Vlive=0*V;  % voltage if live - unwired pins have zero

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)
    pinVal = pinIDs(i);

    % number of pins in this net
    nPins = sum(BvNZ==pinVal);
    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==pinVal);
%     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); 

    if nPins==2
        [wLink,V,Vlive] = pathfinder1(pinLocs2D(1,:), pinLocs2D(2,:), V,Vlive,pinVal);
        if any(wLink)
            W = [W; wLink];
        end
        continue
    end

    
    % 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(abs(cdist-mean(cdist)));
        elseif k==3   % 3rd attempt: outlier
            [cdistMin,iPin] = max(cdist);
        end

        %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,Vlive] = pathfinder1(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V, Vlive, pinVal);
            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

        % Still here? we failed to initiate. try with maze solver.
        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,Vlive] = maze(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V, Vlive);
            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
    

%     if isempty(W)   % failed to initiated? try with maze search
%         
%     end
    
    % 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;
 
 
        % now loop over all pins, and for ones that aren't live, try to connect them. 
    % Now roam over all unconnected pins and try to get them into the net
    % 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       %loop over all pins
                if livePins(iPin)  % ignore pins that are wired up
                    continue
                end
                dist = sum(abs(pinLocs2D(iPin*ones(nPins,1),:) - pinLocs2D),2);      % staircase distance to all other pins
                dist(iPin) = Inf;
                dist(~livePins)=Inf;   % don't connect pin to itself or non-wired pins
                [distMin,iTarget] = min(dist);
                %                 [wLink,V] = pathfinder1(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V);
                wLink=[];
                % This loop works through all possible target pins
                while isempty(wLink) && any(dist<Inf)
                    [distMin,iTarget] = min(dist);
                    [wLink,V,Vlive] = pathfinder1(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V, Vlive, pinVal);
                    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

    % repeat the exercise, using maze search
    if any(livePins) && 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       %loop over all pins
            if livePins(iPin)  % ignore pins that are wired up
                    continue
                end
                % recomputing distance here is a bit wasteful - could be smarter
                dist = sum(abs(pinLocs2D(iPin*ones(nPins,1),:) - pinLocs2D),2);      % staircase distance to all other pins
                dist(iPin) = Inf;
                dist(~livePins)=Inf;   % don't connect pin to itself or non-wired pins
   %             [distMin,iTarget] = min(dist);
                wLink=[];
                % This loop works through all possible target pins
                while isempty(wLink) && any(dist<Inf)
                    [distMin,iTarget] = min(dist);
                    [wLink,V,Vlive] = maze(pinLocs2D(iPin,:), pinLocs2D(iTarget,:), V, Vlive);
                    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  % for k=1:4
    end

end


return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [W,V,Vlive]=maze(loc1,loc2,V,Vlive)

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

B=V;
B(logical(V))=1;
v=V(i1,j1); 
B(V==v)=0;   % ok to pass through points at our voltage
sizeB=size(B);
% at this stage B is a binary map - 0=allowed, 1=off-limits


% pad board with a wall of ones, set up some auxiliary boards
B1=ones(sizeB+[2 2]);
T1 = B1-1;    % trail map - entries will show the sequence number on the trail
V1=-B1;      % padded voltage map
B1(2:sizeB(1)+1,2:sizeB(2)+1) = B;
V1(2:sizeB(1)+1,2:sizeB(2)+1) = Vlive;


i1=i1+1;j1=j1+1;i2=i2+1;j2=j2+1;


W=zeros(0,4);
dsq = (i1-i2)^2+(j1-j2)^2;
keepgoing=true;

% values of B
% 0: available
% 1: off limits
% 2: explored and rejected
% 3: behind us on current track

B1(i1,j1)=3;

i=i1;j=j1;
moves=false(1,4);

% moves are right up left down
diMoves = [0 -1 0 1];
djMoves = [1 0 -1 0];

trail=zeros(1000,2);
trail(1,:) = [i1 j1];
nTrail=1;
T1(i1,j1) = 1;

arrived=false;

while 1
    % moves are right up left down
    moves = ~[B1(i,j+1) B1(i-1,j) B1(i,j-1) B1(i+1,j)];
    % no move available? 
    if ~any(moves) 
        if nTrail==1 % at square 1 with nowhere to go - failure
            break
        end
        B1(i,j)=2;   % mark the square as a reject
        T1(i,j)=0;  
        nTrail = nTrail-1;  % backtrack
        i=trail(nTrail,1);
        j=trail(nTrail,2);
    else
        % signed distances to destination
        Di = i2-i;
        Dj = j2-j;
%         newDist = abs(Di-diMoves) + abs(Dj-djMoves);
%         newDist(~moves) = Inf;
%         [minDist,iMove] = min(newDist);
        newDsq = (Di-diMoves).^2 + (Dj-djMoves).^2;
         newDsq(~moves) = Inf;
         [minDsq,iMove] = min(newDsq);
        i = i + diMoves(iMove);
        j = j + djMoves(iMove);
        nTrail=nTrail+1;
        trail(nTrail,:)=[i j];
        T1(i,j)=nTrail;
        B1(i,j) = 3;
        % see if we're adjacent to any visited location other than our last stop - if so, shorten the trail:
        [trail,nTrail,T1] = shortCut(i,j,trail,nTrail,T1);
        % !!!TODO!!! insert a check here for clear line-of-sight to destination
        %            or maybe to any point of target voltage
        if V1(i,j)==v || (i==i2 && j==j2)
            arrived=true;
            break;
        end
    end
%     dsq = (i-i2)^2+(j-j2)^2;
%     % we have at most 4 possible moves
%     dx1 = sign (i2-i); 
%     dy1 = sign(j2-j);
%     if abs(dx)>abs(dy) 
%         dx=dx1;
%         dy=0;
%     elseif abs(
end

if arrived
    W=zeros(nTrail-1,4);
    W(:,1) = trail(1:nTrail-1,1);
    W(:,2) = trail(1:nTrail-1,2);
    W(:,3) = trail(2:nTrail,1);
    W(:,4) = trail(2:nTrail,2);
    W=W-1; % correct for initial padding of board
    [V,Vlive] = updateV(V,Vlive,W,V(i1-1,j1-1));

else
    W=[];
end

return
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [trail,nTrail,T1] = shortCut(i,j,trail,nTrail,T1);
% Check if we're adjacent to any visited location other than our very last
% stop - if so, shorten the trail.
%
% !!!!!TODO!!!!!! NEED TO CHECK WE don't cut out GOOD PINS we visited ON THE WAY
if T1(i-1,j)>0 && T1(i-1,j)<nTrail-1
    iTrail = T1(i-1,j);  % step number on trail
    for k= iTrail+1:nTrail
        T1(trail(k,1),trail(k,2))=0;
    end
    nTrail=iTrail+1;
    trail(nTrail,:) = [i j];
    T1(i,j)=nTrail;
elseif T1(i+1,j)>0 && T1(i+1,j)<nTrail-1
    iTrail = T1(i+1,j);  % step number on trail
    for k= iTrail+1:nTrail
        T1(trail(k,1),trail(k,2))=0;
    end
    nTrail=iTrail+1;
    trail(nTrail,:) = [i j];
    T1(i,j)=nTrail;
elseif T1(i,j-1)>0 && T1(i,j-1)<nTrail-1
    iTrail = T1(i,j-1);  % step number on trail
    for k= iTrail+1:nTrail
        T1(trail(k,1),trail(k,2))=0;
    end
    nTrail=iTrail+1;
    trail(nTrail,:) = [i j];
    T1(i,j)=nTrail;
elseif T1(i,j+1)>0 && T1(i,j+1)<nTrail-1
    iTrail = T1(i,j+1);  % step number on trail
    for k= iTrail+1:nTrail
        T1(trail(k,1),trail(k,2))=0;
    end
    nTrail=iTrail+1;
    trail(nTrail,:) = [i j];
    T1(i,j)=nTrail;
end
return

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

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

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

W=[];

okLocs = V>0 & V~=v;


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

dir=1;

% less special - on the same row
if i1==i2
    if j2<j1
        t=j1; j1=j2; j2=t;          
        t=i1; i1=i2; i2=t;  
        dir = -1;
        %[j2,j1]=copyVar(j1,j2); [i2,i1]=copyVar(i1,i2);
    end
    if sum(okLocs(i1,j1+1:j2-1))==0     % clear path between them
        if dir==-1
            if any(Vlive(i1,j1+1:j2-1)==v)
                j1 = j1+find(Vlive(i1,j1+1:j2-1)==v,1,'last');   % stop if we hit a live wire before our destination
            end
        else
            if any(Vlive(i1,j1+1:j2-1)==v)
                j2 = j1+find(Vlive(i1,j1+1:j2-1)==v,1,'first');   % stop if we hit a live wire before our destination
            end
        end
         L = ones(j2-j1,1);   % length of path
       W = [ i1*L (j1:j2-1)' i2*L (j1+1:j2)' ];
        [V,Vlive] = updateV(V,Vlive,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;  
        dir = -1;
    end
    if sum(okLocs(i1+1:i2-1,j1)) == 0    % clear path between them
        if dir==-1
            if any(Vlive(i1+1:i2-1,j1)==v)
                i1 = i1+find(Vlive(i1+1:i2-1,j1)==v,1,'last');   % stop if we hit a live wire before our destination
            end
        else
            if any(Vlive(i1+1:i2-1,j1)==v)
                i2 = i1+find(Vlive(i1+1:i2-1,j1)==v,1,'first');   % stop if we hit a live wire before our destination
            end
        end
        L = ones(i2-i1,1);   % length of path
        W = [ (i1:i2-1)' j1*L (i1+1:i2)' j2*L ];
        [V,Vlive] = updateV(V,Vlive,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 ~okLocs(i1,j2)
    [W1,V1,Vl1] = pathfinder1([i1 j1],[i1 j2],V,Vlive,v);
    if any(W1)
        [W2,V2,Vl2] = pathfinder1([i1 j2],[i2 j2],V1,Vl1,v);
        if any(W2)
            W=[W1; W2];
            V = V2;
            Vlive = Vl2;
            return
        end
    end
end
if isempty(W) && ~okLocs(i2,j1)
    [W1,V1,Vl1] = pathfinder1([i1 j1],[i2 j1],V,Vlive,v);
    if any(W1)
        [W2,V2,Vl2] = pathfinder1([i2 j1],[i2 j2],V1,Vl1,v);
        if any(W2)
            W=[W1; W2];
            V =V2; 
            Vlive = Vl2;
            return
        end
    end
end

% if we get this far, pathfinder1 has failed 

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



function [V,Vlive] = updateV(V,Vlive,W,v)
% Update the voltage map with a new set of connectors.
% We need to be told the voltage (pin value) v because the order of links is
% unreliable - we can't infer it from that. 
n = size(W,1);
%v = V(W(1,1),W(1,2));

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

return

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

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