| Code: | function W = solver(boardIn)
nchoosekMax = 110;
pinValueExp = 1.0;
nrOfSamePinsExp = 0.5;
padSize = 13;
% pad board
[MIn, NIn] = size(boardIn);
padSize = min(padSize, max(MIn, NIn));
board = zeros(MIn+2*padSize, NIn+2*padSize);
boardIndex = board;
board (padSize+1:MIn+padSize, padSize+1:NIn+padSize) = boardIn;
boardIndex(padSize+1:MIn+padSize, padSize+1:NIn+padSize) = 1;
M = MIn + 2*padSize;
N = NIn + 2*padSize; %#ok
% initialize arrays
boardMod = board; % pin values at pin positions, negative pin values at connected points
islandMatrix = zeros(M, N); % matrix with island Ids
% get index of pin positions
pinIndex = find(board);
pinValues = board(pinIndex); %#ok
% get number of pins with a given value
pinValuesUnique = unique(pinValues);
nrOfSamePins = histc(pinValues, pinValuesUnique);
nrOfGroups = length(pinValuesUnique);
% decide with which pin value to start
pinGroupValues = (pinValuesUnique .^ pinValueExp) .* (nrOfSamePins .^ nrOfSamePinsExp);
[ignore, sortIndex] = sort(pinGroupValues, 1, 'descend'); %#ok
% get move codebook
[moveCodebook, col] = getmovecodebook__(M, padSize, nchoosekMax);
% loop over pin values (groups)
connMatrix = zeros(0,2);
for groupNr = 1:nrOfGroups
groupPinValue = pinValuesUnique(sortIndex(groupNr));
groupPinsIndex = pinIndex(pinValues == groupPinValue);
groupSize = length(groupPinsIndex);
% reset island index
islandMatrix(:) = 0;
lastIslandId = 0;
% loop over pin1 of current group (all pins of current value)
for pin1Nr = 1:groupSize
pin1Index = groupPinsIndex(pin1Nr);
% check island number
if islandMatrix(pin1Index) > 0
% pin was already touched
continue
else
% get new island Id
islandId = lastIslandId + 1;
lastIslandId = islandId;
islandMatrix(pin1Index) = islandId;
end
% start recursive search for possible moves
[boardMod, islandMatrix, connMatrix] = findmoves__(...
pin1Index, boardMod, islandMatrix, islandId, connMatrix, ...
moveCodebook, col, groupPinValue, boardIndex);
end
end
% remove duplicates
connMatrix = unique(connMatrix, 'rows');
% convert linear indices to row-column indices
W = convertConns__(connMatrix, M);
% consider padding
W = W - padSize;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [boardMod, islandMatrix, connMatrix] = findmoves__(...
pin1Index, boardMod, islandMatrix, islandId, connMatrix, ...
moveCodebook, col, groupPinValue, boardIndex)
% get vector of move ends
moveEnds = pin1Index + moveCodebook(:, col.move);
% check which moves end at other pin or wire of current group but other island
moveIndex = (abs(boardMod(moveEnds)) == groupPinValue) & ...
(islandMatrix(moveEnds) ~= islandId);
% loop over possible moves
for moveNr = find(moveIndex')
moveEndIndex = moveEnds(moveNr);
% check if point was touched before
if islandMatrix(moveEndIndex) == islandId
continue
end
% check if required fields are free
nrOfFreePoints = moveCodebook(moveNr, col.free);
if nrOfFreePoints > 0
freePinIndex = pin1Index + moveCodebook(moveNr, col.ind:(col.ind+nrOfFreePoints-1));
moveValid = all(boardMod(freePinIndex) == 0);
else
moveValid = 1;
end
if moveValid
% get current connections
currConns = pin1Index + getconnections__(moveCodebook(moveNr,:), col);
% check if any connections go outside the original board
if all(boardIndex(currConns(:,1)))
% save moves
connMatrix = [connMatrix; currConns]; %#ok
% mark points as occupied with connection
boardMod(currConns(2:end,1)) = -groupPinValue;
% set island Id
moveEndIslandId = islandMatrix(moveEndIndex);
if moveEndIslandId > 0
% merge islands
islandMatrix(islandMatrix == moveEndIslandId) = islandId;
end
% set current island Id to all connected points of current move
islandMatrix(currConns(:,2)) = islandId;
% start recursion if untouched pin at move end
if moveEndIslandId == 0 && boardMod(moveEndIndex) > 0
[boardMod, islandMatrix, connMatrix] = findmoves__(...
moveEndIndex, boardMod, islandMatrix, islandId, connMatrix, ...
moveCodebook, col, groupPinValue, boardIndex);
end
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [moveCodebook, col] = getmovecodebook__(M, padSize, nchoosekMax)
col.move = 1;
col.fwd = 2;
col.free = 3;
col.ind = 4;
moveCodebook = [
% mv fwd free indices ...................
2*M 1 3 -1 M-1 2*M-1 0 0 0; % two right with a loop (1)
2*M 1 3 1 M+1 2*M+1 0 0 0; % two right with a loop (2)
2 1 3 M M+1 M+2 0 0 0; % two down with a loop (1)
2 1 3 -M -M+1 -M+2 0 0 0; % two down with a loop (2)
3*M 1 4 -1 M-1 2*M-1 3*M-1 0 0; % three right with a loop (1)
3*M 1 4 1 M+1 2*M+1 3*M+1 0 0; % three right with a loop (2)
3 1 4 M M+1 M+2 M+3 0 0; % three down with a loop (1)
3 1 4 -M -M+1 -M+2 -M+3 0 0; % three down with a loop (2)
];
moveCodebook = [moveCodebook, zeros(size(moveCodebook,1), 10)];
drVec = [1 1 2 2 2 3 3 3 3 4 4 4 4 4 5 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 13 13];
dcVec = [0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 0 1 2 3 0 1 2 3 0 1 2 0 1 2 0 1 2 0 1 2 0 1 0 1];
nchoosekVec = zeros(size(drVec));
for k=1:length(drVec)
nchoosekVec(k) = nchoosek(drVec(k)+dcVec(k), drVec(k));
end
index = (nchoosekVec < nchoosekMax & drVec <= padSize);
drVec = drVec(index);
dcVec = dcVec(index);
for k=1:length(drVec)
codebookLine = codebookline__(drVec(k), dcVec(k), M, col, size(moveCodebook, 2));
moveCodebook = [moveCodebook; codebookLine]; %#ok
end
moveCodebook = addmirrors__(moveCodebook, col);
[ignore, sortIndex] = sort(moveCodebook(:, col.free));
moveCodebook = moveCodebook(sortIndex, :);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [codebookLines, rStep, cStep] = codebookline__(dr, dc, M, col, K)
% get steps in row-column notation
% slow: [rStep, cStep] = step__(0, 0, dr, dc);
% also slow: rStep3 = uniqueperms__([ones(dr,1); zeros(dc,1)]);
rStep = permpos__(dr, dr+dc);
cStep = ~rStep;
% add mirrored version
rStep = [rStep; -rStep];
cStep = [cStep; cStep];
% compute connection matrix
[nOfRows, nOfCols] = size(rStep);
connMatrix = zeros(nOfRows, nOfCols);
for m = 1:nOfRows
nextPoint = 0;
for n = 1:nOfCols
if rStep(m,n) ~= 0
nextPoint = nextPoint + rStep(m,n);
else
nextPoint = nextPoint + M;
end
connMatrix(m,n) = nextPoint;
end
end
% format codebooklines
codebookLines1 = zeros(nOfRows, K);
index = ones(nOfRows,1);
codebookLines1(:, col.move) = connMatrix(:,end);
codebookLines1(:, col.fwd) = index;
codebookLines1(:, col.free) = nOfCols(index) - 1;
codebookLines1(:, col.ind:(col.ind+nOfCols-2)) = connMatrix(:,1:end-1);
% compute transposed version of connection matrix
connMatrix = zeros(nOfRows, nOfCols);
for m = 1:nOfRows
nextPoint = 0;
for n = 1:nOfCols
if rStep(m,n) ~= 0
nextPoint = nextPoint + rStep(m,n) * M;
else
nextPoint = nextPoint + 1;
end
connMatrix(m,n) = nextPoint;
end
end
% format codebooklines
codebookLines2 = zeros(nOfRows, K);
index = ones(nOfRows,1);
codebookLines2(:, col.move) = connMatrix(:,end);
codebookLines2(:, col.fwd) = index;
codebookLines2(:, col.free) = nOfCols(index) - 1;
codebookLines2(:, col.ind:(col.ind+nOfCols-2)) = connMatrix(:,1:end-1);
codebookLines = [codebookLines1; codebookLines2];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function C = permpos__(M,N)
% PERMPOS - all possible permutations of M values in N positions
% (c) Jos van der Geest
A = [] ;
if M==1
% one true value -> on diagonal
B = logical(eye(N)) ;
else
% 1 < M < N, only now some real calculations have to be done
ind = nchoosek(1:N,M) ; % create a list of all possible column indices
nr = size(ind,1) ; % equals nchoosek(N,M)
ind = sub2ind([nr N],repmat((1:nr).',1,M),ind) ; % create linear indices
% fill the matrix
B = false(nr,N) ;
B(ind) = true ;
end
if ~isempty(A),
if numel(A)==1,
% negative scalar
C = zeros(size(B)) ;
C(B) = A ;
else
% vector argument
C = cumsum(B,2) ;
C(B) = A(C(B)) ;
C(~B) = 0 ;
end
else
C = B ;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function moveCodebook = addmirrors__(moveCodebook, col)
[nOfRows, nOfCols] = size(moveCodebook);
colIndex = [col.move, col.ind:nOfCols];
rowIndex = nOfRows+1:2*nOfRows;
moveCodebook = [moveCodebook; moveCodebook];
moveCodebook(rowIndex, colIndex) = -moveCodebook(rowIndex, colIndex);
rowIndex = reshape([1:nOfRows; nOfRows+1:2*nOfRows], 2*nOfRows, 1);
moveCodebook = moveCodebook(rowIndex,:);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function conn = getconnections__(moveCode, col)
conn = zeros(moveCode(col.free)+1, 2);
% set start and end points
conn(:,1) = [0; moveCode(1, col.ind:(col.ind+moveCode(1, col.free)-1))'];
conn(:,2) = [conn(2:end,1); moveCode(1, col.move)];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function W = convertConns__(connMatrix, M)
[r1, c1] = ind2sub__(M, connMatrix(:,1));
[r2, c2] = ind2sub__(M, connMatrix(:,2));
W = [r1 c1 r2 c2];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [r, c] = ind2sub__(M, k)
r = (rem(k - 1, M)) + 1;
c = (k - r) ./ M + 1;
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function k = sub2ind__(M, r, c)
%
% k = r + M * (c - 1);
|