function moves = solver(A, B, w0)
n = length(w0);
ipos1=zeros(n,1);
ipos2=ipos1;
fpos1=ipos1;
fpos2=ipos1;
for i=1:n
[ipos1(i) ipos2(i)] = find(A==i);
[fpos1(i) fpos2(i)] = find(B==i);
end
optmove = sum(abs(fpos1-ipos1)+abs(fpos2-ipos2));
if n~=28 || (numel(A)/n) <= 1.98
moves = TLL79(A,B,w0);
flag =0;
else
flag=1;
end
if ((n >= 18 && n <= 20) || n==28 || n==23 || (n>=13 && n <= 16)) &&...
(flag || length(moves) > 1.17*optmove) && (numel(A)/n) > 1.98
if flag==0
moves = checksummer(A,moves,n,ipos1,ipos2);
end
ym = size(A,1);
M = [ym 1 -ym -1];
mask = isfinite(w0(:))';
w = abs(w0(:)')+.1;
rand('seed',42);
[mov, ok] = mainsolver(A,B,w,mask,' ');
if ok && flag==0
mov = 1*(mov==M(1)) + 2*(mov==M(2)) + 3*(mov==M(3)) + 4*(mov==M(4));
mov = [(mov>0)*(1:n)' sum(mov,2)];
mov=optimize(A,mov);
res1 = sum(w0(moves(:,1)));
res2 = sum(w0(mov(:,1)));
if res2<res1
moves = mov;
end
else
mov = 1*(mov==M(1)) + 2*(mov==M(2)) + 3*(mov==M(3)) + 4*(mov==M(4));
mov = [(mov>0)*(1:n)' sum(mov,2)];
moves=optimize(A,mov);
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [mov, ok] = mainsolver(A,B,w,mask,reclevel)
n = sum(mask);
if n==0
ok = 0;
return
end
[mov, ok] = easysolver(A,B,w,mask);
if ok
return
end
ipos = zeros(size(mask));
for i=find(mask)
ipos(i) = find(A==i);
end
pos = cumsum([ipos; mov]);
okmov = 1;
newipos = pos(okmov,:);
invw = max(w)+1-w;
blockers = sum(findoverlaps(pos));
for leaveout = ceil(2*log(n)):(n-1)
mmask = mask;
choosew = sum(blockers).*invw;
for i = 1:leaveout
randi = rand*sum(mmask.*choosew);
choose = find(cumsum(mmask.*choosew)>=randi,1,'first');
mmask(choose) = false;
end
Ap = zeros(size(A));
Bp = zeros(size(B));
for i = find(mmask)
Ap(newipos(i)) = i;
Bp(B==i) = i;
end
[partialmov, ok] = mainsolver(Ap, Bp, w+min(w)*rand(size(w)), mmask, [reclevel ' ']);
blockers = blockers + sum(findoverlaps(cumsum([newipos;partialmov])));
if ~ok
continue
end
for i = find(mask)
Ap(newipos(i)) = i;
end
for i = 1:3*sum(mask)
randi = rand*sum(w.*(~mmask & mask));
choose = find(cumsum(w.*(~mmask & mask))>=randi,1,'first');
[trymov, ok] = imoves(choose,partialmov,Ap,B,mmask);
if ok
partialmov = trymov;
mmask(choose) = true;
if isequal(mmask,mask)
ok = 1;
mov = [mov(1:okmov-1,:); partialmov];
return
end
else
dropw = blockers.*invw;
randi = rand*sum(dropw.*(mmask&mask));
choose = find(cumsum(dropw.*(mmask&mask))>=randi,1,'first');
mmask(choose) = false;
partialmov(find(partialmov(:,choose)),:) = [];
end
end
ok = 0;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [mov, ok] = imoves(c,mov,A,B,mask)
mov(find(mov(:,c)),:) = [];
nmov = size(mov,1);
n = length(mask);
[crow,ccol] = find(A==c);
[trow,tcol] = find(B==c);
if nmov == 0 && crow==trow && ccol==tcol
ok = 1;
return
end
[rows,cols] = size(A);
slices = false(rows, cols, nmov+1);
ipos = zeros(1,n);
for i=find(mask)
ipos(i) = find(A(:)==i);
end
pos = cumsum([ipos; mov],1);
for k=1:(nmov+1)
R = zeros(size(A));
R(pos(k,mask)) = -1;
slices(:,:,k) = (R==-1);
end
target = sub2ind(size(slices),trow,tcol,nmov+1);
optlen = abs(crow-trow) + abs(ccol-tcol);
[path] = dijkstra(numel(slices),find(A==c), target, slices, optlen);
if isempty(path)
ok = 0;
return
end
for i=length(path):-1:2
if path(i)-path(i-1) < rows*cols
k = floor((path(i-1)-1)/(rows*cols))+1;
mov = [mov(1:(k-1),:); zeros(1,n); mov(k:end,:)];
mov(k,c) = path(i)-path(i-1);
end
end
ok = 1;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [moves, ok] = easysolver(A,B,w,mask)
global TEST
TEST=1;
NFIDDLE = 5;
ok = 0;
ym = size(A,1);
n = length(mask);
M = [ym 1 -ym -1];
moves = [];
ipos = zeros(1,n);
for i = find(mask)
[row,col] = find(A==i);
[rowt,colt] = find(B==i);
nm = abs(col-colt) + abs(row-rowt);
moves = [moves; zeros(nm,i-1) ...
[M(1)*ones(max((colt-col),0),1); ...
M(2)*ones(max((rowt-row),0),1); ...
M(3)*ones(max((col-colt),0),1); ...
M(4)*ones(max((row-rowt),0),1)] ...
zeros(nm,n-i)];
ipos(i) = (col-1)*ym + row;
end
nmov = size(moves,1);
if nmov == 0
ok = 1;
return
end
moves = moves(randperm(nmov),:);
for i=1:NFIDDLE
pos = cumsum([ipos; moves]);
okmov = min(find(any(findoverlaps(pos),2)))-1;
if isempty(okmov)
ok = 1;
return
end
indperm = localfiddler(pos(okmov,:),moves(okmov:nmov,:),w);
moves(okmov:nmov,:) = moves(okmov-1+indperm,:);
end
pos = cumsum([ipos; moves]);
okmov = min(find(any(findoverlaps(pos),2)))-1;
if isempty(okmov)
ok=1;
return
end
oldmoves = moves;
for i = 1:ceil(sqrt(nmov-okmov))
pos = cumsum([ipos; moves]);
overlap = findoverlaps(pos);
if ~any(overlap(:))
ok = 1;
return
else
oli = min(find(any(overlap,2)));
one = min(find(overlap(oli,:)));
other = max(find(overlap(oli,:)));
rowinds = [oli-1 ...
min(find(moves(:,one) & (1:nmov)'>=oli)) ...
min(find(moves(:,other) & (1:nmov)'>=oli)) ...
max(find(moves(:,one) & (1:nmov)'<oli-1)) ...
max(find(moves(:,other) & (1:nmov)'<oli-1))];
indperm = localfiddler(pos(oli-1,:),moves(rowinds,:),w);
moves(rowinds,:) = moves(rowinds(indperm),:);
end
end
pos = cumsum([ipos; moves]);
if min(find(any(findoverlaps(pos),2)))-1 < okmov
moves = oldmoves;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function indperm = localfiddler(ipos,mov,w)
M = 4;
[nmov,n] = size(mov);
if nmov <= M
M = nmov;
P = perms(1:M);
else
M = min(M,nmov);
inds = (M+1):nmov;
P = [perms(1:M) inds(ones(prod(2:M),1),:)];
for i=1:size(P,1)
P(i,M+1:nmov) = inds(randperm(nmov-M));
end
end
f = zeros(size(P,1),1);
for i=1:size(P,1)
newmov = mov(P(i,:),:);
pos = cumsum([ipos;newmov]);
overlap = findoverlaps(pos);
if ~any(overlap(:))
indperm = P(i,:);
return
else
p=any(overlap,1);
for c=1:n
if p(c)
f(i) = f(i)+w(c)*min(find(overlap(:,c)));
else
f(i) = f(i)+w(c)*nmov;
end
end
end
end
[DNC, best] = max(f);
indperm = P(best,:);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function overlaps = findoverlaps(pos)
[npos,n] = size(pos);
cols = find(all(pos));
pos = pos(:,cols);
A = zeros(npos,length(cols));
[sortpos, ind] = sort(pos,2);
ind1 = ind(:,1:end-1);
ind2 = ind(:,2:end);
dp = diff(sortpos,1,2)==0;
for i=1:npos
A(i,ind1(i,dp(i,:))) = true;
A(i,ind2(i,dp(i,:))) = true;
end
overlaps = zeros(npos,n);
overlaps(:,cols) = A;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [path] = dijkstra(n, s, d, R, optlen)
RELAX = 1;
[rows,cols,depth] = size(R);
R = R(:);
visited = false(1,n);
distance = inf*ones(1,n);
parent = zeros(1,n);
distance(s) = 0;
stack = zeros(1,n);
stack(1)=s;
next = 1;
last = 1;
for i = 1:(n-1),
if next>last
break
else
u = stack(next);
next = next + 1;
end
visited(u) = true;
ndx = u - 1;
k = floor(ndx/(rows*cols)) + 1;
ndx = rem(ndx, rows*cols);
col = floor(ndx/rows) + 1;
ndx = rem(ndx, rows);
row = floor(ndx) + 1;
v = u + 1;
if v>0 && v<=n && ~R(v) && row<rows
if distance(u) + 1 < distance(v)
distance(v) = distance(u) + 1;
parent(v) = u;
if ~visited(v)
if (v==d) && (distance(d) <= RELAX*optlen)
break
end
last = last + 1;
stack(last) = v;
end
end
end
v = u - 1;
if v>0 && v<=n && ~R(v) && row>1
if distance(u) + 1 < distance(v)
distance(v) = distance(u) + 1;
parent(v) = u;
if ~visited(v)
if (v==d) && (distance(d) <= RELAX*optlen)
break
end
last = last + 1;
stack(last) = v;
end
end
end
v = u + rows;
if v>0 && v<=n && ~R(v) && col<cols
if distance(u) + 1 < distance(v)
distance(v) = distance(u) + 1;
parent(v) = u;
if ~visited(v)
if (v==d) && (distance(d) <= RELAX*optlen)
break
end
last = last + 1;
stack(last) = v;
end
end
end
v = u - rows;
if v>0 && v<=n && ~R(v) && col>1
if distance(u) + 1 < distance(v)
distance(v) = distance(u) + 1;
parent(v) = u;
if ~visited(v)
if (v==d) && (distance(d) <= RELAX*optlen)
break
end
last = last + 1;
stack(last) = v;
end
end
end
v = u + rows*cols;
if v>0 && v<=n && ~R(v) && k < depth
if distance(u) < distance(v)
distance(v) = distance(u);
parent(v) = u;
if ~visited(v)
if (v==d) && (distance(d) <= RELAX*optlen)
break
end
last = last + 1;
stack(last) = v;
end
end
end
end
path = [];
if parent(d) ~= 0
t = d;
path = d;
while t ~= s
p = parent(t);
path = [p path];
t = p;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function mv = TLL79(Ai,Af,w)
global Dperfect CHECKER
I1=[];J1=[];I2=[];J2=[];for p=1:length(w);[i,j]=find(Ai==p);I1(p)=i;J1(p)=j;[i,j]=find(Af==p);I2(p)=i;J2(p)=j;end;Dperfect=sum(abs(I1-I2)+abs(J1-J2));
b=Ai;b(:)=1:numel(b);b=b.*rand(size(b));b=b(:);CHECKER=b;
n_blk = length(w);
[n_row,n_col] = size(Ai);
I = [0 1 0 -1];
J = [1 0 -1 0];
Ci = zeros(n_blk,2);
Cf = Ci;
for row = 1:n_row,
for col = 1:n_col,
b = Ai(row,col);
if b > 0,
Ci(b,:) = [row,col];
end
b = Af(row,col);
if b > 0,
Cf(b,:) = [row,col];
end
end
end
mv = solv(Ai,Af,w);
if size(mv,1)== Dperfect;return;end
mv_len = size(mv,1);
sc = sum(w(mv(:,1)));
dist = w' * sum(abs(Cf - Ci),2);
num_fail = 0;
max_try = 75;
max_fail = max_try;
for j_try = 1:max_try,
sc_old = sc;
A = Ai;
C = Ci;
j = 1;
while j < mv_len,
if (mv(j,1) == mv(j+1,1)) && (abs(mv(j,2) - mv(j+1,2)) == 2),
sc = sc - 2*w(mv(j,1));
mv = mv([1:j-1,j+2:mv_len],:);
mv_len = mv_len - 2;
if sc == dist,
return
end
else
if A(C(mv(j+1,1),1) + I(mv(j+1,2)),C(mv(j+1,1),2) + J(mv(j+1,2))) == 0,
mv([j j+1],:)=mv([j+1 j],:);
else
if j+3 <= mv_len,
if (mv(j,1) == mv(j+3,1)) && (abs(mv(j,2) - mv(j+3,2)) == 2)
b = mv(j,1);
sit = 0;
if (mv(j,1) == mv(j+1,1)) && (mv(j,1) == mv(j+2,1)) && (mv(j+1,2) == mv(j+2,2)),
b1 = A(C(b,1) + I(mv(j+1,2)),C(b,2) + J(mv(j+1,2)));
sit = 1;
else
if (mv(j,1) == mv(j+1,1)) && (mv(j,1) ~= mv(j+2,1)) && (abs(mv(j+1,2) - mv(j+2,2)) == 2),
b1 = mv(j+2,1);
sit = 1;
else
if (mv(j,1) ~= mv(j+1,1)) && (mv(j,1) == mv(j+2,1)) && (abs(mv(j+1,2) - mv(j+2,2)) == 2),
b1 = mv(j+1,1);
sit = 1;
else
if (mv(j,1) == mv(j+1,1)) && (mv(j,1) ~= mv(j+2,1)),
b1 = mv(j+2,1);
sit = 3;
else
if (mv(j,1) ~= mv(j+1,1)) && (mv(j,1) == mv(j+2,1)),
b1 = mv(j+1,1);
sit = 2;
end
end
end
end
end
if sit == 1,
if w(b1) < w(b),
mv(j,1) = b1;
mv(j+3,1) = b1;
sc = sc - 2*(w(b)-w(b1));
end
else
if sit ~= 0,
if A(C(b1,1) + I(mv(j+sit-1,2)),C(b1,2) + J(mv(j+sit-1,2))) == 0,
sc = sc - w(b) - w(b1);
mv(j:j+1,:) = mv([j+sit-1 j+4-sit],:);
mv = mv([1:j+1,j+4:end],:);
mv_len = mv_len - 2;
if sc == dist,
return
end
end
end
end
end
end
end
b = mv(j,1);
r = C(b,1);
c = C(b,2);
nr = r + I(mv(j,2));
nc = c + J(mv(j,2));
A(r,c) = 0;
A(nr,nc) = b;
C(b,1) = nr;
C(b,2) = nc;
j = j + 1;
end
end
if sc_old == sc,
num_fail = num_fail+1;
if num_fail == max_fail,
break
end
else
num_fail = 0;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function move = solv(aInit, aFinal, wt)
global Dperfect
o = [3; 4; 1; 2];
[move,score] = solverA(aInit, aFinal, wt);
if (score>100)||((length(move)-Dperfect)>3);
[mv2,score2] = solverA(aFinal, aInit, wt);
if score > score2
move = mv2(end:-1:1,:);
score = score2;
move(:,2)=o(move(:,2));
end
if (score>100)||((length(move)-Dperfect)>3);
a = aInit;
midmoves = floor(size(move,1)/2);
I = [0 1 0 -1];
J = [1 0 -1 0];
for k = 1:midmoves
[row, col] = find(a==move(k,1));
a(row,col) = 0;
% new position of the block
row = row + I(move(k,2));
col = col + J(move(k,2));
% place the block in the new position
a(row, col) = move(k,1);
end
oldscore1 = sum(wt(move(1:midmoves,1)));
oldscore2 = sum(wt(move(midmoves+1:size(move,1),1)));
[newmove,newscore] = solverA(aInit, a, wt);
[newmove2,newscore2] = solverA(a, aFinal, wt);
newscore1 = sum(wt(newmove(:,1)));
newscore2 = sum(wt(newmove2(:,1)));
oldmove = move;
if(newscore1 < oldscore1)
move = newmove;
if(newscore2 < oldscore2)
for itr = 1:size(newmove2,1)
move(end+1,[1 2]) = [newmove2(itr,1) newmove2(itr,2)];
end
else
for itr = midmoves+1:size(oldmove,1)
move(end+1,[1 2]) = [oldmove(itr,1) oldmove(itr,2)];
end
end
else
if(newscore2 < oldscore2)
move = [];
for itr = 1:midmoves
move(end+1,[1 2]) = [oldmove(itr,1) oldmove(itr,2)];
end
for itr = 1:size(newmove2,1)
move(end+1,[1 2]) = [newmove2(itr,1) newmove2(itr,2)];
end
end
end
end
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move,score] = solverA(aInit, aFinal, wt)
global Dperfect
[move,isPerfect,score]=solver2(aInit,aFinal,wt,1111);
if ~isPerfect;
move1=solver1(aInit,aFinal,wt,score);
if ( ~isempty(move1) )
isPerfect=length(move1)==Dperfect;
score1=sum(wt(move1(:,1)));
if score1<score;
score=score1;move=move1;
end;
end
end;
if ((length(move)-Dperfect)>5);
move1=solver33(aInit,aFinal,wt,1111,2);
if ( ~isempty(move1) )
isPerfect=length(move1)==Dperfect;
score1=sum(wt(move1(:,1)));
if score1<score;score=score1;
move=move1;
end;
end
end;
if isPerfect;score=0;end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function move = solver1(aInit, aFinal, wt, bscore)
allmoves = [];
wtinitori = wt;
sortbydist = 0;
sortbyweight = 1;
minw = 10000;
if sortbyweight
[tmp inds] = sort(-wt);
wtinit = wtinitori;
end;
lenwt = length(wt);
absx = zeros(lenwt,1);
absy = absx;
for index = 1:lenwt
[hvix hviy] = find(aInit == index);
[hvfx hvfy] = find(aFinal == index);
absx(index) = abs(hvix-hvfx);
absy(index) = abs(hviy-hvfy);
end;
if sortbydist
dist = abs(absx) + abs(absy);
[tmp inds] = sort(-dist);
wtinit = wtinitori;
end;
for index = 1:length(inds)
hv = inds(index);
[hvix hviy] = find(aInit == hv);
[hvfx hvfy] = find(aFinal == hv);
dist = abs(hvix-hvfx)+abs(hviy-hvfy);
wt(hv) = -Inf;
wtinit(hv) = wtinit(hv)+minw+10000;
[move cost aInit] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+5);
if isinf(cost) || isempty(move)
else
move = [move(:,1) 3*abs(move(:,4))-move(:,4)+2*abs(move(:,5))-move(:,5) ];
allmoves = [allmoves; move];
if ( sum(wtinitori(allmoves(:,1)))>bscore )
move=[];
return;
end
end;
end;
count = 1;
oldinds = [];
while ~isequal(aFinal,aInit)
sortbyweight = sortbydist;
sortbydist = ~sortbyweight;
if sortbyweight
inds = find(aFinal ~= aInit);
inds = aFinal(inds);
inds = inds(inds > 0);
[tmp indices] = sort(-wt(inds));
inds = inds(indices);
end;
if sortbydist
for index = 1:length(wt)
[hvix hviy] = find(aInit == index);
[hvfx hvfy] = find(aFinal == index);
dist(index) = abs(hvix-hvfx)+abs(hviy-hvfy);
end;
[tmp inds] = sort(-dist);
firstzeros = find(tmp == 0);
inds(firstzeros:end) = [];
end;
wtinit = wtinitori;
notmove = setdiff(oldinds, inds);
for hv = 1:length(notmove)
wtinit(notmove(hv)) = wtinit(notmove(hv))+minw+10000;
end;
for hind = 1:length(inds)
hv = inds(hind);
[hvix hviy] = find(aInit == hv);
[hvfx hvfy] = find(aFinal == hv);
dist = abs(hvix-hvfx)+abs(hviy-hvfy);
wtinit(hv) = wtinit(hv)+minw+10000;
[move cost aInit] = movefrompos(hv, [hvix hviy], [hvfx hvfy], aInit, aFinal, wtinit, 1, dist+6);
if hind > 1
wtinit(inds(hind-1)) = wtinit(inds(hind-1))-minw-10000;
end;
if isinf(cost) || isempty(move)
else
move = [move(:,1) 3*abs(move(:,4))-move(:,4)+2*abs(move(:,5))-move(:,5) ];
allmoves = [allmoves; move];
if ( sum(wtinitori(allmoves(:,1)))>bscore )
move=[];
return;
end
end;
end;
oldinds = inds;
count = count+1;
end;
move = allmoves;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move, cost, curposnew] = movefrompos(item, pinit, pfin, curpos, finpos, wt, strategy, recur)
cost = 0;
curposnew = curpos;
if isequal(pinit,pfin), move = []; return; end;
if recur == 0, move = []; cost = 0; return; end;
diffx = pfin(1)-pinit(1);
diffy = pfin(2)-pinit(2);
dirx = sign(diffx);
diry = sign(diffy);
cost = Inf;
if (strategy < 10 && abs(diffx) > abs(diffy)) || (strategy == 11 && abs(diffx) < abs(diffy))
if dirx && curpos(pinit(1)+dirx, pinit(2)) <= 0
[move cost curposnew] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end;
end;
if diry && curpos(pinit(1), pinit(2)+diry) <= 0
[move1 cost1 curposnew1] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
if length(move1) > 0 && cost1/size(move1,1) == mod(wt(curpos(pinit(1),pinit(2))),10000)
move=move1;
cost=cost1;
curposnew=curposnew1;
return;
end;
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
else
if diry && curpos(pinit(1), pinit(2)+diry) <= 0
[move cost curposnew] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
if length(move) > 0 && cost/size(move,1) == mod(wt(curpos(pinit(1),pinit(2))),10000), return; end;
end;
if dirx && curpos(pinit(1)+dirx, pinit(2)) <= 0
[move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
if length(move1) > 0 && cost1/size(move1,1) == mod(wt(curpos(pinit(1),pinit(2))),10000)
move=move1;
cost=cost1;
curposnew=curposnew1;
return;
end;
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
end;
if isinf(cost) || cost == 0
if dirx && diry && curpos(pinit(1), pinit(2)+diry) > 0 && curpos(pinit(1)+dirx, pinit(2)) > 0
[move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
[move1 cost1 curposnew1] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
else
if dirx && curpos(pinit(1)+dirx, pinit(2)) > 0
[move1 cost1 curposnew1] = onemove(item, pinit, [dirx 0], pfin, curpos, finpos, wt, strategy, recur);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
if diry && curpos(pinit(1), pinit(2)+diry) > 0
[move1 cost1 curposnew1] = onemove(item, pinit, [0 diry], pfin, curpos, finpos, wt, strategy, recur);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
end;
end;
if isinf(cost) && recur > 1 && abs(strategy) < 5
mv = [dirx diry];
mv1 = abs(mv)-1;
if any(mv1)
mv2 = abs(mv1);
mv3 = -mv;
ok3 = 1;
else
mv1 = [-mv(1) 0];
mv2 = [0 -mv(2)];
ok3 = 0;
end;
sz = size(curpos);
strategy = strategy + sign(strategy)*1;
if all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && ~curpos(pinit(1)+mv1(1),pinit(2)+mv1(2))
[move1 cost1 curposnew1] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
if all(pinit+mv2 > 0) && all(pinit+mv2 <= sz) && ~curpos(pinit(1)+mv2(1),pinit(2)+mv2(2))
[move1 cost1 curposnew1] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
if ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz) && ~curpos(pinit(1)+mv3(1),pinit(2)+mv3(2))
[move1 cost1 curposnew1] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
if all(pinit+mv1 > 0) && all(pinit+mv1 <= sz) && curpos(pinit(1)+mv1(1),pinit(2)+mv1(2)) > 0
[move1 cost1 curposnew1] = onemove(item, pinit, mv1, pfin, curpos, finpos, wt, strategy, recur-1);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
if all(pinit+mv2 > 0) && all(pinit+mv2 <= sz) && curpos(pinit(1)+mv2(1),pinit(2)+mv2(2)) > 0
[move1 cost1 curposnew1] = onemove(item, pinit, mv2, pfin, curpos, finpos, wt, strategy, recur-1);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
if ok3 && all(pinit+mv3 > 0) && all(pinit+mv3 <= sz) && curpos(pinit(1)+mv3(1),pinit(2)+mv3(2)) > 0
[move1 cost1 curposnew1] = onemove(item, pinit, mv3, pfin, curpos, finpos, wt, strategy, recur-1);
if cost1<cost
move = move1;
cost = cost1;
curposnew = curposnew1;
end
end;
end;
if isinf(cost)
move=[];
curposnew = curpos;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [move, cost, curpos] = onemove(item, pinit, movedir, pfin, curpos, finpos, wt, strategy, recur)
move3=0;
curcost = mod(wt(curpos(pinit(1), pinit(2))), 10000);
costnew3 = 0;
newpos = pinit+movedir;
if curpos(newpos(1), newpos(2)) > 0
if wt(curpos(newpos(1), newpos(2))) > 8000
cost = Inf;
move = [];
return;
end;
if wt(curpos(newpos(1), newpos(2))) > 2*curcost && recur > 0 && strategy > 0
tmppos1 = abs(movedir)-1 + pinit;
tmppos2 = abs(movedir)-1 + pinit;
tmppos3 = movedir + tmppos1;
tmppos4 = movedir + tmppos2;
sz = size(curpos);
wt2 = [0; wt];
curpos2 = curpos;
curpos2(curpos2 < 0) = 0;
curpos2 = curpos2+1;
tmpcost = [Inf Inf];
if all(tmppos1 > 0) && all(tmppos1 <= sz)
if all(tmppos3 > 0) && all(tmppos3 <= sz)
tmpcost(1) = wt2(curpos2(tmppos1(1), tmppos1(2))) + wt2(curpos2(tmppos1(1), tmppos1(2))) + 2*curcost;
end;
end;
tmpcost(2)=tmpcost(1);
if tmpcost(2) < wt(curpos(newpos(1), newpos(2)))
[move3 costnew3 curpostmp] = onemove(item, pinit, tmppos2-pinit, pfin, curpos, finpos, wt, strategy, -1);
if ~isinf(costnew3)
[move4 costnew4 curpostmp] = onemove(item, tmppos2, tmppos4-tmppos2, pfin, curpostmp, finpos, wt, strategy, -1);
if ~isinf(costnew4)
[move5 costnew5 curpostmp] = movefrompos(item, tmppos4, pfin, curpostmp, finpos, wt, -strategy, recur-1);
cost = costnew3 + costnew4 + costnew5;
move = [move3; move4; move5];
if ~isinf(cost), curpos = curpostmp; end;
return;
end;
end;
end;
end;
newitem = curpos(newpos(1), newpos(2));
[pfin2(1) pfin2(2)] = find(finpos == newitem);
dirx2 = sign(pfin2(1)-newpos(1));
diry2 = sign(pfin2(2)-newpos(2));
wt(newitem) = wt(newitem) + 20000;
if isequal([dirx2 diry2],-movedir) || isequal(newpos,pfin2)
costnew3 = Inf;
else
[move3 costnew3 curposnew] = movefrompos(newitem, newpos, pfin2, curpos, finpos, wt, strategy, -1);
if costnew3 == 0, costnew3 = Inf; end;
if ~isinf(costnew3), curpos = curposnew; end;
end;
if isinf(costnew3)
wtdir = [ Inf Inf Inf Inf ];
diffpos = pfin - newpos;
if (diffpos(1) && movedir(1)) || (diffpos(2) && movedir(2))
mv1 = abs(movedir)-1;
else
if any(sign(diffpos) > 0)
mv1 = abs(movedir)-1;
else
mv1 = abs(abs(movedir)-1);
end;
end;
mv2 = -mv1;
mv3 = movedir;
sz = size(curpos);
if all(newpos+mv1 > 0) && all(newpos+mv1 <= sz)
if curpos(newpos(1)+mv1(1),newpos(2)+mv1(2)) <= 0
[move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1);
else wtdir(1) = wt(curpos(newpos(1)+mv1(1),newpos(2)+mv1(2)));
end;
end;
if isinf(costnew3) && all(newpos+mv2 > 0) && all(newpos+mv2 <= sz)
if curpos(newpos(1)+mv2(1),newpos(2)+mv2(2)) <= 0
[move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1);
else wtdir(2) = wt(curpos(newpos(1)+mv2(1),newpos(2)+mv2(2)));
end;
end;
if isinf(costnew3) && all(newpos+mv3 > 0) && all(newpos+mv3 <= sz)
if curpos(newpos(1)+mv3(1),newpos(2)+mv3(2)) <= 0
[move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1);
else wtdir(3) = wt(curpos(newpos(1)+mv3(1),newpos(2)+mv3(2)));
end;
end;
if isinf(costnew3)
[wtdir si] = sort(wtdir);
for index = 1:length(wtdir)
if ~isinf(wtdir(index)) && isinf(costnew3)
switch si(index),
case 1, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv1, curpos, finpos, wt, strategy, -1);
case 2, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv2, curpos, finpos, wt, strategy, -1);
case 3, [move3 costnew3 curpos] = movefrompos(newitem, newpos, newpos+mv3, curpos, finpos, wt, strategy, -1);
end;
end;
end;
end;
end;
wt(newitem) = wt(newitem) - 20000;
if isinf(costnew3) || costnew3 == 0
cost = Inf;
move = [];
return;
end;
end;
if curpos(newpos(1), newpos(2)) == -item
cost = Inf;
move = [];
return;
end;
curpos(newpos(1), newpos(2)) = curpos(pinit(1), pinit(2));
curpos(pinit(1) , pinit(2) ) = -curpos(pinit(1), pinit(2));
if recur > 0
[move2 costnew curposnew] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, recur-1);
else
[move2 costnew curposnew] = movefrompos(item, pinit+movedir, pfin, curpos, finpos, wt, strategy, 0);
end;
curpos = curposnew;
if curpos(pinit(1), pinit(2))<0
curpos(pinit(1), pinit(2)) = 0;
end;
if numel(move3)==1 && isempty(move2);
move = [item pinit movedir];
elseif numel(move3)==1
move = [item pinit movedir; move2];
elseif isempty(move2)
move = [ move3; item pinit movedir];
else;
move = [ move3; item pinit movedir; move2];
end;
cost = costnew3+costnew+curcost;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [mv,perfectMV,score] = solver2(ai,af,w,states)
global TEST
global Ac Ar m2 Dperfect
perfectMV=false;
nBlocks = length(w);
[m,n] = size(ai);
m2=m+2;
n2=n+2;
A = -ones(m2,n2);
Af = A;
A( 2:m+1, 2:n+1 ) = ai;
Af( 2:m+1, 2:n+1 ) = af;
Ac=1:n2;
Ac=Ac(ones(m2,1),:);
Ar=(1:m2)';
Ar=Ar(:,ones(n2,1));
notPerfect=false;
if TEST
TEST=0;
Ax=A;
Ax(P(~bOK))=0;
%Pimp=zeros(nBlocks,1);
for i=1:nBlocks
if ~bOK(i)
[P1,f1]=SearchPath(Ax,P(i),Pf(i));
if ~isempty(f1)
% "impossible point"
%Pimp(i)=1;
Dperfect=Dperfect+2; % minimal increase
score=inf;
return
notPerfect=true;
break;
end
end
end
end
Pi=w;
Pf=w;
for i=m2+2:numel(A)-m2-1
if A(i)>0, Pi(A(i)) = i; end
if Af(i)>0, Pf(Af(i)) = i; end
end
P=Pi;
nmv=1;
mv = zeros(300,2);
nNOK=sum(P~=Pf);
Paths=zeros(m+n,nBlocks);
lPaths=w;
fPaths=w;
Pend=w;
bOK=w;
obs=zeros(nBlocks,2);
nmv0=0;
while nmv0<nmv&&nNOK
obs(:)=0;
nmv0=nmv;
for i=1:nBlocks
if P(i)==Pf(i)
lPaths(i)=0;
fPaths(i)=0;
bOK(i)=1;
else
[P1,f1]=SearchPath(A,P(i),Pf(i));
if isempty(P1)
lPaths(i)=0;
fPaths(i)=0;
obs(i,1:length(f1))=f1;
else
if isempty(f1)
fPaths(i)=1;
else
fPaths(i)=0;
obs(i,1:length(f1))=f1;
end
lPaths(i)=length(P1);
Paths(1:lPaths(i),i)=P1;
Pend(i)=P1(end);
end
bOK(i)=0;
end
end
iP=find(~bOK&lPaths);
PCol=zeros(length(iP));
L=lPaths(iP);
for i=1:length(iP)
Pe=Pend(iP(i));
for j=1:length(iP)
if i~=j
lj=L(j);
PCol(i,j)=any(Paths(1:lj,iP(j))==Pe);
end
end
end
sPCol=sum(PCol,2);
pOK=find(sPCol==0);
pNOK=find(sPCol~=0);
if isempty(pOK)
if length(pNOK)==1
pOK(end+1)=pNOK;
elseif ~isempty(pNOK)
if length(pNOK)>1&&any(fPaths(iP(pNOK)))
pNOK(~fPaths(iP(pNOK)))=[];
end
iNOK1=pNOK(find(sPCol(pNOK)==1));
for i=iNOK1'
j=find(PCol(i,:));
jj=iP(j);
p=iP(i);
pe=Pend(p);
A(P(p))=0;
A(pe)=p;
[P1,f1]=SearchPath(A,P(jj),Pf(jj));
A(P(p))=p;
A(pe)=0;
if isempty(f1)
pOK(end+1)=i;
break
end
end
end
end
if length(pOK)>1
obs1=abs(obs(:));
temp = zeros(1,length(obs1));
i=1;
q=0;
pOK1=pOK;
while i<=length(obs1)
temp(obs1==obs1(i))=1;
if sum(temp)>1
j=find(obs1==obs1(i));
obs1(j(2:end))=[];
end
if any(obs1(i)==pOK)
q=1;
j=find(obs1(i)==pOK);
pOK1(j)=0;
end
i=i+1;
end
if q
pOK(pOK1~=0)=[];
end
if length(pOK)>1&&any(fPaths(iP(pOK)))
pOK(~fPaths(iP(pOK)))=[];
end
end
j=1;
while j<=length(pOK)
i=pOK(j);
b=iP(i);
k=nmv+1:nmv+L(i);
mv(k,1)=b;
mv(k,2)=Paths(1:L(i),b);
nmv=nmv+L(i);
A(P(b))=0;
A(Pend(b))=b;
P(b)=Pend(b);
if fPaths(b)
nNOK=nNOK-1;
end
j=j+1;
end
end
P=Pi;
for i=2:nmv
b=mv(i);
p=mv(i,2);
dp=p-P(b);
if dp==1
mv(i,2)=2;
elseif dp==-1
mv(i,2)=4;
elseif dp==m2
mv(i,2)=1;
else
mv(i,2)=3;
end
P(b)=p;
end
mv=mv(2:nmv,:);
if nNOK
rand('state',states);
mv2=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score=sum(w(mv2(:,1)));
if notPerfect % not worth trying too much
perfectMV = Dperfect==size(mv,1);
mv=mv2;
return
end
rand('state',states*2);
mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score1=sum(w(mv1(:,1)));
if score1==score;
mv=mv2;
score=score1;
else
if score1<score;mv2=mv1;score=score1;end;
rand('state',states*371);
mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score1=sum(w(mv1(:,1)));
if score1<score;mv2=mv1;score=score1;end;
rand('state',states*173);
mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score1=sum(w(mv1(:,1)));
if score1<score;mv2=mv1;score=score1;end;
rand('state',states*1980);
mv1=[mv;Faster10IntReps2(A(2:m+1,2:n+1),af,w)];
score1=sum(w(mv1(:,1)));
if score1<score;mv2=mv1;score=score1;end;
mv=mv2;
end
perfectMV = Dperfect==size(mv,1);
else
score=sum(w(mv(:,1)));
perfectMV = 1;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [P,stopped]=SearchPath(A, p1, p2)
global Ac Ar m2
c1=Ac(p1);c2=Ac(p2);
r1=Ar(p1);r2=Ar(p2);
stopped=[];
P=zeros(sum(size(A)),1);
if r1>r2
d_r=-1;
elseif r1<r2
d_r=1;
else
d_r=0;
end
if c1>c2
d_c=-1;
elseif c1<c2
d_c=1;
else
d_c=0;
end
n=0;
p=p1;
if d_r==0||d_c==0
while p~=p2
np=p+d_c*m2+d_r;
if A(np)
stopped=A(np);
break
end
p=np;
n=n+1;
P(n)=p;
end
else
Ah=A;
c=c2;
i1=p2-d_r;
r_1=r2-d_r;
while c~=c1
r=r_1;
r_1=0;
i2=i1;
while r~=r1
if Ah(i2)
Afil=-Ah(i2);
if r==r2
r_1=r2;
i1=i2-d_c*m2;
else
r_1=r+d_r;
i1=i2-d_c*m2+d_r;
end
r=r-d_r;
i2=i2-d_r;
while r~=r1
if Ah(i2)==0
Ah(i2)=Afil;
end
r=r-d_r;
i2=i2-d_r;
end
if Ah(i2)==0
Ah(i2)=Afil;
end
break;
end
r=r-d_r;
i2=i2-d_r;
end
if r_1==0&&Ah(i2)
i1=i2-d_c*m2+d_r;
r_1=r+d_r;
end
c=c-d_c;
if r_1==0
break;
end
end
r=r2;
i1=p2-d_c*m2;
c_1=c2-d_c;
while r~=r1
c=c_1;
c_1=0;
i2=i1;
while c~=c1
if Ah(i2)
if Ah(i2)<0
Afil=Ah(i2);
else
Afil=-Ah(i2);
end
if c==c2
c_1=c2;
i1=i2-d_r;
else
c_1=c+d_c;
i1=i2-d_r+d_c*m2;
end
c=c-d_c;
i2=i2-d_c*m2;
while c~=c1
if Ah(i2)==0
Ah(i2)=Afil;
end
c=c-d_c;
i2=i2-d_c*m2;
end
if Ah(i2)==0
Ah(i2)=Afil;
end
break;
end
c=c-d_c;
i2=i2-d_c*m2;
end
if c_1==0&&Ah(i2)
i1=i2-d_r+d_c*m2;
c_1=c+d_c;
end
r=r-d_r;
if c_1==0
break;
end
end
while p~=p2
if c1~=c2&&Ah(p+m2*d_c)==0
di=m2*d_c;
dc=d_c;
dr=0;
elseif r1~=r2&&Ah(p+d_r)==0
di=d_r;
dc=0;
dr=d_r;
else
if c1==c2
stopped=Ah(p+d_r);
elseif r1==r2
stopped=Ah(p+m2*d_c);
else
stopped=[Ah(p+d_r) Ah(p+m2*d_c)];
end
break;
end
p=p+di;
n=n+1;
P(n)=p;
r1=r1+dr;
c1=c1+dc;
end
end
P=P(1:n);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function bmovelist = Faster10IntReps2(init,final,wts)
global Dperfect
numtimes = 8;
if(max(size(init)) > 30) && max(size(wts))/(size(init,1)*size(init,2))>0.25
numtimes = 10;
elseif(max(size(init)) > 30)
numtimes = 7;
elseif(max(size(init)) < 11)
numtimes = 2;
end
bscore=1e20;
for repcount = 1:numtimes
[movelist,c] = matrixsolver(init,final,wts);
bf = length(wts)+1+zeros(size(init)+2);
bf(2:end-1,2:end-1) = final;
tries = 1;
maxtries = 15;
while ~isequal(c,bf) && (tries < maxtries)
randwts = rand(size(wts));
[addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),final,randwts);
movelist = [movelist;addtomovelist];
tries = tries+1;
end
if ~isequal(c,bf)
movegoaltries = 0;
while ~isequal(c,bf) && (movegoaltries<20)
problemboxes = c(c~=bf & c~=0);
openspots = find(c==0);
tempfinal = bf;
for i = 1:length(problemboxes)
cgind = find(bf==problemboxes(i));
tempfinal(cgind) =0;
newind = ceil(rand*length(openspots));
tempfinal(openspots(newind)) = problemboxes(i);
openspots(newind) = [];
end
randwts = rand(size(wts));
[addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),tempfinal(2:end-1,2:end-1),randwts);
movelist = [movelist;addtomovelist];
movegoaltries = movegoaltries+1;
aftermovegoaltries = 0;
while ~isequal(c,bf) && aftermovegoaltries<5
randwts = rand(size(wts));
[addtomovelist,c] = matrixsolver(c(2:end-1,2:end-1),final,randwts);
movelist = [movelist;addtomovelist];
aftermovegoaltries = aftermovegoaltries+1;
end
end
end
score = sum(wts(movelist(:,1)));
if score<bscore
bmovelist = movelist;
if length(bmovelist)==Dperfect;perfectMV=true;return;end;
bscore=score;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [movelist,c] = matrixsolver(init,final,wts)
biggermatrix = length(wts)+1+zeros(size(init)+2);
bi = biggermatrix;
bf = bi;
bi(2:end-1,2:end-1) = init;
bf(2:end-1,2:end-1) = final;
c = bi;
[m,n] = size(c);
numboxes = length(wts);
[DNC,wtorder] = sort(wts);
movelist = zeros(0,2);
for i = 1:numboxes
cbn = wtorder(i);
cr = 0; cc = 0; fr = 0; fc = 0;
for j=2:m-1,
for k=2:n-1,
if c(j,k)==cbn, cr = j; cc = k; if fr>0, break; end;end;
if bf(j,k)==cbn, fr = j; fc = k; if cr>0, break; end; end
end
if fr>0&&cr>0, break; end
end
dr = fr-cr;
dc = fc-cc;
while dr~=0 || dc~=0
neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)];
opendirs = find(~neighborhood);
desireddirs = [];
if dr~=0
desireddirs(end+1) = -sign(dr)+3;
end
if dc~=0
desireddirs(end+1) = -sign(dc)+2;
end
pic = opendirs(ismember1(opendirs,desireddirs));
if ~isempty(pic)
if length(pic)>1
if abs(dr)>abs(dc)
movedir = desireddirs(1);
else
movedir = desireddirs(2);
end
else
movedir = pic;
end
else
ind = ceil(rand*length(desireddirs));
boxtomove = neighborhood(desireddirs(ind));
switch desireddirs(ind)
case {1,3}
rcaxis = -1;
case {2,4}
rcaxis = 1;
end
[c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf);
ootwtries = 1;
while rejectflag && ootwtries<10
[c,movelist,rejectflag] = outoftheway(boxtomove,rcaxis,cbn,c,movelist,bf);
ootwtries = ootwtries+1;
end
movedir = desireddirs(ind);
end
c(cr,cc) = 0;
switch movedir
case 1
cc = cc+1;
case 2
cr = cr+1;
case 3
cc = cc-1;
case 4
cr = cr-1;
end
c(cr,cc) = cbn;
movelist(end+1,:) = [cbn,movedir];
dr = fr-cr;
dc = fc-cc;
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [c,movelist,rejectflag] = outoftheway(boxnumber,rcaxis,dontmovetheseboxes,c,movelist,bf)
c_in = c;
movelist_in = movelist;
rejectflag = 0;
[cr,cc] = find(c==boxnumber);
neighborhood = [c(cr,cc+1),c(cr+1,cc),c(cr,cc-1),c(cr-1,cc)];
opendirs = find(~neighborhood);
if isempty(opendirs)
switch rcaxis
case -1
bettercandidates = neighborhood([2,4]);
worsecandidates = neighborhood([1,3]);
case 1
bettercandidates = neighborhood([1,3]);
worsecandidates = neighborhood([2,4]);
end
wallnum = c(1,1);
remainingcandidates = setdiff(bettercandidates,[dontmovetheseboxes,wallnum]);
if isempty(remainingcandidates)
remainingcandidates = setdiff(worsecandidates,[dontmovetheseboxes,wallnum]);
if isempty(remainingcandidates)
rejectflag = 1;
c = c_in;
movelist = movelist_in;
return
end
end
if length(remainingcandidates)>1
remainingcandidates = remainingcandidates((rand>.51)+1);
end
[c,movelist,rejectflag] = outoftheway(remainingcandidates,-rcaxis,[dontmovetheseboxes,boxnumber],c,movelist,bf);
if rejectflag
c = c_in;
movelist = movelist_in;
return
end
movedir = find(neighborhood==remainingcandidates);
else
[cr,cc] = find(c==boxnumber);
[fr,fc] = find(bf==boxnumber);
dr = fr-cr;
dc = fc-cc;
desireddirs = [];
if dr~=0
desireddirs(end+1) = -sign(dr)+3;
end
if dc~=0
desireddirs(end+1) = -sign(dc)+2;
end
pic = opendirs(ismember1(opendirs,desireddirs));
if ~isempty(pic)
if length(pic)>1
if abs(dr)>abs(dc)
movedir = desireddirs(1);
else
movedir = desireddirs(2);
end
else
movedir = pic;
end
else
movedir = opendirs(ceil(rand*length(opendirs)));
end
end
c(cr,cc) = 0;
switch movedir
case 1
cc = cc+1;
case 2
cr = cr+1;
case 3
cc = cc-1;
case 4
cr = cr-1;
end
c(cr,cc) = boxnumber;
movelist(end+1,:) = [boxnumber,movedir];
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function mv = checksummer(ai,mv,n,I1,J1)
global CHECKER
I = [0 1 0 -1];
J = [1 0 -1 0];
a = ai;
for k = 1:size(mv,1);
row=I1(mv(k,1));col=J1(mv(k,1));
a(row,col) = 0;
row = row + I(mv(k,2));
col = col + J(mv(k,2));
if (a(row,col) ~= 0);return;end;
I1(mv(k,1))=row;J1(mv(k,1))=col;
a(row, col) = mv(k,1);
chk(k)=sum(CHECKER.*a(:));
end
while 1;
a=sort(chk);a=a(diff(a)==0);
if isempty(a);break;end;
idx=find(chk==a(1));
mv(idx(1)+1:idx(end),:)=[];chk(idx(1)+1:idx(end))=[];
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function mv = solver3(ai,af,w,states)
global mv a airow aicol afrow afcol rowDis colDis I J b m n wn Dperfect
mv = [];
aiMap = ai>0;
a = ai;
[m,n] = size(aiMap);
aiBlock = ai(aiMap);
nBlocks = length(aiBlock);
[aiOrder, aiPos] = sort(aiBlock);
[airow,aicol] = find(aiMap);
airow = airow(aiPos);
aicol = aicol(aiPos);
w0 = w;
w = w(aiPos);
wn = w;
afMap = af>0;
[afOrder, afPos ] = sort( af(afMap) );
[afrow,afcol] = find(afMap);
afrow = afrow(afPos);
afcol = afcol(afPos);
rowDis = airow-afrow;
colDis = aicol-afcol;
[nw,nd]=sort(-w);
I = [0 1 0 -1];
J = [1 0 -1 0];
recurP = [1:4; 3 4 1 2; 1:4];
iter = 0;
while (iter<2) && (( sum(abs(rowDis) + abs(colDis))>0 ) > 0)
iter = iter + 1;
for irr = 1:nBlocks
ir = nd(irr);
priority = 0;
len=0;
iterr = 0;
while (iterr < 10) && (abs(rowDis(ir))+abs(colDis(ir)) > 0)
iterr = iterr+1;
b=ai*0;
x = airow(ir);
y = aicol(ir);
b(x,y) = ir;
if ~chainMV( ir,priority )
break;
end;
len = len+1;
if len>3
if all( mv(end:-1:end-2,1) == ir ) && any( all( mv(end:-1:end-2,[2 2 2 2]) == recurP ) )
priority = Inf;
mv(end-1:end,:) = [];
end;
end
end
end
end
res = sum(abs(rowDis) + abs(colDis));
if res > 0
rand('state',states);mv1=[mv;Faster10IntReps2(a,af,w0)];score=sum(w(mv1(:,1)));
if ((length(mv1)-Dperfect)>1)&&(score>4450);rand('state',states*2);mv2=[mv;Faster10IntReps2(a,af,w0)];score1=sum(w(mv2(:,1)));if score1<score;mv1=mv2;end;end;
mv=mv1;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function isMovable = chainMV( ir , priority)
global mv a airow aicol rowDis colDis I J b m n wn
isMovable = 0;
x = airow(ir);
y = aicol(ir);
disr = rowDis(ir);
disc = colDis(ir);
if (priority>wn(ir))||(abs(disr)+abs(disc)>0)
mvDirects = ( disr * I + disc * J );
[DNC, mvInd] = sort(mvDirects);
for k = 1:2
i = I(mvInd(k));
j = J(mvInd(k));
nx = x + i;
ny = y + j;
succMv = 0;
if (nx>0) && (nx<=m) && (ny>0) && (ny<=n)
if a(nx,ny) == 0
succMv = 1;
else
if b(nx,ny) == 0
b(nx,ny) = 1;
succMv = chainMV( a(nx,ny) , priority );
else
b(nx,ny) = 0;
end;
end;
end;
if succMv == 1
airow(ir) = nx;
aicol(ir) = ny;
rowDis(ir) = rowDis(ir) + I(mvInd(k));
colDis(ir) = colDis(ir) + J(mvInd(k));
a(x,y) = 0;
a(nx,ny) = ir;
mv(end+1,:) = [ir,mvInd(k)];
isMovable = 1;
break;
end;
end;
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [tf,loc] = ismember(a,s)
numelA = numel(a);
numelS = numel(s);
if numelA == 0 || numelS <= 1
if (numelA == 0 || numelS == 0)
tf = false(size(a));
loc = zeros(size(a));
return
elseif numelS == 1
tf = (a == s);
loc = double(tf);
return
end
else
tf = false(size(a));
loc = zeros(size(a));
for i=1:numelA
found = find(a(i)==s(:));
if ~isempty(found)
tf(i) = 1;
loc(i) = found(end);
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [tf] = ismember1(a,s)
numelA = numel(a);
numelS = numel(s);
if numelA == 0 || numelS <= 1
if (numelA == 0 || numelS == 0)
tf = false(size(a));
return
elseif numelS == 1
tf = (a == s);
return
end
else
tf = false(size(a));
for i=1:numelA
found = (a(i)==s(:));
if any(found)
tf(i) = 1;
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [c] = setdiff(a,b)
c = unique(a(~(ismember(a(:),b(:)))));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [b] = unique(a)
numelA = numel(a);
if numelA<2
b = a;
else
b = sort(a);
db = diff(b);
d = db ~= 0;
d(numelA) = true;
b = b(d);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function ndx = sub2ind(siz,varargin)
siz = [siz ones(1,nargin-length(siz)-1)];
mt = cellfun('isempty',varargin);
if any(mt)
ndx = zeros(~mt);
return;
end
k = [1 cumprod(siz(1:end-1))];
ndx = 1;
for i = 1:length(siz),
v = varargin{i};
ndx = ndx + (v-1)*k(i);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function p = randperm(n)
[DNC,p] = sort(rand(1,n));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function P = perms(V)
V = V(:).';
n = length(V);
if n <= 1, P = V;
return;
end
q = perms(1:n-1);
m = size(q,1);
P = zeros(n*m,n);
P(1:m,:) = [n * ones(m,1) q];
for i = n-1:-1:1
t = q;
t(t == i) = n;
P((n-i)*m+1:(n-i+1)*m,:) = [i*ones(m,1) t];
end
P = V(P);
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function move = optimize(ai,move1)
ty = [0 1 0 -1];
tx = [1 0 -1 0];
op = [3 4 1 2];
move = move1;
move1 = zeros(0,2);
while size(move,1) ~= size(move1,1)
w = zeros(size(ai));
i = 1;
move1 = move;
a = ai;
while i <= length(move)
w = w + 1;
f = move(i,1);
d = move(i,2);
[y,x] = find(a == f);
y2 = y + ty(d);
x2 = x + tx(d);
a(y,x) = 0;
a(y2,x2) = f;
h = find(move(1:i-1,1) == f);
for z = (2*floor((length(h)+1)/2)):-2:2
zh = z/2;
da = sort([d;(move(h(end-zh+2:end),2))]);
db = move(h(end-z+2:end-zh+1),2);
if all(da' == sort(op(db)))
if w(y2,x2) == (i-h(end-z+2)+1)
move(i,:) = [];
move(h(end-z+2:end),:) = [];
i = i - z;
w = w - z;
break;
end
end
end
w(a>0) = 0;
i = i + 1;
end
end
function mv = solver33(ai,af,w,states,maxIter)
global mv a airow aicol afrow afcol rowDis colDis I J b m n wn Dperfect curDepth
mv = [];
aiMap = ai>0;
a = ai;
[m,n] = size(aiMap);
aiBlock = ai(aiMap);
nBlocks = length(aiBlock);
[aiOrder, aiPos] = sort(aiBlock);
[airow,aicol] = find(aiMap);
airow = airow(aiPos)';
aicol = aicol(aiPos)';
wn = w;
afMap = af>0;
[afOrder, afPos ] = sort( af(afMap) );
[afrow,afcol] = find(afMap);
afrow = afrow(afPos)';
afcol = afcol(afPos)';
rowDis = airow-afrow;
colDis = aicol-afcol;
[nw,nd]=sort(-w);
I = [0 1 0 -1];
J = [1 0 -1 0];
iter = 0;
while (iter<maxIter) && ( ( sum(abs(rowDis) + abs(colDis))>0 ) > 0 )
iter = iter + 1;
for irr = 1:nBlocks
ir = nd(irr);
priority = 1; %in 2nd iteration, implement more forcible movement
iterr = 0;
curDepth = 0;
odis = abs(rowDis(ir))+abs(colDis(ir)) ;
while (iterr < odis) && (abs(rowDis(ir))+abs(colDis(ir)) > 0)
if iter == 0
priority = 1;
else
priority = rand;
end;
iterr = iterr+1;
b=ai*0;
x = airow(ir);
y = aicol(ir);
b(x,y) = ir;
if ~chainMV1( ir, priority, w(ir) )
break;
end;
end
end
end
res = sum(abs(rowDis) + abs(colDis));
if res > 0
rand('state',states);
mv1=[mv;Faster10IntReps2(a,af,w)];
score=sum(w(mv1(:,1)));
if ((length(mv1)-Dperfect)>1)&&(score>4450);
rand('state',states*2);
mv2=[mv;Faster10IntReps2(a,af,w)];
score1=sum(w(mv2(:,1)));
if score1<score;
mv1=mv2;
end;
end;
mv=mv1;
end;
function isMovable = chainMV1( ir , priority, prew )
global mv a airow aicol rowDis colDis I J b m n wn curDepth
curDepth == curDepth + 1;
isMovable = 0;
x = airow(ir);
y = aicol(ir);
disr = rowDis(ir);
disc = colDis(ir);
if ( abs( disr ) + abs( disc ) > 0 ) || ( priority*prew - wn(ir)>0 )
mvDirects = ( disr * I + disc * J );
[goodMv, mvInd] = sort(mvDirects);
for k = 1:2
succMv = 0;
if (curDepth == 1) && (k > 1)
if goodMv(k) >= 0
break;
end;
end;
i = I(mvInd(k));
j = J(mvInd(k));
nx = x + i;
ny = y + j;
if (nx>0) && (nx<=m) && (ny>0) && (ny<=n)
if a(nx,ny) == 0
succMv = 1;
else
if b(nx,ny) == 0
b(nx,ny) = 1;
succMv = chainMV1( a(nx,ny) , priority, wn(ir) );
if ~succMv
b(nx,ny) = 0;
end;
end;
end;
end;
if succMv == 1
airow(ir) = nx;
aicol(ir) = ny;
rowDis(ir) = rowDis(ir) + I(mvInd(k));
colDis(ir) = colDis(ir) + J(mvInd(k));
a(x,y) = 0;
a(nx,ny) = ir;
mv(end+1,:) = [ir,mvInd(k)];
isMovable = 1;
break;
end;
end;
end;
|
