Cody

Problem 1978. Sokoban: Puzzle 10.45

Solution 593361

Submitted on 7 Mar 2015 by Paul Berglund
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
assignin('caller','score',200);

2   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)));

Elapsed time is 3.035702 seconds. Moves 66 Pushes 19

Suggested Problems

More from this Author241

Community Treasure Hunt

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

Start Hunting!