% Ovaj program generise 15-slagalicu. Prazno mesto je obelezeno nulom.
% Posle racunar nasumicno vuce poteze dok se ne stigne do ciljnog stanja.
clear

B=randperm(9)-1;        %randperm(16)-1
A=reshape(B,3,3)       %reshape(B,4,4)
[i j]=find(A==0);

% A=[2 15 13 11; 10 3 14 7; 12 8 6 1; 9 4 5 0];
% [i j]=find(A==0);

while i~=3              %(while i~=4) prazno mesto (0) prvo pomeramo prema dole
    A(i,j)=A(i+1,j);
    A(i+1,j)=0;
    [i j]=find(A==0);
end

while j~=3              % (while j~=4) prazno mesto (0) pomeramo prema desno
    A(i,j)=A(i,j+1);
    A(i,j+1)=0;
    [i j]=find(A==0);
end

% Sad je prazno mesto (0) u donjem desnom uglu
% Sledece cemo ispitati da li za ovaj raspored mozemo sloziti 
% slagalicu u prirodnom redosledu. Ako je broj inverzija paran, onda ima
% resenja
C=A';
D=reshape(C,1,9);       % D=reshape(C,1,16);
D(9)=[];                % D(16)=[];

clear i j
num_inv=0;

for j=1:7               % for j=1:14
    for i=j+1:8         % for i=j+1:15
       if D(i)<D(j)
           num_inv=num_inv+1;
       end
    end
end

% if mod(num_inv,2)~=0
%     disp ('Ova slagalica nema resenje')
% else
%     disp ('Ova slagalica ima resenje')
% end

if mod(num_inv,2)~=0
    disp ('Ova slagalica nije resiva')
    return;
end

count=0;
 
while (A(1,1)~=1 || A(1,2)~=2 || A(1,3)~=3 || A(2,1)~=4 || A(2,2)~=5 || A(2,3)~=6 ...
        || A(3,1)~=7 || A(3,2)~=8) 
    [x y]=find(A==0);

    direction=ceil(4*rand);
    if (direction==1  && x~=1)   %hole up
        A(x,y)=A(x-1,y);
        A(x-1,y)=0;
        count=count+1;
    end
    if (direction==2 && x~=3)    %hole down
        A(x,y)=A(x+1,y);
        A(x+1,y)=0;
        count=count+1;
    end
    if (direction==3 && y~=1)    %hole left
        A(x,y)=A(x,y-1);
        A(x,y-1)=0;
        count=count+1;
    end
    if (direction==4 && y~=3)     %hole right
        A(x,y)=A(x,y+1);
        A(x,y+1)=0;
        count=count+1;
    end
end
% all elements in correct places

% clear x y i j
% [x y]=find(A==0);
% 
% while y~=3              % (while y~=4) prazno mesto (0) pomeramo prema desno
%     A(x,y)=A(x,y+1);
%     A(x,y+1)=0;
%     [x y]=find(A==0);
% end
A
count