| Code: | %% Wiring contest leading entry as of midnight Sunday
% Entry creator: David Jones
% Comments and cells added by: Alan Chalker
%% Main Solver
function W = solv(B)
% B: Test board matrix, 0's are blanks, #s are pins
% W: Calculated wiring result, n x 4 matrix
% each row is 1 wire segment in form [row1 col1 row2 col2]
% bridges are indicated by [row1 col1 row1 col1]
[W,S] = sunday(B); %Call main subroutine
if S < 2250 % if the score is low enough, return results
return
end
% If a roll a luckly number, return results
if rand < 0.35, return, end
[nr,nc] = size(B); % find size of board
B = flipud(fliplr(B)); % flip board diagonally
[W2,S2] = sunday(B); % rerun main subroutine
% if new score is better, correct coordinates in wiring list
if S > S2
W = [nr-W2(:,1)+1 nc-W2(:,2)+1 nr-W2(:,3)+1 nc-W2(:,4)+1];
end
end
%% Sunday subroutine
function [W,S] = sunday(B0)
[nR,nC]=size(B0); % Determine size of board
% Create a new board of NaNs that has a buffer row/col all the way around
Borig=nan(nR+2,nC+2);
Borig(2:end-1,2:end-1)=B0; % Populate the new board interior with the test board
Bedit = Borig; % Create a copy of the new board
maxbridges = 4; % Constant for max # of bridges
% Check to see if board is more than 20 cols wide and setup cutoffs as
% appropriate
if size(Bedit,2) > 20
cutfirst = 4;
cutsecond = 8;
cutoff = 12;
else
cutfirst = 3;
cutsecond = 7;
cutoff = 11;
end
S = inf;
% Pin stats weight criteria
% i.e. either path value or # of occurances is more important
X1 = [1 2;2 1];
X2 = [1 3;3 1];
Y = [3 2 1;1 2 3];
for x = 1:2 % Loop twice
% Initial wiring tests without bridges
if x == 2 && rand < 0.75 % If on second loop and a random value less than 0.75
[U BU] = phase1(Bedit,cutfirst,X1(x,:)); %make a first attempt at placing wires
[UU BUU] = phase3(BU,U,cutsecond,X2(x,:)); % make another attempt with the modified board
[V BX] = phase3(BUU,UU,cutoff,X2(x,:)); % make a final attempt with the3rd board
else % takes only 2 tries
[U BU] = phase1(Bedit,4,X1(x,:));
[V BX] = phase3(BU,U,11,X2(x,:));
end
for y = 1:2
% if on final loop, don't try bridges
if x == 2 && y == 2 && S > 2100, return, end
W1 = phase2(Bedit,BX,V,maxbridges,cutoff,Y(y,:))-1; % try to find bridges
S1 = mygrade(B0,W1); % check score
if S1 <= S % if score is too low
S = S1;
W = W1;
maxbridges = maxbridges - 1; % reduce number of allowable bridges
end
end
end
% if board is too big, return current results
if nR*nC > 290; return; end
br = sum(W(:,1)==W(:,3)&W(:,2)==W(:,4)); %find number of bridges in wiring list
if br <= 4 % if less than 5 bridges
WSH = solverSH(B0); % try another solvers
ssh = mygrade(B0,WSH); % grade again
if ssh < S % update wiring list if grade is better
W = WSH;
S = ssh;
end
end
end
%% Grading subroutine
function score = mygrade(B,W)
% Function to calculate the score of a wire list / board
% B = test board of pins
% W = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
nR=size(B,1); % Find # of rows of board
% Convert wiring start points from RC to Index coords and set corresponding
% points in board to 0
B(W(:,1)+(W(:,2)-1)*nR)=0;
% Convert wiring end points from RC to Index coords and set corresponding
% points in board to 0
B(W(:,3)+(W(:,4)-1)*nR)=0;
% Score is equal to all non-zero board elements summed, plus
% the number of rows (wires) in the wiring list, plus
% numbers of bridges in the wiring list * 24
score=sum(B(:))+size(W,1)+sum(W(:,1)==W(:,3)&W(:,2)==W(:,4))*24;
end
%% Analyzeboard subroutine
function [pincount k] = analyzeboard(B,rz)
% Finds the number of unique pin values on board, the occurances of each,
% and the distance (value) of the paths between pins of each value
%
% B = test board of pins
% rz = if < 3 than don't calculate path values
% pincount = n x 3 matrix of all pins in board [value #occurance pathvalue]
% k = total # of unique pin values
pin = sort(B(B>0),'descend'); % Make a sorted list of all pins from largest to smallest value
npins = size(pin,1); % Find number of pins
if npins < 1 % if no pins exist, return null result
pincount = [];
k = 0;
return
end
% Preallocate pincount variable. Col1 will be the pin value, col2 will be
% the # of occurances, col3
pincount = zeros(npins,3);
pincount(1,1) = pin(1); % Set first pincount to max pin value
k = 1;
count = 1;
for i = 2:npins % Loop over the rest of the pins
if pin(i) == pincount(k,1) % Check to see if pin is same as previous
count = count + 1;
else % If not same value, update pincount with # of occurances and reset counters
pincount(k,2) = count;
k = k + 1;
count = 1;
pincount(k,1) = pin(i);
end
end
pincount(k,2) = count; % Update final # of occurances
pincount = pincount(1:k,:); % Remove empty rows
% Don't calculate path values if not told to
if rz < 3, return, end
for i = 1:k % Loop over all pin values
if pincount(i,2) >= 2 % If more than 1 pin of a given value
p = pincount(i,1);
[row col] = find(B == p); % Find coords of all pins of that value
d = 0;
N = size(row,1);
% Calculate the total distances between subsequent pairs of pins of
% this value
for j = 2:N %
d = d + abs(row(j)-row(j-1)) + abs(col(j)-col(j-1));
end
% Update path value for this set of pins
pincount(i,3) = pincount(i,2)*p - 0.85 * d;
end
end
end
%% Phase1 subrountine
function [W B] = phase1(B,cutoff,rz)
% Try to find the best wire paths for a given board, doesn't take into
% account bridges
%
% B = test board of pins
% cutoff = max distance between pins to try to connect
% rz = weighting values for pin # vs. path values
% W = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
W = []; % Init wiring list
[pincount k] = analyzeboard(B,rz); % Find stats on pin values and occurances
% If no pins exist, return
if k < 1
return
end
% Sort pin stats according to input col weight criteria
% i.e. either path value or # of occurances is more important
pincount=sortrows(pincount,-rz);
for i = 1:k % Loop for # of unique pin values
if pincount(i,2) >= 2 % If there are more than 1 pin of a given value
p = pincount(i,1);
[row col] = find(B == p); % find all occurances of that value in board
N = size(row,1);
Npairs = N*(N-1)/2; % calculate # of possible pairs
dist = zeros(Npairs,3); % preallocate a dist array
x = 0;
for a = 1:N % Loop for # of pins
for b = (a+1):N % Loop for # of possible pairing pins
x = x + 1;
% Populate dist array with pin index #s and distances between
% the pair
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
end
end
[d ix] = sort(dist(:,3)); % Sort resulting distances from max to min
dist = dist(ix,:); % Eliminate any empty results
npins = 0;
% This loop tries to find the best first wire connection for this
% pin value
for x = 1:Npairs % loop for # of possible pairs
if dist(x,3) > cutoff+1 % don't proceed if distance is too great
break % stop checking this set of pairs
end
% Get the indexes of the current pin pair
a = dist(x,1);
b = dist(x,2);
% Call the path calculation function
path = complexpath(B,[row(a); row(b)], [col(a); col(b)], -p, cutoff, 2*p);
if size(path,1) > 0 % Check to see if a path was found
W = [W; path]; % If so, add to wiring list
B = addwirepath(B,path,-p); % Update board with wire
npins = 2;
% resort row/col list to bring this pair to the top
edit = [1:(a-1) (a+1):(b-1) (b+1):N];
row = [row(a); row(b); row(edit)];
col = [col(a); col(b); col(edit)];
break % stop checking this set of pairs
end
end
if npins < 2 % If didn't find a path, go to next pin value
continue
end
% If we found a wire, we now try to build upon it to connect any
% remaining pins
for j = 3:N % loop for # of remaining pins of this value
[row2 col2] = find(B == -p); % find all wires of this value
Npinwires = size(row2,1);
Npairs = Npinwires * (N - npins); % calculate max number of possible remaining wires
dist = zeros(Npairs,3); % preallocate array
x = 0;
for a = 1:Npinwires % loop for number of wires
for b = (npins+1):N % loop for remaining pins of this value
x = x + 1;
% Populate dist array with pin index #s and distances between
% the pair
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
end
end
[d ix] = sort(dist(:,3)); % Sort resulting distances from max to min
dist = dist(ix,:); % Eliminate any empty results
connected = false;
for x = 1:Npairs % loop for # of possible remaining pairs
if dist(x,3) > cutoff+1 % don't proceed if distance is too great
break % stop checking this set of pairs
end
% Get the indexes of the current wire / pin pair
a = dist(x,1);
b = dist(x,2);
% Call the path calculation function
path = complexpath(B,[row2(a); row(b)], [col2(a); col(b)], -p, cutoff, p);
if size(path,1) > 0 % Check to see if a path was found
W = [W; path]; % If so, add to wiring list
B = addwirepath(B,path,-p); % Update board with wire
npins = npins + 1; % Update number of pins connected to this wire
connected = true;
% resort row/col list to move this pin up a spot
row([j b]) = row([b j]);
col([j b]) = col([b j]);
break
end
end
if ~connected % If didn't find a path, go to next pin value
break
end
end
end
end
end
%% Phase2 subroutine
function [W B] = phase2(Borig,B,W,maxbridges,kappa,rz)
% Try to find the best wire paths for a given board, adding
% bridges where needed
%
% Borig = oringal test board
% B = board with wires in place
% maxbridges = max # of bridges to try to add
% kappa = = max distance between pins to try to connect
% rz = weighting values for pin # vs. path values
% W = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
function addbridgewirepath()
% Nested function to add a bridge wire to board
for w = 1:size(path,1); % Loop over wire list
if path(w,1) == path(w,3) % if horizontal wire
BH(path(w,1),path(w,2)) = false; % update horiz bridge board
BH(path(w,3),path(w,4)) = false;
if path(w,2) == path(w,4) % if a bridge
B(path(w,1),path(w,2)) = -9999; % set board to large -#
end
end
if path(w,2) == path(w,4) % if vertical
BV(path(w,1),path(w,2)) = false; % update vert bridge board
BV(path(w,3),path(w,4)) = false;
end
end
end
% Call buildbridges subrountine
[BH BV] = buildbridges(Borig,B,W);
%
%Note below is the same as Phase1 unless commented on
%
[pincount k] = analyzeboard(B,rz);
if k < 1, return, end
pincount=sortrows(pincount,-rz);
for i = 1:k
p = pincount(i,1); % Get value of max pin
Npinwires = sum(B == -p); % Find number of wires in place for this pin value
if Npinwires == 0 % If no wires exist, continue
if pincount(i,2) >= 2
[row col] = find(B == p);
N = size(row,1);
Npairs = N*(N-1)*.5;
dist = zeros(Npairs,3);
x = 0;
for a = 1:N
for b = (a+1):N
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
end
end
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
% determine the max steps (benefit) of placing bridges based upon pin value
maxstep = min((maxbridges*25)+kappa,2*p+1);
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
break
end
a = dist(x,1);
b = dist(x,2);
%Call the bridge path calculation function
path = bridgepath(B,BH,BV,[row(a); row(b)], [col(a); col(b)], -p, maxbridges, kappa, ceil(1.85*p));
if size(path,1) > 0
W = [W; path];
B = addwirepath(B,path,-p);
addbridgewirepath(); % update board with bridge
connected = true;
break
end
end
if ~connected
continue
end
end
end
[row col] = find(B == p); % find pins in board
Npins = size(row,1);
% determine the max steps (benefit) of placing next bridge based
% upon pin value
maxstep = min((maxbridges*25)+kappa,p+1);
for j = 1:Npins
[row2 col2] = find(B == -p);
Npinwires = size(row2,1);
Npairs = Npinwires * (Npins-j+1);
dist = zeros(Npairs,3);
x = 0;
for a = 1:Npinwires
for b = j:Npins
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
end
end
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
break
end
a = dist(x,1);
b = dist(x,2);
%Call the bridge path calculation function
path = bridgepath(B,BH,BV,[row2(a); row(b)], [col2(a); col(b)], -p, maxbridges, kappa, p);
if size(path,1) > 0
W = [W; path];
B = addwirepath(B,path,-p);
addbridgewirepath(); % update board with bridge
connected = true;
row([j b]) = row([b j]);
col([j b]) = col([b j]);
break
end
end
if ~connected
break
end
end
end
end
%% Phase3 subrountine
function [W B] = phase3(B,W,kappa,rz)
% Try to find the best wire paths for a given board, doesn't take into
% account bridges
%
% B = test board of pins and wires
% kappa = max distance between pins to try to connect
% rz = weighting values for pin # vs. path values
% W = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
%
%Note below is the same as Phase2 unless commented on
%
[pincount k] = analyzeboard(B,rz);
if k < 1, return, end
pincount=sortrows(pincount,-rz);
for i = 1:k
p = pincount(i,1);
Npinwires = sum(B == -p);
if Npinwires == 0
if pincount(i,2) >= 2
[row col] = find(B == p);
N = size(row,1);
Npairs = N*(N-1)*.5;
dist = zeros(Npairs,3);
x = 0;
for a = 1:N
for b = (a+1):N
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row(a)-row(b)) + abs(col(a)-col(b));
end
end
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
% determine the max steps (benefit) of possible paths
maxstep = min(kappa,2*p+1);
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
break
end
a = dist(x,1);
b = dist(x,2);
%Call the complexpath calculation function
path = complexpath(B,[row(a); row(b)], [col(a); col(b)], -p, kappa, 2*p);
if size(path,1) > 0
W = [W; path];
B = addwirepath(B,path,-p);
connected = true;
break
end
end
if ~connected
continue
end
end
end
[row col] = find(B == p);
Npins = size(row,1);
% determine the max steps (benefits) of subsequent wires
maxstep = min(kappa,p+1);
for j = 1:Npins
[row2 col2] = find(B == -p);
Npinwires = size(row2,1);
Npairs = Npinwires * (Npins-j+1);
dist = zeros(Npairs,3);
x = 0;
for a = 1:Npinwires
for b = j:Npins
x = x + 1;
dist(x,1) = a;
dist(x,2) = b;
dist(x,3) = abs(row2(a)-row(b)) + abs(col2(a)-col(b));
end
end
[d ix] = sort(dist(:,3));
dist = dist(ix,:);
connected = false;
for x = 1:Npairs
if dist(x,3) > maxstep+1
break
end
a = dist(x,1);
b = dist(x,2);
path = complexpath(B,[row2(a); row(b)], [col2(a); col(b)], -p, kappa, 2*p);
if size(path,1) > 0
W = [W; path];
B = addwirepath(B,path,-p);
connected = true;
row([j b]) = row([b j]);
col([j b]) = col([b j]);
break
end
end
if ~connected
break
end
end
end
end
%% Buildbridges subrountine
function [BH BV] = buildbridges(Borig,B,path)
% Creates 2 boards with maps of horiz and vert wires
%
% Borig = original test board without wires
% B = test board with wires
% path = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
% BH = board with 1 where there is a horz wire
% BV = board with 1 where these is a vert wire
[NR NC] = size(B); % find size of board
BH = Borig == 0; % find all locations without pins in original board
BV = BH;
BH(:,[1 NC]) = false; % clear first and last col
BV([1 NR],:) = false; % clear fist and last row
for i = 1:size(path,1) % loop for each wire
if path(i,1) == path(i,3) % if a horiz wire
BH(path(i,1),path(i,2)) = false; % clear coords in horiz board map
BH(path(i,3),path(i,4)) = false;
end
if path(i,2) == path(i,4) % if a vert wire
BV(path(i,1),path(i,2)) = false; % clear coords in vert board map
BV(path(i,3),path(i,4)) = false;
end
end
end
%% Addwirepath subroutine
function B = addwirepath(B,path,label)
% Update board with wires of a set value
%
% B = test board
% label = value to set wires to
% path = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
B(path(1,1),path(1,2)) = label; % set first point to value
for i = 1:size(path,1); % for remaining points
B(path(i,3),path(i,4)) = label; % set end points to value
end
end
%% Complexpath subroutine
function path = complexpath(B,row,col,label,cutoff,maxpathlen)
% Try to find the best wire paths for a given pair of pins, doesn't take into
% account bridges
%
% B = test board of pins
% row = row coords of pins
% col = col coords of pins
% label = pin values
% cutoff = max distance between pins to try to connect
% maxpathlen = max length of path to consider
% path = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
function path = traceback(dr,dc,t)
%follows back the current path branch and develops a wiring list
%
% dr = ending row
% dc = ending col
% t = # of steps taken
% path = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
%select ending point
PR(dr,dc) = r(i);
PC(dr,dc) = c(i);
path = zeros(t,4);
for j = 1:t % loop over number of steps taken
path(j,1:2) = [dr dc]; % update path with current point as starting coord
% find next ending coords
pr = PR(dr,dc);
pc = PC(dr,dc);
path(j,3:4) = [pr pc]; % update path with next point as ending coord
% copy ending coord to next starting coords
dr = pr;
dc = pc;
end
end
[NR NC] = size(B); % find size of board
%preallocate arrays
PR = zeros(NR,NC);
PC = zeros(NR,NC);
C = -ones(NR,NC);
C(row(2),col(2)) = 0; % set starting point
C(row(1),col(1)) = -2; % set end point
C( B == label ) = -2; % mark any other matching pins
% create vector with # of elements as board
rnext = zeros(NR*NC,1);
cnext = zeros(NR*NC,1);
count = 1;
% set starting point
rnext(1) = row(2);
cnext(1) = col(2);
dR=[-1 1 0 0];
dC=[0 0 -1 1];
for step = 0:min(cutoff,maxpathlen) % loop for max # of steps
% stop if this path is a deadend
if count < 1, break, end
N = count;
% select all the previous wires
r = rnext(1:N);
c = cnext(1:N);
count = 0;
for i = 1:N % loop over all possible steps
% select previous wire
ci = c(i);
ri = r(i);
for s=1:4 % for each of the possible directions
%create the next possible row / col coords
dr = ri + dR(s);
dc = ci + dC(s);
Z = dr + (dc-1)*NR; % convert from rc to index
tag = C(Z);
if tag == -2 % check to see if it's a matching pin
path = traceback(dr,dc,step+1); % if so, finish wire list
return
elseif tag == -1 && B(Z) == 0 % else check if it's an open space
C(Z) = step+1; % mark the step num
% update the potential step list
PR(Z) = ri;
PC(Z) = ci;
count = count + 1; rnext(count) = dr; cnext(count) = dc;
end
end
end
end
path = []; % return a null path if nothing is found
end
%% Bridgepath subroutine
function path = bridgepath(B,BH,BV,row,col,label,maxbridges,kappa,maxpathlen)
% Try to find the best wire paths for a given pair of pins, using bridges
%
% B = test board of pins
% BH = board map of horiz wires
% BV = board map of vert wire
% row = row coords of pins
% col = col coords of pins
% label = pin values
% maxbridges = max # of bridges to us
% kappa = max distance between pins to try to connect
% maxpathlen = max length of path to consider
% path = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
function path = traceback(Z,step)
%follows back the current path branch and develops a wiring list
%adds bridges where needed
%
% Z = indexed coord
% step = # of steps taken
% path = wiring list, n x 4 matrix of [r1 c1 r2 c2] coordinates
% get current location
PZ(Z) = zi;
dr=mod(Z,NR);
dc=ceil(Z/NR);
path = zeros(step,4); % preallocate path array
j = 0;
while dr ~= row(2) || dc ~= col(2) % loop until finding starting pin
j = j + 1;
path(j,1:2) = [dr dc]; %insert current starting wire coord
Z = dr + (dc-1)*NR;
pz = PZ(Z);
pr=mod(pz,NR);
pc=ceil(pz/NR);
path(j,3:4) = [pr pc]; %insert current ending wire coord
dr = pr;
dc = pc;
if BRIDGE(dr,dc) % if a bridge, insert coords
j = j + 1;
path(j,:) = [dr dc dr dc];
end
end
path = path(1:j,:);
end
[NR NC] = size(B); % find size of board
%preallocate arrays
BRIDGE = false(NR,NC);
PZ = zeros(NR,NC);
C = -ones(NR,NC);
C(row(2),col(2)) = 0; % set starting point
C(row(1),col(1)) = -2; % set ending point
C( B == label ) = -2; % set matching pins
%determine the max # of steps with bridges
maxstep = min((maxbridges*25)+kappa,maxpathlen+1);
stepcount = zeros(maxstep+26,1);
for step = 0:maxstep % loop for max # steps
if step == 0 % if starting, find size of board to search
z = row(2) + (col(2)-1)*NR;
elseif stepcount(step) == 0 % else check if any previous steps
continue
else % else find previous step
z = find(C == step);
end
N = numel(z);
for i = 1:N % loop over max search size
zi = z(i);
Z = zi + NR; % calculated index next row element
tag = C(Z);
% checks for wire to col to right
if tag == -2 % check if next col is pin
path = traceback(Z,step+1); % if so, construct path back to start and end
return
elseif tag == -1 % else check if empty space
if B(Z) == 0 % if empty space
C(Z) = step+1; stepcount(step+1) = 1; % if so update map as possible step
PZ(Z) = zi;
elseif BH(Z) % else if horiz wire
C(Z) = step+26; stepcount(step+26) = 1; % update map as possible bridge
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
% checks for wire to col to left (everything else is same as lines
% above)
Z = zi - NR;
tag = C(Z);
if tag == -2
path = traceback(Z,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PZ(Z) = zi;
elseif BH(Z)
C(Z) = step+26; stepcount(step+26) = 1;
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
% checks for wire to row above (everything else is same as lines
% above)
Z = zi - 1;
tag = C(Z);
if tag == -2
path = traceback(Z,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PZ(Z) = zi;
elseif BV(Z)
C(Z) = step+26; stepcount(step+26) = 1;
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
% checks for wire to row below (everything else is same as lines
% above)
Z = zi + 1;
tag = C(Z);
if tag == -2
path = traceback(Z,step+1);
return
elseif tag == -1
if B(Z) == 0
C(Z) = step+1; stepcount(step+1) = 1;
PZ(Z) = zi;
elseif BV(Z)
C(Z) = step+26; stepcount(step+26) = 1;
PZ(Z) = zi;
BRIDGE(Z) = true;
end
end
%
%
end
end
path = []; % return a null path if nothing is found
end
%% SolverSH subroutine
function w = solverSH(b)
% get pin numbers
p = unique(b);
p(1) = []; % discard zero
% count number of each pin
n = zeros(size(p));
for i = 1:length(n)
n(i) = nnz(p(i) == b(:));
end
% ignore single pins since they can't be connected to anything
for i = 1:length(n)
if n(i) == 1
b(p(i) == 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 = 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+0.5 - rr).^2 + (size(bb,2)/2+0.5 - cc).^2;
[d, order] = sort(d); % start in center of board and work out
order = order';
for k = 1:length(rr)-1
bestscore = 0;
minsteps = 32;
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, mv, steps] = findBestMove(bb, g, rr(i), cc(i), minsteps);
if score > bestscore
bestscore = score;
bestmove = mv;
minsteps = steps;
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
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
%% Findbestmove subroutine
function [bestscore, bestmove, minsteps] = findBestMove(b, g, r, c, steplimit)
bestscore = 0;
bestmove = [];
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
minsteps = Inf;
p = b(r,c);
for i = 1:steplimit % only allowed this many steps
[rr, cc] = find(bb==i);
for n = 1:length(rr)
for m = 1:4
thisr = rr(n) + j(m);
thisc = cc(n) + k(m);
if g(thisr,thisc) == p && ~(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;
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 = b(r,c) - minsteps;
% 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
bestmove = zeros(minsteps,4);
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(step,:) = [nextr, nextc, thisr, thisc];
thisr = nextr;
thisc = nextc;
end
end
%% Domove subroutine
function b = doMove(b, mv, v)
% Marks wires on board with the same value as the connectng pins
% b= test board of pins
% mv = wiring list, n x 4 matrix of [r1 c1 r2 c2]
% v = value of pin to set wires to
for i = 1:size(mv,1) % for # of wires in wiring list
b(mv(i,1), mv(i,2)) = v; % set start coordinate to value
end
b(mv(end,3), mv(end,4)) = v; % set final ending coordinate to value
end
|