启发函数suggestFunc计算所有棋子到目标位置的距离，又称为曼哈顿距离。
import java.applet.Applet;
import java.awt.*;
import java.awt.Graphics;
import java.util.Vector;
public class EightNumber extends Applet implements Runnable
{
private class State
{
int[] states = new int[9];
int size;
int steps;
public State(int [] s)
{
int i;
for(i=0;i<9;i++)
states[i] = s[i];
}
public boolean equals(State st)
{
int[] s=st.getStates();
int i;
for(i=0;i<9;i++)
if(s[i] != states[i])
return false;
return true;
}
public int judgeMove(State st)
{
int[] s=st.getStates();
int i;
for(i=0;i<9;i++)
{
if(s[i] != states[i] && s[i]!=0)
return i;
}
return -1;
}
public int[] getStates()
{
return states;
}
public int expandSize()
{
if(states[4] == 0)
size = 4;
else if(states[0]==0 || states[2]==0 || states[6]==0 || states[8]==0)
size = 2;
else
size = 3;
return size;
}
public State[] expandState()
{
State[] st;
int [] ex=new int[9];
int i,j,k;
int m=0,n=0;
int a=0,b=0;
st = new State[size];
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
k = i*3+j;
ex[k] = states[k];
if(states[k] == 0)
{
m = i;
n = j;
}
}
}
i = 0;
a = m*3+n;
if(m-1>=0)
{
b = (m-1)*3+n;
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
if(m+1<=2)
{
b = (m+1)*3+n;
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
if(n-1>=0)
{
b = m*3+(n-1);
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
if(n+1<=2)
{
b = m*3+(n+1);
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i++;
}
return st;
}
}
Image[] stateImg = new Image[10];
Image[] moveImg = new Image[10];
Image stepsImg;
Vector vecClose = new Vector();//记录下已经扩展的节点
Vector vecOpen = new Vector();//记录下未扩展的节点
int[] first = {7,2,4,5,0,6,8,3,1};
int[] aim = {0,1,2,3,4,5,6,7,8};
State nowState = null;
State aimState = new State(aim);
int stepX;
int stepY;
int startX;
int startY;
int steps;
int move;
boolean start;
Thread moveTh = null;
public void init()
{
int i;
Integer tmp;
String fileName;
State st = new State(first);
st.steps = 0;
resize(200,300);
startX = 16;
startY = 19;
stepX = 55;
stepY = 55;
steps = 0;
start = false;
move = -1;
for(i=0;i<10;i++)
{
tmp = new Integer(i);
fileName = "img/";
fileName = fileName + tmp.toString()+"_1.gif";
stateImg[i] = getImage(getCodeBase(),fileName);
waitForImage(stateImg[i]);
fileName = "img/";
fileName = fileName + tmp.toString() + "_2.gif";
moveImg[i] = getImage(getCodeBase(),fileName);
waitForImage(stepsImg);
}
vecOpen.add(st);
fileName = "img/steps.gif";
stepsImg = getImage(getCodeBase(),"img/steps.gif");
waitForImage(stepsImg);
}
public void waitForImage(Image i)
{
MediaTracker tracker = new MediaTracker(this);
try
{
tracker.addImage(i,0);
tracker.waitForID(0);
}
catch(InterruptedException e) {System.err.println("Wait interrupted.");}
}
public void paint(Graphics g)
{
int i,j,k;
int[] state;
Integer tmp;
if(start == false)
return ;
state = nowState.getStates();
g.drawImage(stepsImg,startX+20,startY,this);
tmp = new Integer(steps);
g.drawString(tmp.toString(),startX+80,startY+20);
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
k = i*3+j;
if(move == k)
{
putNumber(g,state[k],i,j,false);
}
else
{
putNumber(g,state[k],i,j,true);
}
}
}
}
public void update(Graphics g)
{
paint(g);
}
private void putNumber(Graphics g,int number,int i,int j,boolean isState )
{
int x,y;
x = startX + j*stepX;
y = startY + i*stepY + stepY;
if(isState)
{
g.drawImage(stateImg[number],x,y,this);
}
else
{
g.drawImage(moveImg[number],x,y,this);
}
}
//启发函数
private int suggestFunc(State st)
{
int i,j,m,n;
int a=0,b=0;
int result=0;
int[] state;
state = st.getStates();
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
a = i*3+j;
if(state[a]==0)
continue;
for(m=0;m<3;m++)
{
for(n=0;n<3;n++)
{
b = m*3+n;
if(state[a] == aim[b])
{
result += (Math.abs(m-i)+Math.abs(n-j));
break;
}
}
if(state[a] == aim[b])
break;
}
}
}
return result;
}
public void start()
{
if(moveTh == null)
{
moveTh = new Thread(this);
moveTh.start();
}
}
public void stop()
{
if(moveTh != null)
{
moveTh = null;
}
}
public void run()
{
searchPath();
}
//寻找路径
private boolean searchPath()
{
int openSize;
State st;
boolean result=false;
start = true;
while(!vecOpen.isEmpty())
{
openSize = vecOpen.size();;
st = (State)vecOpen.elementAt(openSize-1);
if(nowState != null)
{
move = nowState.judgeMove(st);
}
nowState = st;
vecOpen.remove(openSize-1);
vecClose.add(nowState);
if(expandNowState() == 0)
{
result = true;
}
steps++;
repaint();
if(result == true)
break;
try
{
Thread.sleep(1000);
}
catch(InterruptedException e){}
}
return result;
}
private boolean haveContained(State st)
{
int size;
int i;
State tmp;
size = vecClose.size();
for(i=0;i<size;i++)
{
tmp = (State)vecClose.elementAt(i);
if(tmp.equals(st))
return true;
}
return false;
}
//扩展当前节点,1表示扩展成功,0表示找到目标节点，-1表示当前节点不可扩展
private int expandNowState()
{
int[] value = {255,255,255,255};
int size;
int i,j;
int have = -1;
State st[];
State tmpState;
int tmp;
size = nowState.expandSize();
st = nowState.expandState();
for(i=0;i<size;i++)
{
if(!haveContained(st[i]))
{
value[i] = suggestFunc(st[i]);
if(value[i] == 0)
{
move = nowState.judgeMove(st[i]);
nowState = st[i];
return 0;
}
else
have = 1;
}
}
if(have == 1)
{
for(i=0;i<size;i++)
{
for(j=i+1;j<size;j++)
{
if(value[j]>value[i])
{
tmp = value[j];
tmpState = st[j];
value[j] = value[i];
st[j] = st[i];
value[i] = tmp;
st[i] = tmpState;
}
}
}
for(i=0;i<size;i++)
{
if(value[i]!=255)
{
vecOpen.add(st[i]);
}
}
}
return have;
}
}
