Cody

Problem 1978. Sokoban: Puzzle 10.45

Solution 3021247

Submitted on 1 Oct 2020 by Richard Zapor
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

Test Suite

Test Status Code Input and Output
1   Pass
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)));

Solved : Depth 27 Moves 100 -1 -8 -8 -8 1 1 8 1 -8 -1 -1 -1 8 1 8 -8 -8 1 1 8 -1 -8 -1 -1 8 8 1 -8 -1 -8 1 1 8 1 8 -1 -8 -1 -1 8 8 8 1 1 -8 8 -1 -1 -8 1 -8 -8 -1 -8 1 8 1 -8 8 1 8 -1 -8 -1 8 -1 8 8 1 1 -8 -8 1 -8 -1 8 -1 -8 -1 -8 1 8 8 -1 8 1 8 1 -8 -1 -8 -8 1 1 8 -1 8 -1 -8 -8 Solved Elapsed time is 0.159703 seconds. Moves 100 Pushes 27

Suggested Problems

More from this Author246

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!