function retwires = solver1(pB)

    global settingsBestngroups;

    global B;
    global Bsize;
    global Borigin1;
    global Borigin2;

    global nPins;

    global wires;
    global nwires;

    global pValues;
    global pCounts;
    global pDistances;
    global pTriDistances;
    global pDistancesX;
    global pDistancesY;
    global pConnected;
    global pXvs;
    global pYvs;

    global pGroups;
    global pLargestgroupsizes;

    settingsBestngroups = 8; % 2,3,...

 
    Borigin1 = [];
    Borigin2 = [];
 
    pGroups = [];
    pLargestgroupsizes = [];


    B = pB;

    Bsize = size(B);
    wires = zeros( ((Bsize(1)-1) * Bsize(2)) + (Bsize(1) * (Bsize(2)-1)), 4);
    nwires = 0;

    pValues = unique(B(B>0))';
    nPins = size(pValues, 2);
    pCounts = zeros(size(pValues));

    for j = 1:nPins
        pCounts(j) = nnz(B == pValues(j));
    end

    % skip single pins
    skip = pCounts == 1;
    if any(skip)
        nPins = nPins - sum(skip);
        pValues = pValues(~skip);
        pCounts = pCounts(~skip);
    end


    pDistances    = cell(1, nPins);
    pTriDistances = pDistances;
    pDistancesX   = pDistances;
    pDistancesY   = pDistances;
    pConnected    = pDistances;
    pXvs          = pDistances;
    pYvs          = pDistances;
    
    WiresL1andInit();

    WiresL2();

    LinkIslands();

    retwires = wires(1:nwires, :);
end


%% WiresL1andInit

