【题意】
经典的八数码问题。
描述了一个3*3的格子,每个格子里有一个数,还有一个空位,
每次操作可以将空位跟周围的格子里的数交换,问最少多少次操作可以使方格变为
1 2 3
4 5 6
7 8 x
有解打出最少的操作序列
无解打unsolvable
【输入】
一行,表示格子里的数
【输出】
有解打出最少的操作序列
无解打unsolvable
启发式搜索,IDA*算法
估价函数为每个点到自己位置的哈密顿距离之和
program poj1077; const zl:array [1..4,1..2] of longint=((0,1),(1,0),(-1,0),(0,-1)); change:array [1..4] of char=('d','r','u','l'); type status=array [0..4,0..4] of longint; var i,j,k,deep,x,y:longint; square:status; temp:char; yes:boolean; solution:array [0..101] of longint; procedure swap (var a,b:longint); var i:longint; begin i:=a; a:=b; b:=i; end; function h (now:status):longint; var i,j,k:longint; begin k:=0; for i:=1 to 3 do for j:=1 to 3 do if now[i,j]<>9 then k:=k+abs((now[i,j]-1) div 3 +1-i)+abs((now[i,j]-1) mod 3 +1-j); h:=k; end; procedure dfs (x,y,g,lasth,last:longint); var i,j,k,nx,ny:longint; begin k:=h(square); if k+g>deep then exit; if k=0 then begin yes:=true; exit; end; for i:=1 to 4 do if i+last<>5 then begin nx:=x+zl[i,1]; ny:=y+zl[i,2]; if (nx>3)or(nx<1)or(ny>3)or(ny<1) then continue; swap(square[x,y],square[nx,ny]); solution[g+1]:=i; dfs(nx,ny,g+1,k,i); swap(square[x,y],square[nx,ny]); if yes then exit; end; end; function idastar(deep:longint):boolean; begin yes:=false; dfs(x,y,0,deep,0); idastar:=yes; end; begin for i:=1 to 3 do for j:=1 to 3 do begin read(temp); if temp='x' then begin square[i,j]:=9; x:=i; y:=j; end else square[i,j]:=ord(temp)-48; read(temp); end; deep:=h(square); while not idastar(deep) do inc(deep); if deep>100 then begin writeln('unsolvable'); exit; end; for i:=1 to deep do write(change[solution[i]]); writeln; end.