一个简单的手机推箱子游戏图，自己没找到答案，只好编程求解了。复制代码后，以文件名move_box.m存盘，即可在matlab中执行。每次按下回车键，就会移动一次箱子。修改文件中的grds，可求解其他格局的问题。工人路径没有优化，所以有重复移动的现象。用C++实现的话，只需要5秒钟可求解。
function [x]=move_box()set(0,'RecursionLimit',1000);clc;global tar grds MAX_BOXES MAX_STEPS his total_steps;% 箱子的目标位置，用于判断是否成功% 每一行是一个箱子的下标tar = [4,3;4,4;4,6;6,6];% 历史数据，避免再进入同一格局his = containers.Map;% 总步数，用于显示进度total_steps = 0;%{把每次移动得到的结果称为一个格局。问题的初始格局和目标格局分别为 o o o o o o o o o o o o o o o o o o . X . o o o o o . . . o o o o o . o B . . o o o . o . . . o o . B . . . . o o . B B . B . o o . . B B . o o o . . . . . o o o o o . o . o o o o o . o B o o o o o . . . o o o o o . . . o o o o o o o o o o o o o o o o o o约定 B -- 箱子 o -- 墙壁 X -- 工人 . -- 空白%}% 最大步数MAX_STEPS = 1000;% 箱子个数MAX_BOXES = 4;% 格局grds(8,8,MAX_STEPS)=0;grds(:,:,1)=[ 'oooooooo'; 'oo.X.ooo'; 'oo.oB..o'; 'o.B....o'; 'o..BB.oo'; 'ooo.o.oo'; 'ooo...oo'; 'oooooooo'];% 计算工人位置[x,y]=find(grds(:,:,1)=='X');% 求解s = test(1,x,y);if s > 0 for i = 1:s print_grd(i); fprintf(1,'\n'); pause; endelse fprintf(1, 'failed\n');endend% 判断是否成功function [res] = is_succ(step)global MAX_BOXES tar grds;% 检查每一个目标位置是否都有箱子res = true;for i = 1:MAX_BOXES if grds(tar(i,1),tar(i,2),step) ~= 'B' res = false; break; end;end;end% 打印格局function print_grd(step)global grds;for i=1:8 for j=1:8 fprintf(1,'%c ',char(grds(i,j,step))); end fprintf(1,'\n');endend% 判断是否可以沿方向d移动function [res] = can_move(d, step, x, y)global grds;% d的取值为1到4的整数，分别表示上下左右四个方向switch d % 向上移动 case 1 % 上方是墙壁吗？ if grds(x-1,y,step) == 'o' % 返回不能移动 res = false; % 上方是空白吗? elseif grds(x-1,y,step) == '.' % 返回可以移动 res = true; % 上方既不是墙壁、也不是空白，那么只能是箱子 else % 如果箱子上方是空白，则能移动，否则不能移动 res = grds(x-2,y,step) == '.'; end; case 2 if grds(x+1,y,step) == 'o' res = false; elseif grds(x+1,y,step) == '.' res = true; else res = grds(x+2,y,step) == '.'; end case 3 if grds(x,y-1,step) == 'o' res = false; elseif grds(x,y-1,step) == '.' res = true; else res = grds(x,y-2,step) == '.'; end; case 4 if grds(x,y+1,step) == 'o' res = false; elseif grds(x,y+1,step) == '.' res = true; else res = grds(x,y+2,step) == '.'; endendend% 按方向d计算step+1步的新格局function move(d, step, x, y)global grds;% 新格局位于grds[step + 1]处，大多数元素与grds[step]相同grds(:,:,step+1) = grds(:,:,step);switch (d) case 1 % 工人上方是箱子 if grds(x-1,y,step+1)=='B' % 箱子上移 grds(x-2,y,step+1) = 'B'; end; % 工人上移 grds(x-1,y,step+1) = 'X'; case 2 if grds(x+1,y,step+1) == 'B' grds(x+2,y,step+1) = 'B'; end grds(x+1,y,step+1) = 'X'; case 3 if grds(x,y-1,step+1) == 'B' grds(x,y-2,step+1) = 'B'; end grds(x,y-1,step+1) = 'X'; case 4 if grds(x,y+1,step+1) == 'B' grds(x,y+2,step+1) = 'B'; end grds(x,y+1,step+1) = 'X';end% 工人原来的位置变为空白grds(x,y,step+1) = '.';end% 把格局变为字符串function [res]=get_key(step, x, y)global grds;x = ['0'+x,',','0'+y];for i = 2:7 for j = 2:7 if grds(i,j,step) == 'B' x = [x,',','0'+i,',','0'+j]; end endendres = char(x);end% 是否是老格局，如果不是，在his中记录function [res]=is_dup(step, x, y)global his;k = get_key(step,x,y);try % 如果是新格局会抛出异常 his(k); res = true;catch res = false; % 在his中记录新格局，1并无实际意义 his(k) = 1;end;end% 搜索，处理第step步移动function [res] = test(step, x, y)global MAX_STEPS total_steps;res = step;total_steps = total_steps+1;if mod(total_steps,1000)==0 fprintf(1,'total_steps = %d\n', total_steps);end% 超出搜索范围，做失败处理if (step > MAX_STEPS) fprintf(1,'too deep\n'); res = 0; return;end;% 成功if is_succ(step) return;end% 沿上下左右四个方向搜索一步for d = 1:4 % 判断是否可以沿方向d移动 if can_move(d, step, x, y) == false continue; end; % 执行沿方向d的移动 move(d, step, x, y); x1 = x; y1 = y; switch d case 1 x1 = x - 1; case 2 x1 = x + 1; case 3 y1 = y - 1; case 4 y1 = y + 1; end % 判断移动后是否为重复格局 if is_dup(step+1, x1, y1) continue; end res = test(step+1,x1,y1); if res > 0 return; endendres = 0;end
