%% Main Solver Function
function W = solver3(B)

BB = B; % board's copy
%BB = repmat(B, [1 1 2]); % represent wires and pins together, a bridge
%means a switch in the 3rd dimension from one board to the other
pinNbr = sort(unique(B(B>0)), 'descend');
szB = size(B);
%neighbIdx = [ -1 br 1 -br ]; % [ ^ > v < ]
W = zeros(0,4);
for n = pinNbr.'
    
    pinSet = find(B == n);
    if numel(pinSet) == 1, continue, end; % for connecting purposes ignore pins with only one occurrence

    p = 1;
    pinSetOut = [ pinSet zeros(numel(pinSet),1) ]; % 2nd column: 1 means unable to connected since last wire was added
    w = [];
    while ~all(pinSetOut(:,2)) && isempty(w) && p < size(pinSetOut,1)
        p1 = pinSetOut(p,1);
        [ign, d] = sort(setDist(szB, p1, pinSet), 'ascend'); % first distance will be zero (same point)
        pinSetOut(p,2) = 1; % assume connection attempt is going to fail
        for k = 2:numel(d)
            p2 = pinSet(d(k));
            [w, widx] = elbowConn(BB, p1, p2);
            if ~isempty(w)
                W = [ W; w ];
                BB(widx) = BB(p1); % "paint' wire on board
                pinSet = [ p1; p2; widx(:) ]; % add new "pins', connection points
                pinSetOut([p d(k)],:) = []; % remove endpoints pins from unconnected
                break;
            end
        end
        if ~isempty(pinSetOut) && isempty(w) % if indeed attempt failed, move on to the next
            p = p + 1;
        end
    end

    if isempty(w), continue, end; % unable to make connection between the initial group of pins
    
    % connected remaining pins to the previously created connected
    % component
    p = 1; % restart from top
    pinSetOut(:,2) = 0; % reset connection attempt
    while ~all(pinSetOut(:,2))
        p1 = pinSetOut(p,1);
        [ign, d] = sort(setDist(szB, p1, pinSet), 'ascend'); % first distance will be zero (same point)
        pinSetOut(p,2) = 1; % assume connection attempt is going to fail
        for k = 2:numel(d)
            p2 = pinSet(d(k));
            [w, widx] = elbowConn(BB, p1, p2);
            if ~isempty(w)
                W = [ W; w ];
                BB(widx) = BB(p1); % "paint' wire on board
                pinSet = [ pinSet; p1; widx(:) ]; % add outside pin and new wire-"pins', connection points
                pinSetOut(p,:) = []; % remove outside pin from unconnected
                p = 1; % restart from top
                pinSetOut(:,2) = 0; % reset connection attempt
                %visualize(B,w,1);
                %pause(0.3)
                break;
            end
        end
        if ~isempty(pinSetOut) && pinSetOut(p,2) % if indeed attempt failed, move on to the next
            p = p + 1;
        end
    end
end

end % solver3

%% Elbow Connection
%  Attempts to create an *elbow* connection between p1 and p2. Sees other
%  not compatible wires are obstacle - *does not use bridges*.
function [W, Widx] = elbowConn(B, p1, p2)

[br, bc] = size(B);
n = B(p1);
W = zeros(0,4);
Widx = [];

[i1, j1] = ind2sub([br bc], p1);
[i2, j2] = ind2sub([br bc], p2);

istep = sign(i2-i1);
jstep = sign(j2-j1);
if istep == 0 % <=> i1 == i2
    vhline = i2 + ((j1+jstep:jstep:j2-jstep)-1)*br; % horizontal traverse
    if all( ~B(vhline) | B(vhline) == n )
        W = idx2wire([br bc], [p1 vhline p2]);
        Widx = vhline;
    end
elseif jstep == 0 % <=> j1 == j2
    hvline = (i1+istep:istep:i2-istep) + (j2-1)*br; % vertical traverse
    if all( ~B(hvline) | B(hvline) == n )
        W = idx2wire([br bc], [p1 hvline p2]);
        Widx = hvline;
    end
else
    vhline = [ (i1+istep:istep:i2) + (j1-1)*br ... % vertical traverse
        i2 + ((j1+jstep:jstep:j2-jstep)-1)*br ]; % horizontal traverse
    if all( ~B(vhline) | B(vhline) == n )
        W = idx2wire([br bc], [p1 vhline p2]);
        Widx = vhline;
    else
        hvline = [ i1 + ((j1+jstep:jstep:j2)-1)*br ... % horizontal traverse
            (i1+istep:istep:i2-istep) + (j2-1)*br ]; % vertical traverse
        if all( ~B(hvline) | B(hvline) == n )
            W = idx2wire([br bc], [p1 hvline p2]);
            Widx = hvline;
        end
    end
end

end % elbowConn

%% Index list to wire list
function W = idx2wire(szB, idxList)

[Wi Wj] = ind2sub(szB, idxList.');
W = [ Wi(1:end-1) Wj(1:end-1) Wi(2:end) Wj(2:end) ];

end % idx2wire

%% Manhattan distance between an index and a set of indexes
function d = setDist(sz,k,kset)

[i j] = ind2sub(sz,[k; kset(:)]);
d = abs(i(1)-i(2:end)) + abs(j(1)-j(2:end));

end % dist