visualize=0; if visualize figure(1); % Start map=[.5 .5 .5;0 0 0;.5 .5 .5;0 1 0;0 0 1; 1 0 0;1 1 0;0 0 0;1 0 1;.5 .5 .5]; colormap(map); figure(2); % Move map % -1 0 1 2 3 4 5 6 7 8 % -1 color limit, 8 color limit % 0 Empty; 1 Wall; 2 Block; 3 Pedestal; % 4 Sokoban; 5 Block & Pedestal;6 Nothing; 7 Soko & Pedestal colormap(map) end %Sokoban map http://www.game-sokoban.com/index.php?mode=level&lid=16138 %Puzzle 45 smap=[0 0 0 0 0 0;0 3 2 2 4 0;3 3 2 0 2 0;3 5 0 0 1 1]; [nr,nc]=size(smap); m=ones(nr+4,nc+4); m(3:end-2,3:end-2)=smap; if visualize im=m; mend=size(map,1)-2; im(1)=-1;im(end)=mend; figure(1);imagesc(im) m end tic moves=solve_Sokoban(m); toc % Check Solution valid=1; ptr=find(m==4); pushes=0; if isempty(ptr),ptr=find(m==7);end for i=1:length(moves) mv=moves(i); mvptr=m(ptr+mv); mvptr2=m(ptr+2*mv); if mvptr==1 % Illegal run into wall valid=0; break; end if (mvptr2==5 || mvptr2==2 || mvptr2==1) && (mvptr==5 || mvptr==2) % Illegal double block push valid=0; break; end if mvptr==0 || mvptr==3 m(ptr)=m(ptr)-4; m(ptr+mv)=m(ptr+mv)+4; ptr=ptr+mv; elseif mvptr==2 || mvptr==5 m(ptr)=m(ptr)-4; m(ptr+2*mv)=m(ptr+2*mv)+2; m(ptr+mv)=m(ptr+mv)-2+4; ptr=ptr+mv; pushes=pushes+1; end end fprintf('Moves %i Pushes %i\n',length(moves),pushes) valid=valid && nnz(m==3)==0 && nnz(m==7)==0; assert(valid) if visualize && valid % display moves figure(2);imagesc(im) pause(0.2) ptr=find(im==4); if isempty(ptr),ptr=find(im==7);end for i=1:length(moves) mv=moves(i); mvptr=im(ptr+mv); if mvptr==0 || mvptr==3 im(ptr)=im(ptr)-4; im(ptr+mv)=im(ptr+mv)+4; ptr=ptr+mv; elseif mvptr==2 || mvptr==5 im(ptr)=im(ptr)-4; im(ptr+2*mv)=im(ptr+2*mv)+2; im(ptr+mv)=im(ptr+mv)-2+4; ptr=ptr+mv; end figure(2);imagesc(im) pause(0.2) end end % vis and valid movs=length(moves); assignin('caller','score',min(200,max(0,movs+pushes)));