function w = solver(B)

tweak = rand(8,1);
%%%%%
[nR,nC] = size(B);

w = solverX(B,77,nR,nC);
s = mygrade(B,w,nR);



X = flipud(B);
X = X.';

W2 = solverX(X,90,nR,nC);
W2 = [nR-W2(:,2)+1 W2(:,1) nR-W2(:,4)+1 W2(:,3)];
s2 = mygrade(B,W2,nR);

if s>s2
	w=W2;
end
end
function score = mygrade(B,W,nR)
% 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,nR,nC)
% get pin numbers
p = unique(B(B>0));
%%%%%%%
N = length(p);
% count number of each pin
n = zeros(N,1);
for h = 1:N
    n(h) = nnz(p(h) == B(:));
end

% ignore single pins since they can't be connected to anything
for h = 1:N
    if n(h) == 1
        B(p(h) == B(:)) = -1;
    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 = G-1;
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 = (nR/2 - rr + 1).^2 + (nC/2 - cc + 1).^2;

[d, order] = sort(d); % start in center of board and work out
for k = 1:length(rr)-1
    bestscore = 0;
    minsteps = step;
    for h = order'
        rri = rr(h);
        cci = cc(h);
        if G(rri, cci)
            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, rri, cci, 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(rri, cci, 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;
%%%%
up = [1;-1;0;0];
lr = [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);
nextrr = zeros(steplimit,1);

nextcc = nextrr;
nextrr(1) = r;
nextcc(1) = c;
nextnumrr = 1;
brc = B(r,c);
for h = 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 + up(m);
            thisc = ccn + lr(m);
            v = G(thisr,thisc);
            if v == brc && ~(thisr == r && thisc == c)
                minsteps = h; % can link to group in this number of steps
                break
            end
            v = BB(thisr,thisc);
            if v == 0
                BB(thisr,thisc) = h + 1;
                nextnumrr = nextnumrr + 1;
                nextrr(nextnumrr) = thisr;
                nextcc(nextnumrr) = thisc;
            end
        end
        if minsteps < Inf
            break
        end
    end
    if minsteps < Inf
        break
    end
end
if minsteps == Inf
    return % can't reach any pins (good candidate for a bridge)
end

% score for this connection
bestscore = brc - minsteps;

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
up = [1;-1;0;0];
lr = [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 + up(irm);
        nextc = thisc + lr(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
for h = 1:size(mv,1)
    B(mv(h,1), mv(h,2)) = v;
end
B(mv(end,3), mv(end,4)) = v;

end