function WiresL1andInit()
    global pXvs;
    global pYvs;
    global pConnected;
    global pDistancesX;
    global pDistancesY;
    global pDistances;
    global pTriDistances;
    global nPins;
    global pValues;
    global B;
    global Borigin1;
    global Borigin2;
    global pCounts;
    global wires;
    global nwires;

    for pix = 1:nPins
        [pXvs{pix} pYvs{pix}] = find(B == pValues(pix));

        for j = 1:length(pXvs{pix})
            Borigin1(pXvs{pix}(j), pYvs{pix}(j)) = pXvs{pix}(j);
            Borigin2(pXvs{pix}(j), pYvs{pix}(j)) = pYvs{pix}(j);
        end

        pConnected{pix}    = ~~eye(pCounts(pix));
        pDistancesX{pix}   = bsxfun(@(x1, x2) abs(x1-x2), pXvs{pix}, pXvs{pix}');
        pDistancesY{pix}   = bsxfun(@(y1, y2) abs(y1-y2), pYvs{pix}, pYvs{pix}');
        pDistances{pix}    = pDistancesX{pix} + pDistancesY{pix};
        pTriDistances{pix} = triu(pDistances{pix});

        % add wires for adjacent pins immediately
        adjacent = pTriDistances{pix} == 1;
        if any(any(adjacent))
            [aix1 aix2] = find(adjacent);
            nadjacent = length(aix1);
            for j = 1:nadjacent
                pConnected{pix}(aix1(j), aix2(j)) = true;
                pConnected{pix}(aix2(j), aix1(j)) = true;
            end
            [wires nwires] = addwires(wires, nwires, [pXvs{pix}(aix1) pYvs{pix}(aix1) pXvs{pix}(aix2) pYvs{pix}(aix2)]);
        end
    end
end


%% WiresL2

function WiresL2()
    global pTriDistances;
    global pDistancesX;
    global pYvs;
    global pXvs;
    global pConnected;
    global pValues;
    global nPins;
    global B;
    global Borigin1;
    global Borigin2;
    global wires;
    global nwires;

    [sv svix] = sort(pValues, 'descend');

    for cix = 1:nPins
        pix = svix(cix);

        d2b = pTriDistances{pix} == 2;

        if any(any(d2b))
            d2bstraight = d2b & pDistancesX{pix} ~= 1;
            d2bcorner   = d2b & ~d2bstraight;

            if any(any(d2bstraight))
                [ix1 ix2] = find(d2bstraight);
                pins = [pXvs{pix}(ix1) pYvs{pix}(ix1) pXvs{pix}(ix2) pYvs{pix}(ix2)];
                midpoints     = (pins(:, [1, 2]) + pins(:, [3, 4])) / 2;
                midpointsfree = PointsFree(B, midpoints);
                if any(midpointsfree)
                    pins      = pins(midpointsfree, :);
                    midpoints = midpoints(midpointsfree, :);
                    ix1 = ix1(midpointsfree);
                    ix2 = ix2(midpointsfree);
                    for j = 1:size(midpoints, 1)
                        %check if connected
                        if ~pConnected{pix}(ix1(j), ix2(j))
                            %if not connected, connect

                            [wires nwires] = addwires(wires, nwires, [ ...
                                pins(j, [1, 2]) midpoints(j, :); ...
                                pins(j, [3, 4]) midpoints(j, :)]);

                            B(midpoints(j, 1), midpoints(j, 2)) = -pValues(pix);
                            Borigin1(midpoints(j, 1), midpoints(j, 2)) = pins(j, 1);
                            Borigin2(midpoints(j, 1), midpoints(j, 2)) = pins(j, 2);

                            pConnected{pix}(ix1(j), ix2(j)) = true;
                            pConnected{pix}(ix2(j), ix1(j)) = true;
                            pConnected{pix} = ConvexConnections(pConnected{pix});
                        end


                    end
                    for j = 1:size(midpoints, 1)

                    end
                end
            end

            if any(any(d2bcorner))
                [ix1 ix2] = find(d2bcorner);
                pins = [pXvs{pix}(ix1) pYvs{pix}(ix1) pXvs{pix}(ix2) pYvs{pix}(ix2)];
                n = size(ix1, 1);
                midpoints = [pins(:, 1) pins(:, 4); pins(:, 3) pins(:, 2)];
                midpointsfree = PointsFree(B, midpoints);
                for j = 1:n
                    if ~pConnected{pix}(ix1(j), ix2(j))
                        pick = false;
                        if midpointsfree(j)
                            freemidpoint = midpoints(j, :);
                            pick = true;
                        elseif midpointsfree(j+n)
                            freemidpoint = midpoints(j+n, :);
                            pick = true;
                        end
                        if pick
                            [wires nwires] = addwires(wires, nwires, [ ...
                                pins(j, [1, 2]) freemidpoint; ...
                                pins(j, [3, 4]) freemidpoint]);
                            B(freemidpoint(1), freemidpoint(2)) = pValues(pix) * -1;
                            Borigin1(freemidpoint(1), freemidpoint(2)) = pins(j, 1);
                            Borigin2(freemidpoint(1), freemidpoint(2)) = pins(j, 2);
                            pConnected{pix}(ix1(j), ix2(j)) = true;
                            pConnected{pix}(ix2(j), ix1(j)) = true;
                            pConnected{pix} = ConvexConnections(pConnected{pix});
                        end
                    end
                end
            end
        end % if any(any(d2b))
    end % for cix = 1:nPins
end


%% LinkIslands

function LinkIslands()
    global pLargestgroupsizes;
    global pValues;
 
    lastpin = 0;
    foundlink = true;

    while foundlink
        %showme
                
        GenerateGroups(lastpin);
        profits = bsxfun(@times, pLargestgroupsizes, pValues);

        foundlink = false;
        while ~foundlink

            [profit pin] = max(max(profits(2:end, :)));

            if isnan(profit)
                break;
            end

            if isnan(profits(2, pin)) group = 2 + find(profits(3:end, pin)>0, 1, 'first');
            else                      group = 2;
            end

            foundlink = LinkGroups(pin, 1, group, profit);

            if foundlink
                lastpin = pin;
            else
                pLargestgroupsizes(group, pin) = NaN;
                profits(group, pin) = NaN;
            end
        end
    end
end


%% GenerateGroups

function GenerateGroups(pins)
    global pConnected;
    global pGroups;
    global pLargestgroupsizes;
    global nPins;
    global pCounts;
    global settingsBestngroups;

    if ~exist('pins', 'var') || isempty(pins) || (numel(pins) == 1 && pins < 1);
        pins = 1:nPins;
    end

    memogroupsizes = settingsBestngroups;
    if isempty(pGroups)
        pGroups = cell(1, nPins);
        pLargestgroupsizes = nan(memogroupsizes, nPins);
    else
        pGroups(pins) = cell(1);
        pLargestgroupsizes(:, pins) = nan(memogroupsizes, size(pins, 2));
    end

    for pix = pins
        % Make Convex Connections-Matrix
        pConnected{pix} = ConvexConnections(pConnected{pix});
        pGroups{pix} = zeros(1, pCounts(pix));

        c = pConnected{pix};
        sc = sum(c);
        items = 1:pCounts(pix);

        curgroup = 0;

        while ~isempty(c) %any(any(~c))
            if all(sc==1)
                pGroups{pix}(items) = curgroup + (1:length(sc));
                pLargestgroupsizes( curgroup+1 : min(curgroup+length(sc), memogroupsizes), pix) = 1;
                break;
            end
            curgroup = curgroup + 1;

            [gsize, gitem] = max(sc);
            gitems = c(gitem, :);
            remains = ~gitems;

            pGroups{pix}(items(gitems)) = curgroup;
            if curgroup <= memogroupsizes
                pLargestgroupsizes(curgroup, pix) = sum(gitems);
            end

            items = items(remains);
            sc = sc(remains);
            c = c(remains, remains);
        end
    end % for pix = 1:nPins
end


%% LinkGroups

function ret = LinkGroups(pin, group1, group2, budget)
    global pGroups;
    %     global pLargestgroupsizes;
    %     global nPins;
    %     global pCounts;
    global B;
    global Bsize;
    global pValues;
    global wires;
    global nwires;
    global pYvs;
    global pXvs;
    global Borigin1;
    global Borigin2;
    global pConnected;

    % we are sniffing from g2's items towards the center of g1 (g1 is the
    % larger group)

    ixitems1 = pGroups{pin} == group1;
    ixitems2 = pGroups{pin} == group2;

    g1 = [pXvs{pin}(ixitems1) pYvs{pin}(ixitems1)];
    g2 = [pXvs{pin}(ixitems2) pYvs{pin}(ixitems2)];

    g1center = mean(g1, 1);

    bestcost = inf;
    % bestcost = budget;
    bestwires = zeros(0, 4);

    for g2ix = 1:size(g2, 1)
        origin = g2(g2ix, :);
        % 8 17
        %[newcost newwires newconnecteditem] = Sniff(origin, pin, g1center, min(bestcost, budget), g2, false(Bsize), []);
        [newcost newwires newconnecteditem] = Sniff(origin, pin, g1center, budget, g2, false(Bsize), []);
        if newcost < bestcost;
            bestcost = newcost; 
            bestwires = newwires;
            bestconnecteditem = newconnecteditem;
        end
    end 

    if ~isempty(bestwires) 
        bestwires = ShortcutWires(bestwires);
        wiredpoints = [bestwires(:, [1 2]); bestwires(end, [3 4])];
        [wires nwires] = addwires(wires, nwires, bestwires);

        for j = 1:size(wiredpoints, 1)
            if ~B(wiredpoints(j, 1), wiredpoints(j, 2))
                B(wiredpoints(j, 1), wiredpoints(j, 2)) = pValues(pin) * -1;
                Borigin1(wiredpoints(j, 1), wiredpoints(j, 2)) = g2(1,1);
                Borigin2(wiredpoints(j, 1), wiredpoints(j, 2)) = g2(1,2);
            end
        end

        % link groups in connections-matrix
        item2 = pGroups{pin} == group2;
        item1 = all(bsxfun(@eq, [pXvs{pin} pYvs{pin}], bestconnecteditem), 2);
        pConnected{pin}(item1, item2) = true;

        ret = true;
    else
        ret = false;
    end

end


%% Sniff

function [bestcost bestwires bestconnecteditem beenthere] = Sniff(position, pix, direction, budget, sourcegroup, beenthere, camefromdir)
    global Bsize;
    global B;
    global Borigin1;
    global Borigin2;
    global pValues;

    if budget <= 0;
        bestcost = inf;
        bestwires = zeros(0, 4);
        bestconnecteditem = [];
        return;
    end

    d     = direction - position;
    dabs  = abs(d);
    dsign = sign(d);
    dsign(~dsign) = 1;

    if dabs(1) > dabs(2)     compass = [dsign(1) 0; 0 dsign(2); 0 -dsign(2); -dsign(1) 0];  % force = [true true false false];
    elseif dabs(1) < dabs(2) compass = [0 dsign(2); dsign(1) 0; -dsign(1) 0; 0 -dsign(2)];  % force = [true true false false];
    else                     compass = [dsign(1) 0; 0 dsign(2); -dsign(1) 0; 0 -dsign(2)];  % force = [true true false false];
    end


    neighbors = position([1;1;1;1], :) + compass;
    picks = all(neighbors>0 & neighbors <= Bsize([1;1;1;1], :), 2);
    if ~isempty(camefromdir)
        picks = picks & any(compass ~= -camefromdir([1;1;1;1], :), 2);
    end

    if ~all(picks)
        compass = compass(picks, :);
        % force = force(picks);
        neighbors = neighbors(picks, :);
    end
    ndirections = size(neighbors, 1);

    isnewempty = true(ndirections, 1);
    
    for j = 1:ndirections
        isnewempty(j) = ~B(neighbors(j, 1), neighbors(j, 2));
        if ~isnewempty(j) && abs(B(neighbors(j, 1), neighbors(j, 2))) == pValues(pix) 
            newpin = neighbors(j, :);
            origin = [Borigin1(newpin(1), newpin(2)), Borigin2(newpin(1), newpin(2))];
            odiff = bsxfun(@eq, origin, sourcegroup);
            isnewvalid = ~any(all(odiff, 2));
            if isnewvalid
                bestcost = 1;
                bestwires = [position newpin];
                bestconnecteditem = [Borigin1(newpin(1), newpin(2)), Borigin2(newpin(1), newpin(2))];
                return;
            end
        end
    end

    bestcost = inf;
    bestwires = zeros(0, 4);
    bestconnecteditem = [];
    
    
    
    for dix = 1:ndirections
        % if bestcost < inf && ~force(dix) break; end
        if bestcost < inf; break; end
        dir = compass(dix, :);
        newpin = neighbors(dix, :);

        if beenthere(newpin(1), newpin(2)) continue; end

        if isnewempty(dix)
            B(newpin(1), newpin(2)) = -pValues(pix);
            Borigin1(newpin(1), newpin(2)) = Borigin1(position(1), position(2));
            Borigin2(newpin(1), newpin(2)) = Borigin2(position(1), position(2));

            % RECURSE
            [newcost newwires newconnecteditem beenthere] = Sniff(newpin, pix, direction, budget-1, sourcegroup, beenthere, dir);

            beenthere(newpin(1), newpin(2)) = true;
            B(newpin(1), newpin(2)) = 0;
            Borigin1(newpin(1), newpin(2)) = 0;
            Borigin1(newpin(1), newpin(2)) = 0;

            if newcost < bestcost
                bestcost = newcost + 1;
                bestwires = [[position newpin]; newwires];
                bestconnecteditem = newconnecteditem;
            end
        end
    end
    
    % check for bridges
    if budget > 27 && isinf(bestcost)
        for dix = 1:ndirections
            dir = compass(dix, :);
            newpin  = neighbors(dix, :);
            newpin2 = newpin   + dir;

            if ~isnewempty(dix) ...                          % jump reqd
                    && all([newpin2>0 newpin2 <= Bsize]) ... % inside board
                    && ~B(newpin2(1), newpin2(2)) ...
                    && B(newpin(1), newpin(2))<0 ...         % wire here
                    && ~beenthere(newpin2(1), newpin2(2)) ...   % not been there
                    && B(newpin(1), newpin(2)) ~= -pValues(pix) ...
                    

                B(newpin2(1), newpin2(2)) = -pValues(pix);
                Borigin1(newpin2(1), newpin2(2)) = Borigin1(position(1), position(2));
                Borigin2(newpin2(1), newpin2(2)) = Borigin2(position(1), position(2));

                % RECURSE
                [newcost newwires newconnecteditem beenthere] = Sniff(newpin2, pix, direction, budget-27, sourcegroup, beenthere, dir);

                beenthere(newpin2(1), newpin2(2)) = true;

                B(newpin2(1), newpin2(2)) = 0;
                Borigin1(newpin2(1), newpin2(2)) = 0;
                Borigin1(newpin2(1), newpin2(2)) = 0;

                if newcost < bestcost
                    bestcost = newcost + 27;
                    bestwires = [[position newpin]; [newpin newpin]; [newpin newpin2]; newwires];
                    bestconnecteditem = newconnecteditem;
                end
            end
        end
    end
end

% function [cost newwires] = LinkPins(pin1, pin2)
% end


%% Misc Funcs


function wires = ShortcutWires(wires)

    %anybridges?
    ixbridges = all(wires(:, [1 2]) == wires(:, [3 4]), 2);
    havebridges = any(ixbridges);
    if havebridges
        bridges = wires( ixbridges, :);
        wires   = wires(~ixbridges, :);
    end

    wiredpoints = [wires(:, [1 2]); wires(end, [3 4])];
    dx = abs(bsxfun(@minus, wiredpoints(:, 1), wiredpoints(:, 1)'));
    dy = abs(bsxfun(@minus, wiredpoints(:, 2), wiredpoints(:, 2)'));
    d = dx + dy;

    trid = triu(d, 2);
    if any(any(trid == 1))
        [xs ys] = find(trid == 1);
        [maxv, maxix] = max(ys-xs);

        x = xs(maxix);
        y = ys(maxix);

        wires = [ ...
            wires(1:x-1, :); ...
            [wires(x, 1:2) wires(y-1, 3:4)]; ...
            wires(y:end , :)];
        wires = ShortcutWires(wires);
    end

    if havebridges
        nbridges = sum(ixbridges);
        for j = 1:nbridges
            bridgepoint = bridges(j, [1 2]);
            insert = find(all(bsxfun(@eq, wires(:, [1 2]), bridgepoint), 2));
            if ~isempty(insert)
                wires = [ wires(1:insert-1, :); [bridgepoint bridgepoint]; wires(insert:end, :)];
            end
        end
    end

end


function ret = PointsFree(B, points)
    ret = false(size(points, 1), 1);
    for j = 1:size(points, 1);
        if ~B(points(j, 1), points(j, 2))
            ret(j) = true;
        end
    end
end


function [wires nwires] = addwires(wires, nwires, newwires)
    nnewwires = size(newwires, 1);
    wires(nwires+1:nwires+nnewwires, :) = newwires;
    nwires = nwires + nnewwires;
end


function connected = ConvexConnections(connected)
    if ~any(any(connected)) return; end
    nc = nnz(connected);
    connected = connected | connected';
    while true
        connected = connected | (connected ^ 2);
        newnc = nnz(connected);
        if nc ~= newnc nc = newnc;
        else           break;
        end
    end
end


function showme()
    global B;
    global wires;
    global nwires;

    visualize(max(B, 0), wires(1:nwires, :));
end