Go语言视频零基础入门到精通

javalearner

八数码方块移动游戏要求从一个含8个数字（用1-8表示）的方块以及一个空格方块（用0表示）的3x3矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方 块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移 动。例如，假设一个3x3矩阵的初始状态为：
    8 0 3
    2 1 4
    7 6 5
目标状态为：
    1 2 3
    8 0 4
    7 6 5
则一个合法的移动路径为：

1. 8 0 3     8 1 3     8 1 3     0 1 3     1 0 3    1 2 3
2. 2 1 4  >  2 0 4  >  0 2 4  >  8 2 4   > 8 2 4  > 8 0 4
3. 7 6 5     7 6 5     7 6 5     7 6 5     7 6 5    7 6 5

复制代码

  
   
   
     
   

     
   
  
      另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为5。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。 根据启发函数求解八数码问题

1. 
   
2. import java.applet.Applet;
   
3. import java.awt.*;
   
4. import java.awt.Graphics;
   
5. import java.util.Vector;
   
6. public class EightNumber extends Applet implements Runnable
   
7. {
   
8. /*内部类，表示一个节点，如
   
9.   * 0  1  2
   
10.   * 3  4  5
    
11.   * 6  7  8
    
12.   */
    
13. private class State
    
14. {
    
15.   int[] states = new int[9];
    
16.   int size;
    
17.   int steps;
    
18.   public State(int [] s)
    
19.   {
    
20.    int i;
    
21.    for(i=0;i<9;i++)
    
22.     states[i] = s[i];
    
23.   }
    
24.   public boolean equals(State st)
    
25.   {
    
26.    int[] s=st.getStates();
    
27.    int i;
    
28.    for(i=0;i<9;i++)
    
29.     if(s[i] != states[i])
    
30.      return false;
    
31.    return true;
    
32.   }
    
33. //返回从当前节点跳到下一节点时，与“0”交换移动的位置，这个位置的数字用红色画出
    
34.   public int judgeMove(State st)
    
35.   {
    
36.    int[] s=st.getStates();
    
37.    int i;
    
38.    for(i=0;i<9;i++)
    
39.    {
    
40.     if(s[i] != states[i] && s[i]!=0)
    
41.      return i;
    
42.    }
    
43.    return -1;
    
44.   }
    
45.   public int[] getStates()
    
46.   {
    
47.    return states;
    
48.   }
    
49.   public int expandSize()//返回从一个节点出发，可以扩展的点节数(以“0”为中心）
    
50.   {
    
51.    if(states[4] == 0)//如果"0"位于中心，可以扩展出4个节点
    
52.     size = 4;
    
53.    else if(states[0]==0 || states[2]==0 || states[6]==0 || states[8]==0)
    
54.     size = 2;//如果“0”位于角上，可以扩展出2个节点
    
55.    else
    
56.     size = 3;//边上
    
57.    return size;
    
58.   }
    
59.   public State[] expandState()//返回当前节点扩展出的所有节点
    
60.   {
    
61.    State[] st;
    
62.    int [] ex=new int[9];
    
63.    int i,j,k;
    
64.    int m=0,n=0;
    
65.    int a=0,b=0;
    
66.    st = new State[size];
    
67.    for(i=0;i<3;i++)
    
68.    {
    
69.     for(j=0;j<3;j++)
    
70.     {
    
71.      k = i*3+j;
    
72.      ex[k] = states[k];
    
73.      if(states[k] == 0)//记录“0”的位置
    
74.      {
    
75.       m = i;
    
76.       n = j;
    
77.      }
    
78.     }
    
79.    }
    
80.    //以下根据"0"的位置，求出所有扩展的节点
    
81.    i = 0;
    
82.    a = m*3+n;
    
83.    if(m-1>=0)
    
84.    {
    
85.     b = (m-1)*3+n;
    
86.     ex[a] = ex[b];
    
87.     ex[b] = 0;
    
88.     st[i] = new State(ex);
    
89.     ex[b] = ex[a];
    
90.     ex[a] = 0;
    
91.     i++;
    
92.    }
    
93.    if(m+1<=2)
    
94.    {
    
95.     b = (m+1)*3+n;
    
96.     ex[a] = ex[b];
    
97.     ex[b] = 0;
    
98.     st[i] = new State(ex);
    
99.     ex[b] = ex[a];
    
100.     ex[a] = 0;
     
101.     i++;
     
102.    }
     
103.    if(n-1>=0)
     
104.    {
     
105.     b = m*3+(n-1);
     
106.     ex[a] = ex[b];
     
107.     ex[b] = 0;
     
108.     st[i] = new State(ex);
     
109.     ex[b] = ex[a];
     
110.     ex[a] = 0;
     
111.     i++;
     
112.    }
     
113.    if(n+1<=2)
     
114.    {
     
115.     b = m*3+(n+1);
     
116.     ex[a] = ex[b];
     
117.     ex[b] = 0;
     
118.     st[i] = new State(ex);
     
119.     ex[b] = ex[a];
     
120.     ex[a] = 0;
     
121.     i++;
     
122.    }
     
123.    return st;
     
124.   }
     
125. }
     
126. Image[] stateImg = new Image[10];
     
127. Image[] moveImg = new Image[10];
     
128. Image stepsImg;
     
129. Vector vecClose = new Vector();//闭集，记录下已经扩展的节点
     
130. Vector vecOpen = new Vector();//开集，记录下未扩展的节点
     
131. int[] first = {7,2,4,5,0,6,8,3,1};
     
132. int[] aim = {0,1,2,3,4,5,6,7,8};
     
133. State nowState = null;//当前节点
     
134. State aimState = new State(aim);//目标节点
     
135. int stepX;
     
136. int stepY;
     
137. int startX;
     
138. int startY;
     
139. int steps;
     
140. int move;
     
141. boolean start;
     
142. Thread moveTh = null;
     
143. public void init()
     
144. {
     
145.   int i;
     
146.   Integer tmp;
     
147.   String fileName;
     
148.   State st = new State(first);
     
149.   st.steps = 0;
     
150.   
     
151.   resize(200,300);
     
152.   startX = 16;
     
153.   startY = 19;
     
154.   stepX = 55;
     
155.   stepY = 55;
     
156.   steps = 0;
     
157.   start = false;
     
158.   move = -1;
     
159.   for(i=0;i<10;i++)
     
160.   {
     
161.    tmp = new Integer(i);
     
162.    fileName = "img/";
     
163.    fileName = fileName + tmp.toString()+"_1.jpg";
     
164.    stateImg[i] = getImage(getCodeBase(),fileName);
     
165.    waitForImage(stateImg[i]);
     
166.    fileName = "img/";
     
167.    fileName = fileName + tmp.toString() + "_2.jpg";
     
168.    moveImg[i] = getImage(getCodeBase(),fileName);
     
169.    waitForImage(stepsImg);
     
170.   }
     
171.   vecOpen.add(st);//将首节点加入到开集中
     
172.   fileName = "img/steps.jpg";
     
173.   stepsImg = getImage(getCodeBase(),"img/steps.jpg");
     
174.   waitForImage(stepsImg);
     
175.    
     
176. }
     
177. 
     
178. public void waitForImage(Image i)//载入图像
     
179.    {
     
180.     MediaTracker tracker = new MediaTracker(this);
     
181.         try
     
182.         {
     
183.          tracker.addImage(i,0);
     
184.             tracker.waitForID(0);
     
185.         }
     
186.         catch(InterruptedException e) {System.err.println("Wait interrupted.");}
     
187.    }
     
188. 
     
189. public void paint(Graphics g) //画当前节点
     
190. {
     
191.   int i,j,k;
     
192.   int[] state;
     
193.   Integer tmp;
     
194.   if(start == false)
     
195.    return ;
     
196.   state = nowState.getStates();
     
197.   g.drawImage(stepsImg,startX+20,startY,this);
     
198.   tmp = new Integer(steps);
     
199.   g.drawString("第"+tmp.toString()+"步",startX+80,startY+20);
     
200.   
     
201.   for(i=0;i<3;i++)
     
202.   {
     
203.    for(j=0;j<3;j++)
     
204.    {
     
205.     k = i*3+j;
     
206.    
     
207.     if(move == k)
     
208.     {
     
209.      putNumber(g,state[k],i,j,false);//刚移动的位置，用红色画出
     
210.     }
     
211.     else
     
212.     {
     
213.      putNumber(g,state[k],i,j,true);
     
214.     }
     
215.    }
     
216.   }
     
217. }
     
218. public void update(Graphics g)
     
219. {
     
220.   paint(g);
     
221. }
     
222. private void putNumber(Graphics g,int number,int i,int j,boolean isState )
     
223. {
     
224.   int x,y;
     
225.   x = startX + j*stepX;
     
226.   y = startY + i*stepY + stepY;
     
227.   if(isState)
     
228.   {
     
229.    g.drawImage(stateImg[number],x,y,this);
     
230.   }
     
231.   else
     
232.   {
     
233.    g.drawImage(moveImg[number],x,y,this);
     
234.   }
     
235. }
     
236. //启发函数,计算节点st与目标节点的距离（曼哈顿距离）。
     
237. private int suggestFunc(State st)
     
238. {
     
239.   int i,j,m,n;
     
240.   int a=0,b=0;
     
241.   int result=0;
     
242.   int[] state;
     
243.   state = st.getStates();
     
244.   for(i=0;i< 3;i++)
     
245.   {
     
246.    for(j=0;j< 3;j++)
     
247.    {
     
248.     a = i*3+j;
     
249.     if(state[a]==0)
     
250.      continue;
     
251.     for(m=0;m< 3;m++)
     
252.     {
     
253.      for(n=0;n< 3;n++)
     
254.      {
     
255.       b = m*3+n;
     
256.       if(state[a] == aim[b])
     
257.       {
     
258.        result += (Math.abs(m-i)+Math.abs(n-j));
     
259.        break;
     
260.       }
     
261.      }
     
262.      if(state[a] == aim[b])
     
263.       break;
     
264.     }
     
265.    }
     
266.   }
     
267.   return result;
     
268. }
     
269. 
     
270. public void start()
     
271. {
     
272.   if(moveTh == null)
     
273.   {
     
274.    moveTh = new Thread(this);
     
275.    moveTh.start();//启动线程
     
276.   }
     
277. }
     
278. public void stop()
     
279. {
     
280.   if(moveTh != null)
     
281.   {
     
282.    moveTh = null;
     
283.   }
     
284. }
     
285. public void run()
     
286. {
     
287. 
     
288.   searchPath();
     
289. }
     
290. 
     
291. //寻找路径
     
292. private boolean searchPath()
     
293. {
     
294.   int openSize;
     
295.   State st;
     
296.   boolean result=false;
     
297.   start = true;
     
298.   while(!vecOpen.isEmpty())
     
299.   {
     
300.    openSize = vecOpen.size();;
     
301.    st = (State)vecOpen.elementAt(openSize-1);
     
302.    if(nowState != null)
     
303.    {
     
304.     move = nowState.judgeMove(st);
     
305.    }
     
306.    
     
307.    nowState = st;
     
308.    vecOpen.remove(openSize-1);
     
309.    vecClose.add(nowState);
     
310.    if(expandNowState() == 0)
     
311.    {
     
312.     result = true;
     
313.    }
     
314.    steps++;
     
315.    repaint();
     
316.    if(result == true)
     
317.     break;
     
318.    try
     
319.    {
     
320.     Thread.sleep(2000);
     
321.    }
     
322.    catch(InterruptedException e){}
     
323.    
     
324.   }
     
325.   return result;
     
326. }
     
327. 
     
328. private boolean haveContained(State st)//判断闭集中是否包含节点st
     
329. {
     
330.   int size;
     
331.   int i;
     
332.   State tmp;
     
333.   size = vecClose.size();
     
334.   for(i=0;i< size;i++)
     
335.   {
     
336.    tmp = (State)vecClose.elementAt(i);
     
337.    if(tmp.equals(st))
     
338.     return true;
     
339.   }
     
340.   return false;
     
341. }
     
342. //扩展当前节点,1表示扩展成功,0表示找到目标节点，-1表示当前节点不可扩展
     
343. private int expandNowState()
     
344. {
     
345.   int[] value = {255,255,255,255};
     
346.   int size;
     
347.   int i,j;
     
348.   int have = -1;
     
349.   State st[];
     
350.   State tmpState;
     
351.   int tmp;
     
352.   size = nowState.expandSize();//当前节点能扩展的节点数
     
353.   st = nowState.expandState();//获取所有扩展的节点
     
354.   for(i=0;i< size;i++)
     
355.   {
     
356.    if(!haveContained(st[i]))
     
357.    {
     
358.     value[i] = suggestFunc(st[i]);
     
359.     if(value[i] == 0)
     
360.     {
     
361.      move = nowState.judgeMove(st[i]);
     
362.      nowState = st[i];
     
363.      return 0;
     
364.     }
     
365.     else
     
366.      have = 1;
     
367.    }
     
368.   }
     
369.   if(have == 1)//对扩展的节点根据距离排序
     
370.   {
     
371.    for(i=0;i< size;i++)
     
372.    {
     
373.     for(j=i+1;j< size;j++)
     
374.     {
     
375.      if(value[j]>value[i])
     
376.      {
     
377.       tmp = value[j];
     
378.       tmpState = st[j];
     
379.       value[j] = value[i];
     
380.       st[j] = st[i];
     
381.       value[i] = tmp;
     
382.       st[i] = tmpState;
     
383.      }
     
384.     }
     
385.    }
     
386.    for(i=0;i< size;i++)
     
387.    {
     
388.     if(value[i]!=255)
     
389.     {
     
390.      vecOpen.add(st[i]);//所有扩展的节点排序后放入开集
     
391.     }
     
392.    }
     
393.   }
     
394.   return have;
     
395. }
     
396. }
     
397.                   

复制代码

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/11/7/000337140.zip