eightnumber.java

这个是八数码的原程序

import java.applet.Applet;
import java.awt.*;
import java.awt.Graphics;
import java.util.Vector;
public class EightNumber extends Applet implements Runnable 
{
 /*内部类，表示一个节点，如
  * 0  1  2
  * 3  4  5
  * 6  7  8
  */
 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;
  }
 //返回从当前节点跳到下一节点时，与“0”交换移动的位置，这个位置的数字用红色画出
  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()//返回从一个节点出发，可以扩展的点节数(以“0”为中心）
  {
   if(states[4] == 0)//如果"0"位于中心，可以扩展出4个节点
    size = 4;
   else if(states[0]==0 || states[2]==0 || states[6]==0 || states[8]==0)
    size = 2;//如果“0”位于角上，可以扩展出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)//记录“0”的位置
     {
      m = i;
      n = j;
     }
    }
   }
   //以下根据"0"的位置，求出所有扩展的节点
   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.jpg";
   stateImg[i] = getImage(getCodeBase(),fileName);
   waitForImage(stateImg[i]);
   fileName = "img/";
   fileName = fileName + tmp.toString() + "_2.jpg";
   moveImg[i] = getImage(getCodeBase(),fileName);
   waitForImage(stepsImg);
  }
  vecOpen.add(st);//将首节点加入到开集中
  fileName = "img/steps.jpg";
  stepsImg = getImage(getCodeBase(),"img/steps.jpg");
  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);
  }
 }
 //启发函数,计算节点st与目标节点的距离（曼哈顿距离）。
 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(2000);
   }
   catch(InterruptedException e){}
   
  }
  return result;
 }
 
 private boolean haveContained(State st)//判断闭集中是否包含节点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;
 }
}