一、问题简介
华容道是在我国流传久远的一个益智游戏，然而其魅力至今不减，目前在许多商场内仍可见到基于这一游戏的玩具。该游戏起源于三国时期的一个著名故事：东汉末年，赤壁之战，曹操被周瑜杀得大败，带残兵从华容道仓皇逃走，不料大将关羽带兵在此等候。由于曹操与关羽曾经有过一段交往，关羽放曹操逃离华容道。华容道游戏的棋盘是由20个小正方形组成的长方形，宽4格，长5格。共有10个棋子，详见下图：
|
张
飞
|
曹 操
|
马
超
|
|
赵
云
|
关 羽
|
黄
忠
|
|
兵
|
兵
|
|
兵
|
|
|
兵
|
棋盘的下部有两个空置的小格作为华容道的出口。棋子就在这个长方形的棋盘内滑动，滑动过程中棋子不允许重叠。华容道是一个比较复杂的游戏，要移动很多步才能完成。据有关资料介绍，对于上面的布局（华容道游戏还有多种布局），已知的最好走法是81步。
笔者采用双向广度优先搜索的方法搜索出在一定意义下最佳的解题步骤，并指导我系学生姚刚用DELPHI V5.0开发了一个相应的电脑游戏。本文首先介绍了该算法的基本思想，然后通过完整的PASCAL源程序及其注释给出该算法的具体的实现，最后给出搜索的结果。至于相应的电脑游戏，读者可从将在2001年10月1日之前开通的“信息学（计算机）奥林匹克”网站上找到，该网站是天津师范大学网站（http://www.tjnu.edu.cn）的二级网站。
二、算法简介
我们用一个5*4的数组来记录棋盘状态，用标号1-5，8，9来表示各个棋子，例如，初始状态可表示为
4 9 9 5
4 9 9 5
2 8 8 3
2 1 1 3
1 0 0 1
（单向）广度优先搜索是大家熟知的算法，其基本步骤如下：
1． 将初始结点入队。队头指向该结点，队尾指向该结点之后。
2． 将队头结点出队，生成所有可能的扩展结点，队头指向下一个结点。如果某个新生成的结点已符合目标则结束，否则通过比较，将与已在队列中的结点不重复的新结点入队。队尾指向新结点之后。
3． 重复2，直到某个结点符合目标或队列空（即队尾位于队头之前）为止。
我们采用的双向广度优先搜索是指建立两个队列，分别从初始状态和目标状态出发进行搜索，直到遇到一个共同的结点（状态）为止。与单向搜索相比，其效率要高得多。但这一方法必须要事先知道目标状态。实际计算表明，与单向搜索相比，我们的双向搜索方法可节省一半的空间，而时间不到前者的一半。因而是一个很有效的算法。
从理论上讲，广度优先搜索得到的结果在某种确定的意义下应该是最优的。
三、PASCAL源程序及其注释
program road;{用 PASCAL7.0 BP（大内存模式）运行，不要用TURBO运行}
const range2=6000;{搜索队列的最大结点数}
b1=[2,3,4,5];
type
arr1=array [0..6,0..5] of byte;
arr2=array [1..5,1..4] of byte;
node_sd=record{标准结点，采用小数组arr2，用于主队列存储结点}
parent:integer; {存放父结点编号}
i1,j1,i2,j2:byte;{存放空格坐标}
arr:arr2; {存放结点状态}
end;
node_ext=record {扩展结点，采用加边的大数组arr1，用于工作结点，可减少对边缘的判断}
parent:integer;
i1,j1,i2,j2:byte;
arr:arr1;
end;
var
queue,queue2:array [0..range2] of ^node_sd;{搜索队列，分别从源点与目标点出发}
work,work2:arr1;
pp,qhead,qend,qhead2,qend2:integer;
node2:node_ext;
fname:string;
f1:text;
procedure ext_to_sd(node0:node_ext; var node3:node_sd); forward;
procedure prtnode(node3:node_ext); forward;
procedure sd_to_ext(node0:node_sd;var node3:node_ext); forward;
procedure initwork; {No.1 初始化}
var i,j:integer;
begin {1}
writeln('Input file name for result...');
readln(fname);
assign(f1,fname);
rewrite(f1);
qhead:=0; qend:=1; qhead2:=0; qend2:=1;
for i:=0 to 6 do
for j:=0 to 5 do
work[i,j]:=20;
for i:=1 to 2 do {源点状态}
begin
work[i,1]:=4; work[i,2]:=9; work[i,3]:=9; work[i,4]:=5;
end;
work[3,1]:=2; work[3,2]:=8; work[3,3]:=8; work[3,4]:=3;
work[4,1]:=2; work[4,2]:=1; work[4,3]:=1; work[4,4]:=3;
work[5,1]:=1; work[5,2]:=0; work[5,3]:=0; work[5,4]:=1;
node2.arr:=work; node2.parent:=0;
node2.i1:=5; node2.j1:=2;
node2.i2:=5; node2.j2:=3;
ext_to_sd(node2,queue[0]^);
writeln(f1,'Huarong dao result:');
writeln(f1,'num=0');
prtnode(node2);
for i:=0 to 6 do
for j:=0 to 5 do
work2[i,j]:=20;
for i:=1 to 2 do {目标点状态}
begin
work2[i,1]:=5; work2[i,2]:=4; work2[i,3]:=3; work2[i,4]:=2;
end;
work2[3,1]:=1; work2[3,2]:=1; work2[3,3]:=8; work2[3,4]:=8;
work2[4,1]:=0; work2[4,2]:=9; work2[4,3]:=9; work2[4,4]:=1;
work2[5,1]:=0; work2[5,2]:=9; work2[5,3]:=9; work2[5,4]:=1;
node2.arr:=work2; node2.parent:=0;
node2.i1:=4; node2.j1:=1;
node2.i2:=5; node2.j2:=1;
ext_to_sd(node2,queue2[0]^);
end;{1}
procedure prtnode(node3:node_ext); {No.2 打印结点值}
var i,j:integer;
begin {2}
with node3 do
begin {node3}
for i:=1 to 5 do
begin
for j:=1 to 4 do write(f1,arr[i,j]:3);
writeln(f1);
end;
end;{node3}
end; {2}
procedure ext_to_sd(node0:node_ext;var node3:node_sd); {No.3 结点类型转换，扩展结点转为标准结点}
var i,j:integer;
begin {3}
with node3 do
begin
for i:=1 to 5 do
for j:=1 to 4 do
arr[i,j]:=node0.arr[i,j];
parent:=node0.parent;
i1:=node0.i1; j1:=node0.j1;
i2:=node0.i2; j2:=node0.j2;
end;
end; {3}
procedure sd_to_ext(node0:node_sd;var node3:node_ext); {No.4结点类型转换，标准结点转为扩展结点}
var i,j:integer;
begin {4}
with node3 do
begin
for i:=1 to 5 do
for j:=1 to 4 do
work[i,j]:=node0.arr[i,j];
arr:=work;
parent:=node0.parent;
i1:=node0.i1; j1:=node0.j1;
i2:=node0.i2; j2:=node0.j2;
end;
end; {4}
procedure result(k:integer;node3:node_ext); {No.5 搜索成功后的处理}
var i,tmp,num:integer;
res:array [1..200]of integer;
snode:node_sd;
begin {5}
tmp:=node3.parent; num:=0;
while(tmp>0) do
begin
num:=num+1;
snode:=queue[tmp]^;
res[num]:=tmp;
tmp:=snode.parent;
end;
writeln(f1,'num=',num); writeln(f1,'queue_1');
for i:=num downto 1 do
begin
snode:=queue[res[i]]^;
sd_to_ext(snode,node2);
writeln(f1,'num=',num-i+1);
prtnode(node2);
end;
writeln(f1,'queue_2');
tmp:=k;
while (tmp>0) do
begin
num:=num+1;
snode:=queue2[tmp]^;
sd_to_ext(snode,node2);
writeln(f1,'num=',num);
prtnode(node2);
tmp:=snode.parent;
end;
writeln('OK!!!');
close(f1);
for i:=0 to range2 do
freemem(queue[i],sizeof(queue[i]^));
for i:=0 to range2 do
freemem(queue2[i],sizeof(queue2[i]^));
halt(0);
end;{5}
function judge2(arr:arr1):boolean; {No.6 排除若干不可能情形，以减少入队的结点数}
var i3:integer;
begin {6}
judge2:=true;
if(arr[2,1]=9)and(arr[3,2]=9)and(arr[1,3] in b1)and(arr[1,1]=0)
and(arr[1,2]=0) then
judge2:=false;
if(arr[2,2]=9)and(arr[3,3]=9)and(arr[1,1] in b1)and(arr[1,4] in b1)
and(arr[1,2]=0)and(arr[1,3]=0) then
judge2:=false;
if(arr[1,1]=9)and(arr[2,2]=9)and((arr[1,3]=0)or(arr[1,4]=0))
and(arr[2,3]=8) then
judge2:=false;
for i3:=1 to 2 do {利用对称性，可限定在前两行，曹操只能向左或向中间移动}
if (arr[i3,4]=9) then
judge2:=false;
if(arr[1,2]=9)and(arr[2,3]=9)and(arr[1,1]=0)and(arr[1,4]=0)
then
judge2:=false;
end; {6}
function judge3(arr01:arr1;arr02:arr2):boolean; {No.7 判断是否等于已入队结点}
var i3,j3:integer;
begin {7}
judge3:=true;
for i3:=1 to 5 do
for j3:=1 to 4 do
begin
if (arr01[i3,j3] in b1) then arr01[i3,j3]:=2;
if (arr02[i3,j3] in b1) then arr02[i3,j3]:=2;
if (arr01[i3,j3]<>arr02[i3,j3]) then
begin judge3:=false; exit; end;
end;
end;{7}
procedure toqueue(node3:node_ext; i,j,kz3:integer); {No.8 判断新扩展的结点可否进入队列}
var k,t,i3,j3:integer;
begin {8}
with node3 do
begin {node3}
if kz3=1 then
begin {kz3_1}
for k:=qend-1 downto 0 do
if judge3(node3.arr,queue[k]^.arr) then exit;
for k:=qend2-1 downto 0 do
if judge3(node3.arr,queue2[k]^.arr) then
begin
writeln('No.1 k=',k);
result(k,node3);
end;
if(node3.j1>node3.j2) then
begin
t:=i1; i1:=i2; i2:=t;
t:=j1; j1:=j2; j2:=t;
end;
if(node3.j1=node3.j2)and(i1=i2+1) then
begin t:=i1; i1:=i2; i2:=t; end;
if not judge2(arr) then exit;
ext_to_sd(node3,queue[qend]^);
qend:=qend+1;
end; {kz3_1}
if kz3=2 then
begin {kz3_2}
for k:=qend2-1 downto 0 do
if judge3(node3.arr,queue2[k]^.arr) then exit;
if(node3.j1>node3.j2) then
begin
t:=i1; i1:=i2; i2:=t;
t:=j1; j1:=j2; j2:=t;
end;
if(node3.j1=node3.j2)and(i1=i2+1) then
begin t:=i1; i1:=i2; i2:=t; end;
if not judge2(arr) then exit;
ext_to_sd(node3,queue2[qend2]^);
qend2:=qend2+1;
end; {kz3_2}
end;{node3}
end;{8}
procedure toij_1(xz:byte;node4:node_ext;kz,i,j,kz3:integer);{No.9,xin01等过程共用的中间过程}
begin{9}
with node4 do
begin
arr[i,j]:=0;
if xz=1 then
if kz=1 then i1:=i else i2:=i;
if xz=2 then
if kz=1 then j1:=j else j2:=j;
end;
toqueue(node4,i,j,kz3);
end;{9}
procedure toij_2(xz:byte;node4:node_ext;i,j,kz3:integer); {No.10,xin01等过程共用的中间过程}
begin{10}
with node4 do
begin
arr[i,j]:=0;
if xz=1 then
begin
arr[i,j+1]:=0; i1:=i; i2:=i;
end
else
begin
arr[i+1,j]:=0; j1:=j; j2:=j;
end;
end;
toqueue(node4,i,j,kz3);
end;{10}
procedure xin01( node4:node_ext;ii,jj,kz,kz3:integer); {No.11 处理单个空结点}
var i,j:integer;
nodetmp:node_ext;
begin {11}
nodetmp:=node4;
with node4 do
begin {node4}
i:=ii;j:=jj;
if arr[i-1,j]=1 then
begin
arr[i,j]:=1; i:=i-1;
toij_1(1,node4,kz,i,j,kz3);
end;
i:=ii;j:=jj; {to upper}
if arr[i-1,j] in b1 then
begin
arr[i,j]:=arr[i-2,j];
i:=i-2;
toij_1(1,node4,kz,i,j,kz3);
end;
node4:=nodetmp;
i:=ii;j:=jj; {to lower}
if arr[i+1,j]=1 then
begin
arr[i,j]:=1; i:=i+1;
toij_1(1,node4,kz,i,j,kz3);
end;
i:=ii;j:=jj;
if arr[i+1,j] in b1 then
begin
arr[i,j]:=arr[i+2,j];
i:=i+2;
toij_1(1,node4,kz,i,j,kz3);
end;
node4:=nodetmp;
i:=ii;j:=jj; {to left}
if arr[i,j-1]=1 then
begin
arr[i,j]:=1; j:=j-1;
toij_1(2,node4,kz,i,j,kz3);
end;
i:=ii;j:=jj;
if arr[i,j-1]=8 then
begin
arr[i,j]:=8; arr[i,j-1]:=8; j:=j-2;
toij_1(2,node4,kz,i,j,kz3);
end;
node4:=nodetmp;
i:=ii;j:=jj; {to right}
if arr[i,j+1]=1 then
begin
arr[i,j]:=1; j:=j+1;
toij_1(2,node4,kz,i,j,kz3);
end;
i:=ii;j:=jj;
if arr[i,j+1]=8 then
begin
arr[i,j]:=8; arr[i,j+1]:=8; j:=j+2;
toij_1(2,node4,kz,i,j,kz3);
end;
end;{node4}
end; {11}
procedure xin002( node4:node_ext;ii,jj,kz3:integer); {No.12 处理连续两个同行空结点}
var i,j:integer;
nodetmp:node_ext;
begin {12}
nodetmp:=node4;
with node4 do
begin {node4}
i:=ii;j:=jj; {to upper}
if (arr[i-1,j]=9)and(arr[i-1,j+1]=9) then
begin
arr[i,j]:=9; arr[i,j+1]:=9;
arr[i-1,j]:=9; arr[i-1,j+1]:=9;
i:=i-2;
toij_2(1,node4,i,j,kz3);
end;
node4:=nodetmp;
i:=ii;j:=jj;
if (arr[i-1,j]=8)and(arr[i-1,j+1]=8) then
begin
arr[i,j]:=8; arr[i,j+1]:=8; i:=i-1;
toij_2(1,node4,i,j,kz3);
end;
node4:=nodetmp;
i:=ii; j:=jj; {to lower}
if (arr[i+1,j]=8)and(arr[i+1,j+1]=8) then
begin
arr[i,j]:=8; arr[i,j+1]:=8; i:=i+1;
toij_2(1,node4,i,j,kz3);
end;
node4:=nodetmp;
i:=ii;j:=jj;
if (arr[i+1,j]=9)and(arr[i+1,j+1]=9) then
begin
arr[i,j]:=9; arr[i,j+1]:=9;
arr[i+1,j]:=9; arr[i+1,j+1]:=9;
i:=i+2;
toij_2(1,node4,i,j,kz3);
end;
end;{node4}
end;{12}
procedure xin003( node4:node_ext;ii,jj,kz3:integer); {No.13 处理连续两个同列空结点}
var i,j,tmp:integer;
nodetmp:node_ext;
begin {13}
nodetmp:=node4;
with node4 do
begin {node4}
i:=ii; j:=jj; {to left}
if (arr[i,j-1] in b1) then
begin
tmp:=arr[i,j-1];
if arr[i+1,j-1]=tmp then
begin
arr[i,j]:=tmp; arr[i+1,j]:=tmp; j:=j-1;
toij_2(2,node4,i,j,kz3);
end;
end;
node4:=nodetmp;
i:=ii; j:=jj;
if (arr[i,j-1]=9)and(arr[i+1,j-1]=9) then
begin
arr[i,j]:=9; arr[i+1,j]:=9;
arr[i,j-1]:=9; arr[i+1,j-1]:=9; j:=j-2;
toij_2(2,node4,i,j,kz3);
end;
node4:=nodetmp;
i:=ii; j:=jj; {to right}
if (arr[i,j+1] in b1) then
begin
tmp:=arr[i,j+1];
if arr[i+1,j+1]=tmp then
begin
arr[i,j]:=tmp; arr[i+1,j]:=tmp; j:=j+1;
toij_2(2,node4,i,j,kz3);
end;
end;
node4:=nodetmp;
i:=ii; j:=jj;
if (arr[i,j+1]=9)and(arr[i+1,j+1]=9) then
begin
arr[i,j]:=9; arr[i+1,j]:=9;
arr[i,j+1]:=9; arr[i+1,j+1]:=9; j:=j+2;
toij_2(2,node4,i,j,kz3);
end;
end;{node4}
end;{13}
procedure search; {No.14 建立队列主过程}
var tmp,i3,j3:integer;
snode:node_sd;
snode7:node_ext;
begin {14}
while (qend>qhead)and(qend<range2)and(qend2>qhead2)and(qend2<range2) do
begin {while}
tmp:=qhead;
if (tmp mod 500)=0 then
writeln('tmp:',qhead:2);
snode:=queue[tmp]^;
snode.parent:=qhead;
sd_to_ext(snode,snode7);
xin01(snode7, snode7.i1, snode7.j1, 1, 1);
xin01(snode7, snode7.i2, snode7.j2, 2, 1);
with snode7 do
begin{node7}
if (i1=i2)and(j1+1=j2) then xin002(snode7,i1,j1,1);
if (i1+1=i2) and (j1=j2) then xin003(snode7,i1,j1,1);
end; {node7}
qhead:=qhead+1;
tmp:=qhead2;
snode:=queue2[tmp]^;
snode.parent:=qhead2;
sd_to_ext(snode,snode7);
xin01(snode7,snode7.i1,snode7.j1,1,2);
xin01(snode7,snode7.i2,snode7.j2,2,2);
with snode7 do
begin{node7}
if (i1=i2)and(j1+1=j2) then xin002(snode7,i1,j1,2);
if (i1+1=i2) and (j1=j2) then xin003(snode7,i1,j1,2);
end; {node7}
qhead2:=qhead2+1;
end; {while}
end; {14}
begin {main 主程序}
for pp:=0 to range2 do
getmem(queue[pp],sizeof(queue[pp]^));
for pp:=0 to range2 do
getmem(queue2[pp],sizeof(queue2[pp]^));
initwork;
writeln('*** Huarong dao ***');
search;
close(f1);
for pp:=0 to range2 do
freemem(queue[pp],sizeof(queue[pp]^));
for pp:=0 to range2 do
freemem(queue2[pp],sizeof(queue2[pp]^));
end.
四、运行结果及说明
1．直接运行上述程序所得结果为122步（在PIII 933MH微机上运行大约30秒）。在前面提到得81步的走法中，“一步”是指一个棋子走一次，可能走过2个空格，按这一规则可将122步合并为93步，即下面给出的结果。从理论上讲，广度优先搜索应得到最优的结果，而这里93步却多于81步，原因在于我们是在限定每步只走一个空格的前提下的最优，而不是每步既可走一个空格也可走两个空格的意义下的最优，显然。后者的程序实现会更复杂一些。事实上，利用下面的结果，做少量的调整，便可得到81步的走法，具体处理留给读者。
2．下面的44，45步从表面上看似乎不衔接。事实上，在我们的程序中4个2*1的竖立的棋子的地位是等同的，标号为2，3，4，5的棋子与4个标号为1的棋子一样，可以看作是相同的棋子，在这个意义上，44，45两步（或其它类似的相邻的两步）是完全衔接的。显然，最终的4个竖立的棋子的排列顺序也不一定与第93步所给的一致。
num=0 num=1 num=2 num=3
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
2 8 8 3 2 8 8 3 2 8 8 3 2 8 8 0
2 1 1 3 2 0 1 3 2 0 1 3 2 0 1 3
1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 3
num=4 num=5 num=6 num=7
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
2 0 8 8 0 2 8 8 0 2 8 8 0 2 8 8
2 0 1 3 0 2 1 3 1 2 1 3 1 2 1 3
1 1 1 3 1 1 1 3 0 1 1 3 1 0 1 3
num=8 num=9 num=10 num=11
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
0 0 8 8 8 8 0 0 8 8 0 1 8 8 1 1
1 2 1 3 1 2 1 3 1 2 0 3 1 2 0 3
1 2 1 3 1 2 1 3 1 2 1 3 1 2 0 3
num=12 num=13 num=14 num=15
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
8 8 1 1 8 8 1 1 0 0 1 1 1 0 0 1
1 0 2 3 0 0 2 3 8 8 2 3 8 8 2 3
1 0 2 3 1 1 2 3 1 1 2 3 1 1 2 3
num=16 num=17 num=18 num=19
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
4 9 9 5 4 9 9 5 4 9 9 5 4 9 9 5
1 1 0<