function w = solver(b)

% get pin numbers
p = unique(b);
p(1) = [];

% count number of each pin
n = zeros(size(p));
for i = 1:length(n)
    n(i) = nnz(p(i) == b(:));
end

% don't worry about single pins
p(n==1) = [];
n(n==1) = [];

% [p n]

% sort from least to most number of pins
[n, ndx] = sort(n,'descend');
p = p(ndx);

% pad board
bb = repmat(-1,size(b)+2);
bb(2:end-1,2:end-1) = b;
b = bb;

% loop over pin numbers and connect
w = [];
for i = 1:length(p)
    % find index to pins with this number
    [rr, cc] = find(b == p(i));
    % connect these pins
    [b, mv] = connect(b, rr, cc);
    w = [w; mv];
end

% offset for padding
w = w - 1;


%%
function [b, w] = connect(b, rr, cc)

% loop over pins and find best wiring possible
v = b(rr(1), cc(1));
w = [];
for k = 1:length(rr)-1
    bestscore = 0;
    for i = 1:length(rr)
        if b(rr(i), cc(i)) == -5
            continue
        end
        % find the best possible move for one unconnected pin
        [score, mv] = findBestMove(b, rr(i), cc(i));
        if score > bestscore
            bestscore = score;
            bestmove = mv;
            if size(bestmove,1) == 1
                break
            end
        end
    end
    if bestscore == 0
        b(b==-5) = v; % reset
        return
    end
    b = doMove(b,bestmove);
    w = [w; bestmove];
end

b(b==-5) = v; % reset





return


% connect immediate neighbors vertically
[r, c] = find(b(1:end-1,:) == b(2:end,:) & b(1:end-1,:));
w = [r, c, r+1, c];

% connect immediate neighbors horizontally
[r, c] = find(b(:,1:end-1) == b(:,2:end) & b(:,1:end-1));
w = [w; r, c, r, c+1];

% s = grade(b,w);

% find index to unconnected pins
bb = b;
for i = 1:size(w,1)
    bb(w(i,1),w(i,2)) = 0;
    bb(w(i,3),w(i,4)) = 0;
end
[rr, cc] = find(bb);

visualize(b,w,999);

% pad board
bb = repmat(-1,size(b)+2);
bb(2:end-1,2:end-1) = b;
b = bb;
w = w + 1; % offset for padding
rr = rr + 1; % offset for padding
cc = cc + 1; % offset for padding

% loop to repeatedly find best move and do it
score = zeros(size(rr));
mv = cell(size(rr));
while true
    score(:) = 0;
    % find the best possible move for one unconnected pin
    for i = 1:length(rr)
        [score(i), mv{i}] = findBestMove(b, rr(i), cc(i));
    end
    % choose the best of the best moves
    [maxscore, ndx] = max(score);
    if maxscore == 0
        w = w - 1; % % offset for padding
        return % no moves left, so quit
    end
    % found a move
    w = [w; mv{ndx}]; % add wires to list
    b = doMove(b,mv{ndx}); % update board
    % don't test connected pins again
    rr(ndx) = [];
    cc(ndx) = [];
    ndx = find(rr == w(end,3) & cc == w(end,4));
    rr(ndx) = [];
    cc(ndx) = [];
end


%%
function [bestscore, bestmove] = findBestMove(b, r, c)

bestscore = 0;
bestmove = [];

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

% how many steps does it take to reach other locations on the board?
bb = b;
bb(bb>0) = -1;
bb(r,c) = 1;
for i = 1:50
    [rr, cc] = find(bb==i);
    for n = 1:length(rr)
        for m = 1:4
            v = bb(rr(n)+j(m),cc(n)+k(m));
            if v == 0
                bb(rr(n)+j(m),cc(n)+k(m)) = i+1;
            end
        end
    end
end

% choose closest pin
[rr,cc] = find(b == -5); % pins in group
if isempty(rr)
    [rr,cc] = find(b == b(r,c)); % no groups yet
end
minsteps = Inf;
for i = 1:length(rr)
    if r == rr(i) && c == cc(i)
        continue
    end
    for m = 1:4
        steps = bb(rr(i)+j(m),cc(i)+k(m));
        if steps > 0 && steps < minsteps
            minsteps = steps;
            besti = i;
        end
    end
end
if minsteps == Inf
    return % can't reach any pins
end

% define move and score
thisr = rr(besti);
thisc = cc(besti);
for step = minsteps:-1:1
    for m = 1:4
        nextr = thisr + j(m);
        nextc = thisc + k(m);
        if bb(nextr, nextc) == step
            break
        end
    end
    bestmove = [nextr, nextc, thisr, thisc; bestmove];
    thisr = nextr;
    thisc = nextc;
end
bestscore = 100 - minsteps;

return

bestscore = 0;
[rr,cc] = find(b == -5);
if isempty(rr)
    [rr,cc] = find(b == b(r,c));
end
for i = 1:length(rr)
    if r == rr(i) && c == cc(i)
        continue
    end
    [score, mv, bb] = tryToConnect(b,r,c,rr(i),cc(i),0);
    if score > bestscore
        bestscore = score;
        bestmove = mv;
    end
end


%%
function [bestscore, bestmove, b] = tryToConnect(b,r,c,rr,cc,d)

bestscore = 0;
bestmove = [];
b = b;

if d > 20
    return % prevent deep recursion
end

rd = rr - r;
cd = cc - c;
% if r == rr && c == cc
if abs(rd) + abs(cd) == 1
    bestscore = 100;
    bestmove = [r, c, rr, cc];
    return
end

% figure(998)
% imagesc(b)

order = zeros(1,4);
if abs(rd) > abs(cd)
    if rd > 0
        order([1 4]) = [1 2];
    else
        order([1 4]) = [2 1];
    end
    if cd > 0
        order([2 3]) = [3 4];
    else
        order([2 3]) = [4 3];
    end
else
    if cd > 0
        order([1 4]) = [3 4];
    else
        order([1 4]) = [4 3];
    end
    if rd > 0
        order([2 3]) = [1 2];
    else
        order([2 3]) = [2 1];
    end
end

j = [1 -1 0 0];
k = [0 0 1 -1];
for i = order
    if b(r+j(i),c+k(i)) == 0
        b(r+j(i),c+k(i)) = -10;
        [score, mv, b] = tryToConnect(b,r+j(i),c+k(i),rr,cc,d+1);
        if score > bestscore
            bestscore = score;
            bestmove = [r, c, r+j(i),c+k(i); mv];
        end
    end
end

if bestscore > 0
    bestscore = bestscore - 1;
end


%%
function b = doMove(b,mv)

for i = 1:size(mv,1)
    b(mv(i,1), mv(i,2)) = -5;
end
b(mv(end,3), mv(end,4)) = -5;