KickOff10

function mv = solver(ai,af,w)

rand('state',10);
nBlocks = length(w);
[m,n] = size(ai);
[Ii,Ji,si]=find(sparse(ai));
[si,k]=sort(si);
Ii=Ii(k);
Ji=Ji(k);
[If,Jf,sf]=find(sparse(af));
[sf,k]=sort(sf);
If=If(k);
Jf=Jf(k);
mB=sum(Ii-If | Ji-Jf);

% Make increment tables
% N=1, E=2, S=3, W=4
I = [0  1  0 -1];
J = [1  0 -1  0];

mv = [];
while mB

    % Pick a random block
    bid = ceil(rand*nBlocks);
    i=Ii(bid);
    j=Ji(bid);

    % Move it in a random direction
    ni = i + I;
    nj = j + J;

    % Is it a legal move? Check edges
    K = find((ni<1) | (ni>m) | (nj<1) | (nj>n));

    % Is it a legal move? Check for collision
    for k=1:length(ni);
        if any(K==k)
            continue
        end
        if any(Ii==ni(k) & Ji==nj(k))    
            K=[K k];
        end
    end
    r=1:4;
    r(K)=[];
    ni(K)=[];
    nj(K)=[];
    if isempty(ni)
        continue
    end
    mn=ceil(rand*length(r));
    ni=ni(mn);
    nj=nj(mn);
    r=r(mn);

    % Check distance
    % Get the target location
    ti=If(bid);
    tj=Jf(bid);
    d = abs(ti-i) + abs(tj-j);
    dn = abs(ti-ni) + abs(tj-nj);
    % Have we moved closer to the target location?
    if (d<dn) && (rand>0.05)
        continue
    end

    % Move the block
     Ii(bid)=ni;
     Ji(bid)=nj;

    % Record the move
    mv(end+1,[1 2]) = [bid r];
    mB=sum(Ii-If | Ji-Jf);

end