function My_Frog
clc;clear all;
frog_num=input('输入所有青蛙的个数(非零偶数):');
NN=frog_num+1;
init_STATE=[-1*ones(1,frog_num/2) 0 ones(1,frog_num/2)];
corr_STATE=[ones(1,frog_num/2) 0 -1*ones(1,frog_num/2)];
STATE=cell(256,1);count=0;
solve_backtrack(1);
function solve_backtrack(step)
STATE{1}=init_STATE;
if isequal(STATE{step},corr_STATE)
count=count+1;
fprintf('完成!\n编号表示从左到右石头对应的序号!\n方法%d解答步骤:\n',count);
disp_result(STATE);
else
for i=1:NN
if can_move(STATE{step},i)
STATE{step+1}=STATE{step};
STATE{step+1}(STATE{step+1}==0)=STATE{step}(i);
STATE{step+1}(i)=0;
solve_backtrack(step+1);
end
end
end
end
end
function R=can_move(now_state,j)
switch now_state(j)
case -1
if j==size(now_state,2)
R=0;return
elseif find(now_state==0)==j+1||find(now_state==0)==j+2
R=1;
else R=0; return
end
case 1
if j==1
R=0;return
elseif find(now_state==0)==j-1||find(now_state==0)==j-2
R=1;
else R=0; return
end
case 0
R=0;return
otherwise
R=0;return
end
end
function disp_result(r_STATE)
RESULT=cell2mat(r_STATE);
for k=2:size(RESULT,1)
fprintf('\t第%d步:%d-->%d \n',k-1,find(RESULT(k,:)==0),find(RESULT(k-1,:)==0));
end
end