function moves = solver(board)
moves=dorec(board);
function moves = dorec(board)
[m,n]=size(board);
mp=m+4;
np=n+4;
padBoard=-1*ones(mp,np);
padBoard(3:end-2,3:end-2)=board;
padBoardNoZeros=padBoard;
padBoardNoZeros(find(padBoard<=0))=1;
padBin=padBoard./padBoardNoZeros;
dest=find(padBoard==0);
maybe=zeros(4*size(dest,1),6);
moveCnt=1;
for i=1:size(dest,1)
this=dest(i);
% Format of valid
% valid(2)/not(anything else) src jump_over dest score direction_from(1 fron top, 2 from right etc)
maybe(moveCnt,:)=[padBin(this-1)+padBin(this-2) this-2 this-1 this padBoard(this-1)-padBoard(this-2) 1];
maybe(moveCnt+1,:)=[padBin(this+1)+padBin(this+2) this+2 this+1 this padBoard(this+1)-padBoard(this+2) 3];
maybe(moveCnt+2,:)=[padBin(this-mp)+padBin(this-2*mp) this-2*mp this-mp this padBoard(this-mp)-padBoard(this-2*mp) 4];
maybe(moveCnt+3,:)=[padBin(this+mp)+padBin(this+2*mp) this+2*mp this+mp this padBoard(this+mp)-padBoard(this+2*mp) 2];
moveCnt=moveCnt+4;
end
restoreScore=0;
valid=maybe(find(maybe(:,1)==2),:);
moves=[0 0 0 0];
restoreMoves=[0 0 0 0];
score=0;
totJumps=0;
totChains=0;
while ~isempty(valid)
[chainMoves,scoreRet]=clearChain(padBoard,padBin,valid,mp,np,1);
totJumps=totJumps+size(chainMoves,1);
totChains=totChains+1;
if (scoreRet<0) && (score>=restoreScore)
restoreScore=score;
restoreMoves=moves;
end
[padBoard,padBin,valid,chainMoves]=doMoves(padBoard,padBin,valid,chainMoves);
moves=[moves; chainMoves];
score=score+scoreRet;
end
avgChainLength=totJumps/totChains;
if (score>restoreScore)
moves=moves(find(moves(:,1)>0),:);
else
moves=restoreMoves(find(restoreMoves(:,1)>0),:);
end
function [chainMoves,scoreRet,depthRet]=clearChain(padBoard,padBin,valid,mp,np,depth)
scoreMax=-10000;
chainMoves=[0 0 0];
nextMoves=zeros(4,4);
for i=1:size(valid,1)
scoreChain=0;
newBin=padBin;
newBoard=padBoard;
source=valid(i,2);
over=valid(i,3);
dest=valid(i,4);
newBin([source;over])=0;
newBin(dest)=1;
scoreThis=newBoard(over)-newBoard(source);
newBoard([source;over;dest])=0;
nextMoves(1,:)=[newBin(dest-1)+3*newBin(dest-2) dest dest-1 dest-2];
nextMoves(2,:)=[newBin(dest+1)+3*newBin(dest+2) dest dest+1 dest+2];
nextMoves(3,:)=[newBin(dest-mp)+3*newBin(dest-2*mp) dest dest-mp dest-2*mp];
nextMoves(4,:)=[newBin(dest+mp)+3*newBin(dest+2*mp) dest dest+mp dest+2*mp];
nextMoves=nextMoves(find(nextMoves(:,1)==1),:);
depthRet=depth;
if ~isempty(nextMoves)
[chainMoves,scoreChain,depthRet]=clearChain(newBoard,newBin,nextMoves,mp,np,depth+1);
end
scoreTotal=scoreThis+scoreChain;
if scoreTotal>scoreMax
scoreMax=scoreTotal;
bestMoves=[source over dest; chainMoves];
bestDepth=depthRet;
end
end
if (depth==1)
chainMoves=bestMoves(1:bestDepth,:);
else
chainMoves=bestMoves;
end
scoreRet=scoreMax;
depthRet=bestDepth;
function [padBoard,padBin,valid,retMoves]=doMoves(padBoard,padBin,valid,chainMoves)
retMoves=[0 0 0 0];
[mp,np]=size(padBoard);
for i=1:size(chainMoves,1)
from = chainMoves(i,1);
over = chainMoves(i,2);
to = chainMoves(i,3);
rpadsrc=mod(from,mp)-2;
cpadsrc=(from-rpadsrc-2)/mp-1;
rpaddest=mod(to,mp)-2;
cpaddest=(to-rpaddest-2)/mp-1;
retMoves = [retMoves; rpadsrc cpadsrc rpaddest cpaddest];
padBin(from)=0;
padBin(over)=0;
padBin(to)=1;
padBoard(to)=padBoard(from);
padBoard(from)=0;
padBoard(over)=0;
% Remove entries in valid move table that are no longer possible
for x = 1 : size(valid,1)
if (valid(x,3)==from)||(valid(x,3)==over)||(valid(x,2)==over)||(valid(x,2)==from)||(valid(x,4)==to)
valid(x,1)=0;
end
end
% Add all valid moves into spot where move is made from
valid=[valid; padBin(from-1)+padBin(from-2) from-2 from-1 from padBoard(from-1)-padBoard(from-2) 1];
valid=[valid; padBin(from+1)+padBin(from+2) from+2 from+1 from padBoard(from+1)-padBoard(from+2) 3];
valid=[valid; padBin(from-mp)+padBin(from-2*mp) from-2*mp from-mp from padBoard(from-mp)-padBoard(from-2*mp) 4];
valid=[valid; padBin(from+mp)+padBin(from+2*mp) from+2*mp from+mp from padBoard(from+mp)-padBoard(from+2*mp) 2];
% Add all valid moves into spot that is jumped over
valid=[valid; padBin(over-1)+padBin(over-2) over-2 over-1 over padBoard(over-1)-padBoard(over-2) 1];
valid=[valid; padBin(over+1)+padBin(over+2) over+2 over+1 over padBoard(over+1)-padBoard(over+2) 3];
valid=[valid; padBin(over-mp)+padBin(over-2*mp) over-2*mp over-mp over padBoard(over-mp)-padBoard(over-2*mp) 4];
valid=[valid; padBin(over+mp)+padBin(over+2*mp) over+2*mp over+mp over padBoard(over+mp)-padBoard(over+2*mp) 2];
% Add all valid moves out of destination
valid=[valid; 2*padBin(to-1)+3*padBin(to-2) to to-1 to-2 10000+padBoard(to-1) 1];
valid=[valid; 2*padBin(to+1)+3*padBin(to+2) to to+1 to+2 10000+padBoard(to+1) 3];
valid=[valid; 2*padBin(to-mp)+3*padBin(to-2*mp) to to-mp to-2*mp 10000+padBoard(to-mp) 4];
valid=[valid; 2*padBin(to+mp)+3*padBin(to+2*mp) to to+mp to+2*mp 10000+padBoard(to+mp) 2];
% Add all moves jumping over destination
valid=[valid; 6-4*padBin(to-1)+padBin(to+1) to-1 to to+1 padBoard(to)-padBoard(to-1) 1];
valid=[valid; 6-4*padBin(to+1)+padBin(to-1) to+1 to to-1 padBoard(to)-padBoard(to+1) 3];
valid=[valid; 6-4*padBin(to-mp)+padBin(to+mp) to-mp to to+mp padBoard(to)-padBoard(to-mp) 4];
valid=[valid; 6-4*padBin(to+mp)+padBin(to-mp) to+mp to to-mp padBoard(to)-padBoard(to+mp) 2];
% Remove all invalid entries
valid=valid(find(valid(:,1)==2),:);
end
|
