function w = solver(b)

tweak = rand(8,1);

w = solverX(b,78);
s = mygrade(b,w);

nr = size(b,1);

X = b(nr:-1:1,:);
X = X.';

W2 = solverX(X,88);
W2 = [nr-W2(:,2)+1 W2(:,1) nr-W2(:,4)+1 W2(:,3)];
s2 = mygrade(b,W2);

if s>s2
	w=W2;
end
end
function score = mygrade(B,W)
nR=size(B,1);
B(W(:,1)+(W(:,2)-1)*nR)=0;
B(W(:,3)+(W(:,4)-1)*nR)=0;
score=sum(B(:))+size(W,1)+sum(W(:,1)==W(:,3)&W(:,2)==W(:,4))*24;
end


function w = solverX(b,step)
% get pin numbers
p = unique(b(b>0));

% count number of each pin
n=zeros(size(p));
for i=1:numel(p)
    pos=find(b==p(i));
    if numel(pos)==1

% ignore single pins since they can't be connected to anything
        n(i)=p(i);
        b(pos)=-1;
    else
        n(i)=p(i);
    end
end

% pad board so I don't have to deal with out of bounds indexing
g = zeros(size(b)+2); % board to keep track of groups
bb = repmat(-1,size(g));
bb(2:end-1,2:end-1) = b; % full board
% loop to choose move and do it
w = [];
[rr, cc] = find(bb>0); % pins I want to connect
d = (size(bb,1)/2 - rr).^2 + (size(bb,2)/2 - cc).^2;
[d, order] = sort(d); % start in center of board and work out
for k = 1:length(rr)-1
    bestscore = 0;
    minsteps = step;
    for i = order'
        if g(rr(i), cc(i))
            continue % this pin is already in a group, so don't try to connect
        end
        % find best route from pin to pin's group
        [score, steps, thisr, thisc, stepboard] = findBestMove(bb, g, rr(i), cc(i), minsteps);
        if score > bestscore
            bestscore = score;
            minsteps = steps;
            bestthisr = thisr;
            bestthisc = thisc;
            beststepboard = stepboard;
            if minsteps == 1
                break
            end
        end
    end
    if bestscore == 0 % can't make any more connections (try to add bridges?)
        w = w - 1; % offset for padding
        return
    end
    bestmove = findPath(rr(i), cc(i), bestthisr, bestthisc, minsteps, beststepboard);
    g = doMove(g, bestmove, bb(bestmove(1,1), bestmove(1,2)));
    bb = doMove(bb, bestmove, bb(bestmove(1,1), bestmove(1,2)));
    w = [w; bestmove];
end
w = w - 1; % offset for padding
end


%%
function [bestscore, minsteps, thisr, thisc, bb] = findBestMove(b, g, r, c, steplimit)

bestscore = 0;
minsteps = Inf;

j = [1 -1 0 0];
k = [0 0 1 -1];

if ~any(g(:)==b(r,c))
    g = b; % no groups for this pin yet, so all pins are valid
end

% start at (r,c) pin and step away one unit at a time looking for this pin's group
bb = b;
bb(bb>0) = -1;
bb(r,c) = 1; % keep track of how many steps it takes to get to each position
nextrr = zeros(1,100);
nextcc = nextrr;
nextrr(1) = r;
nextcc(1) = c;
nextnumrr = 1;
brc = b(r,c);
for i = 1:steplimit-1 % only allowed this many steps
    rr = nextrr;
    cc = nextcc;
    numrr = nextnumrr;
    nextnumrr = 0;
    for n = 1:numrr
        rrn = rr(n);
        ccn = cc(n);
        for m = 1:4
            thisr = rrn + j(m);
            thisc = ccn + k(m);
            v = g(thisr,thisc);
            if v == brc && ~(thisr == r && thisc == c)
                minsteps = i; % can link to group in this number of steps
                break
            end
            v = bb(thisr,thisc);
            if v == 0
                bb(thisr,thisc) = i + 1;
                nextnumrr = nextnumrr + 1;
                nextrr(nextnumrr) = thisr;
                nextcc(nextnumrr) = thisc;
            end
        end
        if minsteps < Inf
            break
        end
    end
    if minsteps < Inf
        break
    end
end

% score for this connection
bestscore = brc - minsteps;

 if minsteps == Inf
     bestscore = 0;
 end
end

%%
function bestmove = findPath(r, c, thisr, thisc, minsteps, bb)

% if only one step
if minsteps == 1
    bestmove = [r, c, thisr, thisc];
    return
end

% multiple steps - work backwards to define wire from group to pin
j = [1 -1 0 0];
k = [0 0 1 -1];
bestmove = zeros(minsteps,4);
ir = randperm(4);
for step = minsteps:-1:1
    for m = 1:4
        irm = ir(m);
        nextr = thisr + j(irm);
        nextc = thisc + k(irm);



        if bb(nextr, nextc) == step
            break
        end
    end
    bestmove(step,:) = [nextr, nextc, thisr, thisc];
    thisr = nextr;
    thisc = nextc;
end

end


%%
function b = doMove(b, mv, v)
% mark wires with the same number as the pins
b(mv(:,1)+(mv(:,2)-1)*size(b,1))=v;
b(mv(end,3), mv(end,4)) = v;
end