2012-04-11 12:00:00 UTC

# just a little try

by Eric

Status: Passed
Results: 108922 (cyc: 23, node: 6346)
CPU Time: 65.257
Score: 12322.7
Submitted at: 2012-04-10 18:01:56 UTC
Scored at: 2012-04-10 18:10:26 UTC

Current Rank: 1013th (Highest: 662nd )

Comments
Eric
10 Apr 2012
i'm just a teenager........
Please login or create a profile.
Code
```function [board, orientation] = solver(tiles, boardSize)

[board,orientation,solved,nrow,ncol,ntiles,nElem] = board_perfect_snake(boardSize,tiles);
if solved;    [board, orientation]= change(board,orientation,tiles);return;end

cs=hankel(1:4,0:3);
played = tiles;
numUnplayed = ntiles-nElem;
tiles1=tiles;

sums = sum(tiles,2);
if numUnplayed > 0
[sorted,si] = sort(sums);
numUnplayedp1=numUnplayed+1;
equals = find(sorted(numUnplayedp1)==sorted);
if nnz(sorted(numUnplayedp1) == sorted(numUnplayedp1:end)) ~= length(equals)
temp_si = si(equals);
[~,mi] = sort(min(tiles(temp_si,:),[],2));
for i=1:length(equals)
si(equals(end+1-i))= temp_si(mi(i));
end
end
played(si(1:numUnplayed),:) = Inf(numUnplayed,4);
ntiles=nElem;
height=nrow;
else
height=max(min(ceil(sqrt(ntiles)), nrow),ceil(ntiles/ncol));
end

[y,x]=ind2sub([height,ncol],1:ntiles);
ind = sub2ind(boardSize,y,x);
board(ind) = -1;
last = [y(end),x(end)];

b =repmat(board,[1,1,25]);
o = ones(size(tiles,1), 25);

NZ0 = sum(tiles==0,2);
NZ = NZ0*0;

[b(:,:,1),o(:,1),list] = place([1 height],1:last(2),b(:,:,1),played,played,o(:,1),ntiles, cs,nrow,ncol,false,NZ);
[b(:,:,1),o(:,1),list] = place(height:-1:1,[last(2) 1],b(:,:,1),played,list,o(:,1),ntiles, cs,nrow,ncol,false,NZ);
newList(:,:,1) = list;

[b(:,:,2),o(:,2),list] = place(height:-1:1,last(2),b(:,:,2),played,played,o(:,2),ntiles, cs,nrow,ncol,false,NZ);
[b(:,:,2),o(:,2),list] = place(height,1:last(2),b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,false,NZ);
[b(:,:,2),o(:,2),list] = place(1:height-1,1,b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,false,NZ);
[b(:,:,2),o(:,2),list] = place(1,2:last(2),b(:,:,2),played,list,o(:,2),ntiles, cs,nrow,ncol,false,NZ);
newList(:,:,2) = list;

for i=[2 6]
c = floor(i/6) + 1;
[b(:,:,i+1),o(:,i+1)] = place(height-1:-1:2,ncol-1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles , cs,nrow,ncol,true,NZ0);
[b(:,:,i+2),o(:,i+2)] = place(2:height-1,2:ncol-1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol,true,NZ0);
[b(:,:,i+3),o(:,i+3)] = place(height-1:-1:2,2:ncol-1,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol,true,NZ0);
[b(:,:,i+4),o(:,i+4)] = place(2:height-1,ncol-1:-1:2,b(:,:,c),played,newList(:,:,c),o(:,c),ntiles, cs,nrow,ncol,true,NZ0);
end

b(:,:,1 ) = b(:,:,3); o(:,1 ) = o(:,3);
[b(:,:,2 ), o(:,2 )] = calibrating_pure(played, boardSize,nrow,ncol);
[b(:,:,11),o(:,11)] = place(height:-1:1,1:ncol,b(:,:,12),played,played,o(:,12),ntiles,cs,nrow,ncol,-1,NZ0);
S = 11;

if nElem < 1000
for ii = 1:8
Sii=S+ii;
[b(:,:,Sii),o(:,Sii)] = BiswasMichaelC(height,last(2), played, played, o(:,Sii), ntiles, cs,nrow,ncol);
end

S=Sii;
if nElem < 200
S = S +1;
[b(:,:,S ), o(:,S )] = werner(tiles, boardSize,nrow,ncol);

end
end

overall = zeros(S,1);
parfor i=1:S
overall(i) = overallScore(b(:,:,i),nrow,ncol,o(:,i),tiles, cs);
end
overall(5) = Inf;
[~,mo] = min(overall);
[board,orientation]=localopt(b(:,:,mo), o(:,mo),tiles);
%[board, orientation]= change(board,orientation,tiles);

end

function [board,orientation,gain]=localopt(board, orientation,tiles)
gain=0;
cs=hankel(1:4,0:3);
[r,c]=size(board);
n = size(tiles,1);
didx = [3;4;1;2];
uidx = [1;2;3;4];
lidx = [4;1;2;3];
ridx = [2;3;4;1];
bp = board>0;
bt = board(bp);
te = [zeros(1,4);tiles];
oe = [1;orientation];
ub = [zeros(1,c);board(1:end-1,:)];
db = [board(2:end,:);zeros(1,c)];
lb = [zeros(r,1) board(:,1:end-1)];
rb = [board(:,2:end) zeros(r,1)];
ut = ub(bp)+1;
dt = db(bp)+1;
lt = lb(bp)+1;
rt = rb(bp)+1;
np1=n+1;
uv = te(ut(:)+(didx(oe(ut))-1)*(np1));
dv = te(dt(:)+(uidx(oe(dt))-1)*(np1));
lv = te(lt(:)+(ridx(oe(lt))-1)*(np1));
rv = te(rt(:)+(lidx(oe(rt))-1)*(np1));
bt=bt(:);
bv = tiles(bt(:,ones(1,4))+(cs(orientation(bt),:)-1)*n);
nv = [uv rv dv lv];
pv = sum(abs(bv-nv),2);
[mpv,id]=max(pv);
while mpv
bid=bt(id);
bid1=bid+1;
pv(id)=0;
obid = orientation(bid);
bx = tiles(bid,:);
p0 = sum(abs(bx(cs)-nv(id+zeros(4,1),:)),2);
[pmin,ido]=min(p0);
gain=gain+(p0(obid)-pmin);
if p0(obid)>pmin
bv(id,:)=bx(cs(ido,:));
orientation(bid)=ido;
oe(bid1)=ido;
u1=ut==bid1;
d1=dt==bid1;
l1=lt==bid1;
r1=rt==bid1;
uv(u1)=tiles(bid,didx(ido));
nv(u1,1)=uv(u1);
dv(d1)=tiles(bid,uidx(ido));
nv(d1,3)=dv(d1);
lv(l1)=tiles(bid,ridx(ido));
nv(l1,4)=lv(l1);
rv(r1)=tiles(bid,lidx(ido));
nv(r1,2)=rv(r1);
L=u1|d1|l1|r1;
pv(L) = sum(abs(bv(L,:)-nv(L,:)),2);
end
[mpv,id]=max(pv);
end
pv = sum(abs(bv-nv),2);
[mpv,id]=max(pv);
N=numel(pv);
tv = tiles(bt,:);
k=0;
while mpv>0
bid = bt(id);
bid1=bid+1;
nvid = zeros(1,16);
nvid(:) = nv(id+zeros(4,1),:);
u1=ut==bid1;
d1=dt==bid1;
l1=lt==bid1;
r1=rt==bid1;
L=~(u1|d1|l1|r1);
L(id)=false;
qv = Inf(N,4);
qv(L,:) = reshape(sum(reshape(abs(tv(L,cs)-nvid(ones(sum(L),1),:)),[],4),2),[],4);
[iv,to] = min(qv(:));
jd = mod(to-1,N)+1;
bjd = bt(jd);
bjd1=bjd+1;
% objd = orientation(bjd);
jo = ceil(to/N);
nvjd = nv(jd+zeros(4,1),:);
bvid = zeros(4);
bvid(:) = tiles(bid,cs);
[jv,io]=min(sum(abs(bvid - nvjd),2));
jpv = sum(abs(bv(jd,:) - nv(jd,:)));
if iv+jv < mpv+jpv
bt(jd) = bid;
bt(id) = bjd;
orientation(bid) = io;
orientation(bjd) = jo;
board(bp)=bt;
bv(id,:) = tv(jd,cs(jo,:));
bv(jd,:) = tv(id,cs(io,:));
bx = tv(id,:);
tv(id,:) = tv(jd,:);
tv(jd,:) = bx;
uv(u1)=tiles(bjd,didx(jo));
nv(u1,1)=uv(u1);
dv(d1)=tiles(bjd,uidx(jo));
nv(d1,3)=dv(d1);
lv(l1)=tiles(bjd,ridx(jo));
nv(l1,4)=lv(l1);
rv(r1)=tiles(bjd,lidx(jo));
nv(r1,2)=rv(r1);
u2=ut==bjd1;
d2=dt==bjd1;
l2=lt==bjd1;
r2=rt==bjd1;
uv(u2)=tiles(bid,didx(io));
nv(u2,1)=uv(u2);
dv(d2)=tiles(bid,uidx(io));
nv(d2,3)=dv(d2);
lv(l2)=tiles(bid,ridx(io));
nv(l2,4)=lv(l2);
rv(r2)=tiles(bid,lidx(io));
nv(r2,2)=rv(r2);
L=u1|d1|l1|r1|u2|d2|l2|r2;
pv(L) = sum(abs(bv(L,:)-nv(L,:)),2);
uid = ut==bid1;
ujd = ut==bjd1;
ut(uid) = bjd1;
ut(ujd) = bid1;
did = dt==bid1;
djd = dt==bjd1;
dt(did) = bjd1;
dt(djd) = bid1;
lid = lt==bid1;
ljd = lt==bjd1;
lt(lid) = bjd1;
lt(ljd) = bid1;
rid = rt==bid1;
rjd = rt==bjd1;
rt(rid) = bjd1;
rt(rjd) = bid1;
k=k+1;
end
pv(id)=0;
pv(jd)=0;
[mpv,id]=max(pv);
end
end
function score = overallScore(board,nrow,ncol, orientation, tiles, cs)

tile = zeros(nrow*4,ncol);
tmp = tiles.';
for y = 1:nrow
for x = 1:ncol
com=board(y,x);
if com
tile((y-1)*4+1:y*4,x)=tmp(cs(orientation(com),:),com);
end
end
end

out_tiles = 1:size(tiles,1);
in_tiles = board(board>0);
out_tiles(in_tiles) = [];

score = sum(sum(abs(tile(5:4:end,1:end)-tile(3:4:end-4,1:end))))+ ...
sum(sum(abs(tile(2:4:end,1:end-1)-tile(4:4:end,2:end))))+ ...
sum(tile(4:4:end,1))+sum(tile(2:4:end,end))+sum(tile(end-1,1:end))+ ...
sum(tile(1,1:end))+sum(sum(tiles(out_tiles,:)));
end

function [board, ort, lst] = BiswasMichaelC(height, width, tiles, lst, ort, ntiles, cs,nrow,ncol)
all_indices = reshape(1:(height*width),height,width);
center_x = width/2 + 0.5;
center_y = height/2 + 0.5;
cols = ceil(all_indices/height);
rows = mod(all_indices-1,height)+1;
dist_center = ((cols - center_x).^2 + (rows - center_y).^2).^(1/2.3);
dist_center = dist_center + rand(size(dist_center))*0.03; %param
[~, sort_index] = sort(dist_center(:));
loop_order = flipud(sort_index)';

board = zeros(nrow,ncol);
brd = zeros(height,width)-1;

if ntiles < height*width
loop_order(~ismember(loop_order,1:ntiles)) = [];
brd(ntiles+1:end) = 0;
end
score=inf(size(lst,1),1,4);
for ii = loop_order
y = rows(ii);
x = cols(ii);
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,height,width);

nesw = cat(3, [n e s w], [w n e s], [s w n e],[e s w n]);
mst=~isinf(lst(:,1));
score=score+inf;
score(mst,:,:) = sum(abs(int32(bsxfun(@minus,lst(mst,:),nesw))),2);

[ms, o] = find(score==min(score(:)));
which = round(rand*(length(ms)-1)+1);
t = ms(which);

ort(t) = o(which);
brd(y,x)=t;
lst(t,:)=inf(1,4);
end
end
board(1:height,1:width) = brd;
end

function [brd, ort, lst] = place(rowRange, colRange, brd, tiles, lst, ort, ntiles, cs,nrow,ncol,flag,NZ)
k = 1;
score=inf(size(lst,1),1,4);
for y=rowRange
for x=colRange
if (brd(y,x)==-1)
[n,e,s,w] = findBoundaries(brd, tiles, ort, y, x, cs,nrow,ncol);
nesw = cat(3, [n e s w], [w n e s], [s w n e],[e s w n]);
mst=~isinf(lst(:,1));
score=score+inf;
score(mst,:,:) = sum(abs(int32(bsxfun(@minus,lst(mst,:),nesw))),2);

[TT, O] = find(score==min(score(:)));
%
if flag==-1
idx_t = ceil(length(TT)/1.5);%round(rand*(length(ms)-1)+1);
elseif flag
[~,idx_t] = max(NZ(TT));
else
[~,idx_t] = min(NZ(TT));
end
t = TT(idx_t);
ort(t) = O(idx_t);
brd(y,x)=t;
lst(t,:)=inf(1,4);
k = k + 1;
if (k > ntiles)
return;
end
end
end
end
end

function [north, east, south, west] = findBoundaries(board, tiles, orientation, row, col, cs,nrow,ncol)
north = boundary(board, tiles, orientation, row-1,col ,3, cs,nrow,ncol );
south = boundary(board, tiles, orientation, row+1,col ,1, cs,nrow,ncol );
west = boundary(board, tiles, orientation, row ,col-1,2, cs,nrow,ncol );
east = boundary(board, tiles, orientation, row ,col+1,4, cs,nrow,ncol );
end

function value = boundary(board, tiles, orientation, row,col,id, cs,nrow,ncol )

if row<1 || col<1 || row>nrow || col>ncol || board(row,col) == 0
value = 0;
elseif board(row,col) == -1
value = nan;
else
value = tiles(board(row,col),cs(orientation(board(row,col)),id));
end

end

function [board, orientation] = calibrating_pure(tiles, boardSize,nrows,ncols)
board = zeros(boardSize);
ntiles = size(tiles, 1);
orientation = ones(ntiles, 1);
boarde = board;

% Kudos to Martin F. for quadrupling tiles
tiles = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];

tilestaken = false(4*ntiles, 1);
boarde(nrows,1) = 4;

[nextrow, nextcol,v]  = nextfield();
while v && ~all(tilestaken);

tix = findbesttilefor(nextrow, nextcol,tiles,board,nrows,ncols,tilestaken,false);

placetile(tix, nextrow, nextcol);

[nextrow, nextcol,v]  = nextfield();
end

function [nextrowv, nextcolv,v] = nextfield()
[v, ix] = max(boarde(:));
nextrowv=mod(ix-1,nrows)+1; nextcolv= ceil(ix/nrows);

end
function placetile(tileix, row, col)
board(row, col) = tileix;
boarde(row, col) = 0;
rowm1=row > 1;
colm1= col > 1;
rowmnrows=row < nrows;
colmncols=col < ncols;
rowp1=row+1;
colp1=col+1;
coln1=col-1;
rown1=row-1;

method4a(tileix, row, col,rowm1,colm1,rowmnrows ,colmncols, colp1,coln1,rowp1,rown1);
method4b( rowm1,colm1,colmncols, colp1,coln1, rown1);
method4c( colm1,rowmnrows,colmncols, colp1,coln1,rowp1 );

poptile(tileix);

function method4a(tileix, row, col,rowm1,colm1,rowmnrows,colmncols, colp1,coln1,rowp1,rown1)

if rowm1 && ~board(rown1,col ); boarde(rown1, col ) = boarde(rown1, col ) + tiles(tileix, 1); end;
if rowmnrows && ~board(rowp1,col ); boarde(rowp1, col ) = boarde(rowp1, col ) + tiles(tileix, 3); end;
if colm1 && ~board(row ,coln1); boarde(row , coln1) = boarde(row , coln1) + tiles(tileix, 4); end;
if colmncols && ~board(row ,colp1); boarde(row , colp1) = boarde(row , colp1) + tiles(tileix, 2); end;
end
function method4b( rowm1, colm1,colmncols, colp1,coln1, rown1)
if rowm1 && colm1 && ~board(rown1,coln1); boarde(rown1, coln1) = boarde(rown1, coln1) + 0.1; end;
if rowm1 && colmncols && ~board(rown1,colp1); boarde(rown1, colp1) = boarde(rown1, colp1) + 0.1; end;
end
function method4c( colm1,rowmnrows,colmncols, colp1,coln1,rowp1 )
if rowmnrows && colm1 && ~board(rowp1,coln1); boarde(rowp1, coln1) = boarde(rowp1, coln1) + 0.1; end;
if rowmnrows && colmncols && ~board(rowp1,colp1); boarde(rowp1, colp1) = boarde(rowp1, colp1) + 0.1; end;
end

function poptile(tileix )
ix = mod(tileix-1, ntiles)+1;
o = ceil(tileix/ntiles);
orientation(ix) = o;
tilestaken(ix+ntiles*(0:3), :) = true;
end
end

boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;

end

function [board orientation] = werner(tiles, boardSize,nrows,ncols)

board = zeros(boardSize);
ntiles = size(tiles, 1);
orientation = ones(ntiles, 1);

tiles = [tiles; tiles(:,[2:4,1]); tiles(:,[3:4,1:2]); tiles(:,[4,1:3])];
tilestaken = false(4*ntiles, 1);

boarde = board;
boarde(1,1) = 4;

[nextrow, nextcol,v]  = nextfield();

while v && ~all(tilestaken);

tix = findbesttilefor(nextrow, nextcol,tiles,board,nrows,ncols,tilestaken,true);
placetile(tix, nextrow, nextcol);
[nextrow, nextcol,v]  = nextfield();
end

function [nextrowv, nextcolv,v] = nextfield()
[v, ix] = max(boarde(:));
nextrowv =  mod(ix-1,nrows)+1;
nextcolv= ceil(ix/nrows) ;
end

function placetile(tileix, row, col)
board(row, col) = tileix;
boarde(row, col) = 0;
rowm1=row > 1;
colm1= col > 1;
rowmnrows=row < nrows;
colmncols=col < ncols;
rowp1=row+1;
colp1=col+1;
coln1=col-1;
rown1=row-1;

placetile1(tileix, row, col,rowm1,colm1,rowmnrows,colmncols,rowp1,rown1,colp1,coln1 );
placetile2( rowm1 ,colmncols,colm1, rown1,colp1,coln1);
placetile3( colm1,rowmnrows ,colmncols,rowp1 ,colp1,coln1);

poptile(tileix );

function placetile1(tileix, row, col,rowm1,colm1,rowmnrows,colmncols,rowp1,rown1,colp1,coln1 )
if rowm1 && ~board(rown1,col ); boarde(rown1, col ) = boarde(rown1, col ) + tiles(tileix, 1); end;
if rowmnrows && ~board(rowp1,col ); boarde(rowp1, col ) = boarde(rowp1, col ) + tiles(tileix, 3); end;
if colm1 && ~board(row ,coln1); boarde(row , coln1) = boarde(row , coln1) + tiles(tileix, 4); end;
if colmncols && ~board(row ,colp1); boarde(row , colp1) = boarde(row , colp1) + tiles(tileix, 2); end;
end

function placetile2( rowm1,colmncols,colm1, rown1,colp1,coln1)
if rowm1 && colm1 && ~board(rown1,coln1); boarde(rown1, coln1) = boarde(rown1, coln1) + 0.1; end;
if rowm1 && colmncols && ~board(rown1,colp1); boarde(rown1, colp1) = boarde(rown1, colp1) + 0.1; end;
end

function placetile3( colm1,rowmnrows,colmncols,rowp1, colp1,coln1)
if rowmnrows && colm1 && ~board(rowp1,coln1); boarde(rowp1, coln1) = boarde(rowp1, coln1) + 0.1; end;
if rowmnrows && colmncols && ~board(rowp1,colp1); boarde(rowp1, colp1) = boarde(rowp1, colp1) + 0.1; end;
end

function poptile(tileix )
ix = mod(tileix-1, ntiles)+1;
orientation(ix) =ceil(tileix/ntiles);
tilestaken(ix+ntiles*(0:3), :) = true;
end
end

boardzeros = board == 0;
board = mod(board-1, ntiles)+1;
board(boardzeros) = 0;

end

function ret = findbesttilefor(r, c,tiles,board,nrows,ncols,tilestaken,flag)
function myret=spycat(x,y,z,tiles,board)
if board(x,y) > 0; myret = tiles(board(x,y), z);
else myret = nan;
end
end

if r > 1;
rn1=r-1;
nv = spycat( rn1,c , 3,tiles,board);

else nv = 0;
end
if r < nrows;
rp1=r+1;
sv = spycat( rp1,c,1,tiles,board);

else sv = 0;
end
if c > 1;
cn1=c-1;
wv=spycat(r,cn1,2,tiles,board) ;

else wv = 0;
end
if c < ncols;
cp1=c+1;
ev= spycat(r,cp1,4,tiles,board)  ;
else ev = 0;
end

v = [nv, ev, sv, wv];
mask = ~isnan(v);
tilecosts = sum(abs(bsxfun(@minus, tiles(:,mask), v(mask))), 2);
tilecosts(tilestaken) = inf;
if flag

[~, ret] = min(tilecosts-sum(tiles,2).*1e-6);
else

[~, ret] = min(tilecosts - 1e-10*sum(tiles(:, isnan(v)), 2));
end

end

% Richard routines
function [board,orientation,solved,nr,nc,numtiles,nrnc]=board_perfect_snake(boardSize,tiles)
% check for perfect unique board
solved=false;
board = zeros(boardSize);
numtiles=size(tiles,1);

orientation = ones(numtiles, 1);

[nr nc]=size(board);
nrnc=nr*nc;
if numtiles~=nrnc,return;end

ptiles=prod(tiles,2); % search for zeros to count edge/corner pieces

% minimum required #tiles with a zero
if size(find(ptiles==0),1)<2*(nr+nc-2),return;end % No solution

otiles=tiles;

[tv,orientation,otiles,valid]= ...
find_corner(tiles,otiles,orientation);
if ~valid,return;end
board(1)=tv; % 2 pts

for i=1:nr

if i>1
tile=board(i-1);

[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,tiles,otiles,i,1,nrnc,tile,3);

if ~valid,return;end
end

for j=2:nc
tile=board(i,j-1);

[board,orientation,otiles,valid]= ...
find_tiles(board,orientation,tiles,otiles,i,j,nrnc,tile,2);
if ~valid,return;end

end
end

solved=true;

end

function [tv,orientation,otiles,valid]= ...
find_corner(tiles,otiles,orientation)

valid=false;
cs=[4 1 2 3];

for i=1:4
adj=abs(tiles(:,i))+abs(tiles(:,cs(i)));
tv=find(adj==0,1);
if ~isempty(tv)
orientation(tv)=i;
otiles(tv,:)=rot_tile(i,tiles(tv,:)); % or to i 2 pts
valid=true;
return;
end
end

end

function [one_tile]=rot_tile(rot,tile)
one_tile=circshift(tile,[0 1-rot]);
end

function [board,orientation,otiles,valid]= ...
find_tiles(board,orientation,tiles,otiles,i,j,nrnc,tile,ul)

valid=false;

goal=otiles(tile,ul);
tvec=find(otiles==goal);
if size(tvec,1)~=2,return;end % Non Unique solutions
tvecn1=tvec-1;
tnum=mod(tvecn1,nrnc)+1;
trot=floor((tvecn1)/nrnc)+1;

if tnum(1)~=tile % use
tv=tnum(1);
rot=trot(1);
else % use 2nd
tv=tnum(2);
rot=trot(2);
end

if j>1 % doing rows
rot = mod(rot,4)+1;
end
board(i,j)=tv;
otiles(tv,:)=rot_tile(rot,tiles(tv,:));
orientation(tv)=rot;

valid=true;
end

function [board, orientation]= change(board,orientation,tiles)
fitvalue=zeros(4,size(board,1),size(board,2)); %空穴参数
tilesvalue=zeros(4,size(board,1),size(board,2)); %方块参数
fitvalue1=zeros(size(board,1),size(board,2));
nr=size(board,1);
nc=size(board,2);
fitwell=zeros(nr,nc);
for i=1:size(tiles,1);

tiles(i,:)=circshift(tiles(i,:),[0,mod(5-orientation(i),4)]);
end
for i=1:nr
for j=1:nc
if board(i,j)~=0
for k=1:4
tilesvalue(k,i,j)=tiles(board(i,j),k);
end
else
tilesvalue(:,i,j)=zeros(4,1,1);
end
end
end
for i=1:nr
for j=1:nc

if i==1
fitvalue(1,i,j)=0;
else
fitvalue(1,i,j)=tilesvalue(3,i-1,j);
end

if i==nr
fitvalue(3,i,j)=0;
else
fitvalue(3,i,j)=tilesvalue(1,i+1,j);
end

if j==1
fitvalue(4,i,j)=0;
else
fitvalue(4,i,j)=tilesvalue(2,i,j-1);
end

if j==nc
fitvalue(2,i,j)=0;
else
fitvalue(2,i,j)=tilesvalue(4,i,j+1);
end
end
end

for i=1:nr
for j=1:nc
for k=1:4
fitwell(i,j)=fitwell(i,j)+abs(fitvalue(k,i,j)-tilesvalue(k,i,j));
end
end
end
%chain=zeros(1,4)
x=0;
while max(max(fitwell))~=0
x=x+1;
[epr1,epc1]=find(fitwell==max(max(fitwell)));

epr(1)=epr1(1);
epc(1)=epc1(1);
p=1;

sunvalue(:,1,1)=tilesvalue(:,epr(1),epc(1));
sunnum=board(epr(1),epc(1));
boardvac=zeros(size(board));
boardvac(epr(1),epc(1))=1;
finished=0;
board1=board;

%out=board(epr,epc);  %第一次提出一个方块

%vacantvalue=fitvalue(:,epr,epc);
%dimvalue=tilesvalue(:,epr,epc);
while finished==0
for i=1:nr
for j=1:nc
fitvalue1(i,j)=sum(abs(fitvalue(:,i,j)-tilesvalue(:,epr(p),epc(p))))-sum(abs(fitvalue(:,epr(p),epc(p))-tilesvalue(:,epr(p),epc(p))));
end
end

[epr1,epc1]=find(fitvalue1==min(min(fitvalue1)));

epr(p+1)=epr1(1);
epc(p+1)=epc1(1);
profit(p)=(-1)*min(min(fitvalue1));

if boardvac(epr(p+1),epc(p+1))==1
tprofit=zeros(p,1);
for i=1:p
if i==1
tprofit(i)=sum(profit(i:p-1))-sum(abs(fitvalue(:,epr(i),epc(i))-sunvalue(:,1,1))-(abs(fitvalue(:,epr(p),epc(p))-sunvalue(:,1,1))));
else
tprofit(i)=sum(profit(i:p-1))-sum(abs(fitvalue(:,epr(i),epc(i))-tilesvalue(:,epr(p),epc(p)))-(abs(fitvalue(:,epr(p),epc(p))-tilesvalue(:,epr(p),epc(p)))))-sum(profit(i:p-1));%由于第P个移出块找不到直接对应点，则在其移动路径上找最佳对应点

end
end

cut=find(tprofit==max(tprofit));
cut=cut(1);    %找到截止点cut
chain=[chain;zeros(p-cut+1,4)];
%      for j=x:x+p-cut-1
%          i=j+cut-x;
%          chain(j,1)=epr(i);
%          chain(j,2)=epc(i);
%          chain(j,3)=epr(i+1);
%          chain(j,4)=epc(i+1);
%      end
for i=1:cut-1
[board,fitvalue,tilesvalue,fitwell,~,~]=substitute(board,fitvalue,tilesvalue,fitwell,epr(i),epc(i),tilesvalue(:,epr(i+1),epc(i+1)),board(epr(i+1),epc(i+1)),nr,nc);
end
[board,fitvalue,tilesvalue,fitwell,~,~]=substitute(board,fitvalue,tilesvalue,fitwell,epr(cut),epc(cut),sunvalue,sunnum,nr,nc);

fitwell(epr(p),epc(p))=0;
finished=1;
else

[board,fitvalue,tilesvalue,fitwell,sunvalue,sunnum]=substitute(board,fitvalue,tilesvalue,fitwell,epr(p+1),epc(p+1),sunvalue,sunnum,nr,nc);
boardvac(epr(p+1),epc(p+1))=1;
p=p+1;
end

end
%  for i=1:nr
%      for j=1:nc
%          if board(i,j)~=board1(i,j)
%              board1
%              break;break;
%          end
%      end
%  end
% board1=board;
end

end

function [board,fitvalue,tilesvalue,fitwell,sunvalue,sunnum]=substitute(board,fitvalue,tilesvalue,fitwell,epr,epc,sunvalue,sunnum,nr,nc)%sunvalue表示移出的方块的值
tboard=sunnum;
ttilesvalue=sunvalue;
sunnum=board(epr,epc);
sunvalue=tilesvalue(:,epr,epc);
board(epr,epc)=tboard;
tilesvalue(:,epr,epc)=ttilesvalue;

if epr~=1
fitvalue(3,epr-1,epc)=tilesvalue(1,epr,epc);
end
if epc~=nc
fitvalue(4,epr,epc+1)=tilesvalue(2,epr,epc);
end
if epr~=nr
fitvalue(1,epr+1,epc)=tilesvalue(3,epr,epc);
end
if epc~=1
fitvalue(2,epr,epc-1)=tilesvalue(4,epr,epc);
end

fitwell(epr,epc)=0;

if epr~=1
if fitwell(epr-1,epc)~=0
fitwell(epr-1,epc)=0;
for k=1:4
fitwell(epr-1,epc)=fitwell(epr-1,epc)+abs(fitvalue(k,epr-1,epc)-tilesvalue(k,epr-1,epc));
end
end
end

if epr~=nr
if fitwell(epr+1,epc)~=0
fitwell(epr+1,epc)=0;
for k=1:4
fitwell(epr+1,epc)=fitwell(epr+1,epc)+abs(fitvalue(k,epr+1,epc)-tilesvalue(k,epr+1,epc));
end
end
end

if epc~=1
if fitwell(epr,epc-1)~=0
fitwell(epr,epc-1)=0;
for k=1:4
fitwell(epr,epc-1)=fitwell(epr,epc-1)+abs(fitvalue(k,epr,epc-1)-tilesvalue(k,epr,epc-1));
end
end
end

if epc~=nc
if fitwell(epr,epc+1)~=0
fitwell(epr,epc+1)=0;
for k=1:4
fitwell(epr,epc+1)=fitwell(epr,epc+1)+abs(fitvalue(k,epr,epc+1)-tilesvalue(k,epr,epc+1));
end
end
end
end```