采用了 A* 算法（不在位的将牌的距离和，和深度 的和做 函数值进行优先搜索）这是第一个纯自己码的分享一下 欢迎批评指正！
package com.zyl; import java.util.*; /** * * @author zhaoYuLong * ：QQ 406244471 * @version 1.0 * */ public class Shuma { final static int N = 3 ; //保存数组大小 int kk = 0;//保存 遍历路径表的个数 避免数组越界 int y = 0 ;//保存 解的成功与否 ArrayList<Integer> s ; // 初始状态 ArrayList<Integer> g ; // 目标状态 ArrayList<Xmap> open ; // 待扩展节点 ArrayList<Xmap> close ; // 已扩展节点 ArrayList<Xmap> luJing ; // 最优路径节点 ArrayList<Integer> csz ; // 初始节点的 father int yu = 0 ; int [][] g1 = {{1,2,3},{8,0,4},{7,6,5}};// 奇偶 逆序和 对应的两个二维数组（0代表空格） int [][] g2 = {{1,2,3},{4,5,6},{7,8,0}}; int [][] g0 = {{0,0,0},{0,0,0},{0,0,0}}; ; // 确认之后的目标数组 int [][] s0 = {{0,0,0},{0,0,0},{0,0,0}}; // 生成的起始随机数组 public Shuma() { // 完成open表等值的初始化 this.init(); } // 初始化 开始状态 、open表初始化、 起始数组 和 目标状态、目标数组 public void init (){ csz = new ArrayList<Integer>(); s = new ArrayList<>(); g = new ArrayList<Integer>(); open = new ArrayList<Xmap>(); close = new ArrayList<Xmap>(); int yuShu = 0; change(csz,s0); // 初始状态 for(int i = 0 ; i < N*N ; i++) { s.add(i); } Collections.shuffle(s);// 打乱 changeA(s0,s); // 目标状态 yuShu = niXu(s); yu = yuShu ; // 对不同初始状态设定目标值 同时初始化open表 //奇 if(yuShu == 1) { change(g,g1); g0 = g1; Xmap map = new Xmap(); map.arr.addAll(s); map.p = compDis(g1,s0); map.deep = 0; map.f = map.p + map.deep ; map.dir = "初始图"; map.father = csz ; open.add(map); // 求逆序和 } //偶 else { change(g,g2); g0 = g2; Xmap map = new Xmap(); map.arr.addAll(s); map.p = compDis(g1,s0); map.deep = 0; map.f = map.p + map.deep ; map.father = csz ; open.add(map); } } // 求逆序和 public int niXu(ArrayList<Integer> as) { int count = 0 ; int yuShu = 0 ; for(int i = 0 ; i < s.size() ; i++) { for(int j = 0 ; j < i ; j++) { if(((int)as.get(j) > (int)as.get(i))&&(int)as.get(i)!=0) { count++; } } } yuShu = count % 2 ; return yuShu; } // 将ArrayList 变成数组 public void changeA (int[][] a , ArrayList<Integer> arr) { int num = 0 ; for(int i = 0 ; i < N ; i++) { for(int j = 0 ; j < N ; j++) { a[i][j] = (int)arr.get(num) ; num++ ; } } } // 将数组变成ArrayList public void change ( ArrayList<Integer> arr,int[][] a ) { for(int i = 0 ; i < N ; i++) { for(int j = 0 ; j < N ; j++) { arr.add(a[i][j]) ; } } } // 计算不在位将的距离和 public int compDis ( int[][] a,int[][] b ) { int count = 0 ; for(int i = 0 ; i < N ; i++) { for(int j = 0 ; j < N ; j++) { if(a[i][j] != b[i][j] && a[i][j] != 0) { count += Math.abs(getX(a[i][j],b) - getX(a[i][j],a)) + Math.abs(getY(a[i][j],b) - getY(a[i][j],a)) ; } } } return count ; } // 返回某数的坐标的X值 public int getX ( int c,int[][] d ) { int x = 0 ; for(int i = 0 ; i < N ; i++) { for(int j = 0 ; j < N ; j++) { if(d[i][j] == c) { x = i ; } } } return x ; } // 返回某数的坐标的Y值 public int getY ( int c,int[][] d ) { int y = 0 ; for(int i = 0 ; i < N ; i++) { for(int j = 0 ; j < N ; j++) { if(d[i][j] == c) { y = j ; } } } return y ; } // 完成空格满足规则的移动 并且之后将扩展的节点初始化 然后加入 open表中 public void move(Xmap abc) { // 将传入的参数的 list 转化为数组 便于后面的比较使用 int [][] a = new int[3][3]; changeA(a,abc.arr); // 获得 0（空格）所在的坐标 int x,y ; x = getX(0,a); y = getY(0,a); // 定义4个 list 来完成移动后的数据保存（由于修改一次后后面在移动就不能用了所以定义4个） ArrayList<Integer> list0 = new ArrayList <>() ; ArrayList<Integer> list1 = new ArrayList <>() ; ArrayList<Integer> list2 = new ArrayList <>() ; ArrayList<Integer> list3 = new ArrayList <>() ; list0.addAll(abc.arr); list1.addAll(abc.arr); list2.addAll(abc.arr); list3.addAll(abc.arr); // 移动：利用坐标的范围来过滤不合法的移动规则 // 左移 if( (y-1) > -1) { // 定义一个二维数组用于保存移动后的数据图 int [][] r0 = new int[3][3]; Xmap map0 = new Xmap(); // 利用图形的排列规律 将0所在序号和序号减一的交换即可完成左移 （以下同理） Collections.swap(list0, list0.indexOf(0), list0.indexOf(0)-1); // 把list转换成数组用于比较 changeA(r0,list0); // 遍历open表和close表 保证没有重复的状态加入 boolean bool1 = true ; for(Xmap m : close){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r0)) { bool1 = false; } } for(Xmap m : open){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r0)) { bool1 = false; } } // 如果没有相同状态的则将其加入 并完成初始化 if(bool1) { map0.arr.addAll(list0) ; // 状态图赋值保存（利用了addAll()来拷贝） map0.deep = abc.deep+1; // 利用父节点的节点深度加1即可得扩展节点的深度值（开始定义初始节点的深度为0） map0.p = compDis(r0,g0); // 距离和计算并赋值保存 map0.f = map0.p + map0.deep ;// f值为所有不在位的将牌的距离和加节点所处深度的和 map0.dir = "左移"; // 保存父节点到他的移动方向 map0.father = abc.arr ; //保存父节点的图状态信息 用于后面找父节点 open.add(map0); // 加入open 表完成单方向扩展 } } // 右移 if((y+1) < 3 ) { int [][] r1 = new int[3][3]; Xmap map1 = new Xmap(); Collections.swap(list1, list1.indexOf(0), list1.indexOf(0)+1); changeA(r1,list1); boolean bool1 = true ; for(Xmap m : open){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r1)) { bool1 = false; } } for(Xmap m : close){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r1)) { bool1 = false; } } if(bool1) { map1.arr.addAll(list1) ; map1.deep = abc.deep+1; map1.p = compDis(r1,g0); map1.f = map1.p + map1.deep ; map1.dir = "右移"; map1.father = abc.arr; open.add(map1); } } // 上移 if((x-1) > -1) { int [][] r2 = new int[3][3]; Xmap map2 = new Xmap(); Collections.swap(list2, list2.indexOf(0), list2.indexOf(0)-3); changeA(r2,list2); boolean bool1 = true ; for(Xmap m : open){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r2)) { bool1 = false; } } for(Xmap m : close){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r2)) { bool1 = false; } } if(bool1) { map2.arr.addAll(list2) ; map2.deep = abc.deep+1; map2.p = compDis(r2,g0); map2.f = map2.p + map2.deep ; map2.dir = "上移"; map2.father = abc.arr ; open.add(map2); } } // 下移 if((x+1) < 3 ) { int [][] r3 = new int[3][3]; Xmap map3 = new Xmap(); Collections.swap(list3, list3.indexOf(0), list3.indexOf(0)+3); changeA(r3,list3); boolean bool1 = true ; for(Xmap m : open){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r3)) { bool1 = false; } } for(Xmap m : close){ int [][] ar = new int [3][3]; changeA(ar, m.arr); if(equals(ar,r3)) { bool1 = false; } } if(bool1) { map3.arr.addAll(list3) ; map3.deep = abc.deep+1; map3.p = compDis(r3,g0); map3.f = map3.p + map3.deep ; map3.dir = "下移"; map3.father = abc.arr ; open.add(map3); } } } // 游戏的开始方法 public boolean play() { boolean bl = true ; while(bl) { // 1.判断open表是否为空？ 为空则输出“fail” 否 则继续 if(open.isEmpty()) { y = -1 ; Xframe.text.append("fail\n"); break; } // 2.将open表中的第一个状态对象赋值给map1 Xmap map1 = new Xmap(); map1 = open.get(0); // 2.1将第一个的状态图也就是list 转化为二维数组（ 后面要调用方法比较） int [][] temp = new int[3][3]; changeA(temp,map1.arr); // 3.判断该状态图是否为目标值？ 是则输出“success” 否 则继续 if(equals(temp,g0)){ y = 1 ; break; } // 4.将第一个节点从open表中删除 open.remove(0); // 5.将第一个节点加入至close表中 close.add(map1); // 6.扩展节点 move(map1); // 7.对open表根据f值升序排序（f=p+deep (所有不在位的将牌的距离和+节点所处深度)） // 并且f值相同的节点 先加入的排在前面 open.sort((o1,o2)->((Xmap)o1).f - ((Xmap)o2).f); // 重绘数据显示的9宫格 Xframe.paint(this); } //while的一个循环 只有当 open表为空也就是遍历了所有结果没找到目标值 和成功 //找到目标值时 才退出循环 return true; } // 用于比较两个数组是否相同坐标所对应的值相同 public boolean equals(int[][] aa , int [][] bb) { boolean bool = true ; for(int i = 0 ; i < N ; i++) { for(int j = 0 ; j < N ; j++) { if(aa[i][j] != bb[i][j]) { bool = false ; } } } return bool; } // 输出初始信息 public void infoFirst() { Xframe.text.append(" -------------------------------------- 8数码游戏 --------------------------------------- \n\n"); // 输出初始状态（仅用于检测使用） Xframe.text.append(" 初始状态: （0代表空格）"); if(yu == 1) { Xframe.text.append(" （逆序和为奇）\n"); } else { Xframe.text.append(" （逆序和为偶）\n"); } for(int i = 0 ; i < N ; i++) { Xframe.text.append(" "+Arrays.toString(s0[i])+"\n"); } // 完成初始状态的 list 表转化为二维数组 int[][] aa = new int[3][3]; changeA(aa, g); Xframe.text.append("\n"); // 输出目标状态（仅用于检测使用） Xframe.text.append(" 目标状态:\n"); for(int i = 0 ; i < N ; i++) { Xframe.text.append(" "+Arrays.toString(aa[i])+"\n"); } Xframe.text.append("\n"); Xframe.text.append("初始状态到目标状态的不在位将牌距离和:"); // 输出初始状态到目标状态的不在位将牌距离和（仅用于检测使用） Xframe.text.append(compDis(s0, aa)+"\n"); Xframe.text.append("\n"); } // 用于输出扩展节点个数和存储结点个数（结束信息） public void infoLast() { Xframe.text.append(" 扩展节点个数："+close.size()+"\n"); Xframe.text.append(" 存储节点个数："+(open.size()+close.size())+"\n"); Xframe.text.append(" 最短路径："+open.get(0).deep+"\n"); Xframe.text.append("\n"); path(close); } // 输出初始状态到目标状态的路径图 public void path (ArrayList<Xmap> app ) { luJing = new ArrayList<Xmap>(); luJing.add(open.get(0)); int[][] a = new int[N][N] ; int[][] b = new int[N][N] ; boolean bool = true ; while(bool) { int[][] tem = {{0,0,0},{0,0,0},{0,0,0}}; for(int i = 0 ; i < app.size() ;i++) { changeA(a,app.get(i).arr); changeA(b,luJing.get(luJing.size()-1).father); if(equals(a,b)) { luJing.add(app.get(i)); } if(equals(tem,b)) { bool = false ; } } } Collections.reverse(luJing); Xframe.text.append(" --------------------------------------- 路径图 ----------------------------------------- （0 代表空格）\n"); for(int i = 0 ; i < luJing.size() ; i++) { Xframe.text.append(" "+i+": "+luJing.get(i).dir+"\n"); Xframe.text.append(""); for(int j = 0 ; j < N*N ; j++) { Xframe.text.append(luJing.get(i).arr.get(j)+" "); if((j+1)%3 == 0 && j!=(N*N-1)) { Xframe.text.append("\n"); Xframe.text.append(""); } } Xframe.text.append("\n"); } Xframe.text.append("\n"); Xframe.text.append(" --------------------------------------- 游戏结束 ----------------------------------------- \n"); } // 输出详细步骤 public void mq () { this.infoFirst(); Xframe.text.append(" ------------------------------------- 开始游戏 ----------------------------------------- \n"); Xframe.text.append("\n"); Xframe.text.append(" 遍历结果统计："); // 开始游戏 this.infoLast(); } } package com.zyl; import java.awt.*; import java.awt.event.*; import java.util.ArrayList; import javax.swing.*; public class Xframe { // 定义所需变量 JFrame frame ; //窗体 JButton start ; //开始按钮 JButton reset ; //重置按钮 JButton hand; //最优路径展示按钮 JLabel zhuangTai ; //状态标签 JLabel author ; //作者标签 JPanel card1 ; //游戏面板 JPanel card2 ; //详细步骤面板 JPanel panel9 ; //9宫格 JTabbedPane tab; //分页面板 static JTextArea text ; //输出详细步骤文本 String str1 = "游戏界面" ; // String str2 = "详细步骤" ; // Shuma mm ; //定义一个 数码对象 static ArrayList <JLabel> lab ; //保存状态图信息的 标签集合 static ArrayList<JPanel> pan ; //用于填充9宫格的面板 // 构造方法 public Xframe() { // 调用初始界面方法 this.init(); } // 初始化界面 public void init () { // 创建所需对象 mm = new Shuma() ; hand = new JButton("最优路径展示"); zhuangTai = new JLabel("状态：初始状态"); lab = new ArrayList<JLabel>(); pan = new ArrayList<JPanel>(); // 创建窗体 frame = new JFrame("8数码--启发式宽度优先搜索") ; frame.setLocation(400,100);// 大小 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);// // 游戏界面 card1 = new JPanel(); //游戏面板 card1.setPreferredSize(new Dimension(500,500));//大小 JPanel a = new JPanel();//填充面板 a.setPreferredSize(new Dimension(1500,70));//大小 card1.add(a);//添加 panel9 = new JPanel();//9 宫格 panel9.setPreferredSize(new Dimension(300,300));//大小 panel9.setLayout(new GridLayout(3,3));//3*3布局 panel9.setBorder(BorderFactory.createBevelBorder(1));//边框 csh();//完成9宫格初始化 card1.add(panel9) ;//添加 JPanel a1 = new JPanel();//填充面板 用于排版 a1.setPreferredSize(new Dimension(1500,40));//大小 card1.add(a1);//添加 JPanel a2 = new JPanel();//填充面板 用于排版 a2.setPreferredSize(new Dimension(1300,20));//大小 card1.add(a2);//添加 start = new JButton("开始（自动）");//开始按钮 start.addActionListener(new ActionListener() {// 监听 @Override public void actionPerformed(ActionEvent e) { // TODO 自动生成的方法存根 zhuangTai.setText("状态：拼命运算中"); // 状态改变 mm.play(); // 开始运算 if(mm.y == 1) { mm.mq(); // 将详细步骤输出到文本域 text.setCaretPosition(0); zhuangTai.setText("状态：成功"); // 状态改变 } if(mm.y == -1) { zhuangTai.setText("状态：失败"); } }; }); reset = new JButton("重置"); // 重置按钮 reset.addActionListener(new ActionListener() { // 监听 @Override public void actionPerformed(ActionEvent e) { // TODO 自动生成的方法存根 text.setText(null); mm = new Shuma(); paint(mm); zhuangTai.setText("状态：已重置"); }; }); card1.add(start); // 添加 JPanel a5 = new JPanel(); // 排版面板 a5.setPreferredSize(new Dimension(30,20)); card1.add(a5); hand.addActionListener(new ActionListener() { // 最优路径 按钮监听 @Override public void actionPerformed(ActionEvent e) { if(mm.kk == 0 && mm.luJing.size() != 0) { // 判断是否为第一个 zhuangTai.setText("状态：已恢复至初始位置"); } else // 判断是否为中间节点 if(mm.kk < mm.luJing.size()-1) { zhuangTai.setText("状态：第"+mm.kk+"次移动("+mm.luJing.get(mm.kk).dir+")"); } else // 判断是否为目标节点 if(mm.kk == mm.luJing.size()-1) { zhuangTai.setText("状态：成功（共移动"+mm.kk+"次）"); } // TODO 自动生成的方法存根 if(mm.y == 1 && mm.kk < mm.luJing.size()) { // 完成每一步移动的显示 for(int i = 0 ; i < 9 ; i++ ) { if((int)mm.luJing.get(mm.kk).arr.get(i) == 0) { Xframe.lab.get(i).setText(null); } else { Xframe.lab.get(i).setText(Integer.toString(mm.luJing.get(mm.kk).arr.get(i))); } } mm.kk++; } }; }); card1.add(hand); JPanel a3 = new JPanel(); // 排版面板 a3.setPreferredSize(new Dimension(70,20)); card1.add(a3); card1.add(reset); JPanel a4 = new JPanel(); // 排版面板 a4.setPreferredSize(new Dimension(1500,30)); card1.add(a4); card1.add(zhuangTai); JPanel a6 = new JPanel(); // 排版面板 a6.setPreferredSize(new Dimension(3000,50)); card1.add(a6); JPanel a7 = new JPanel(); // 排版面板 a7.setPreferredSize(new Dimension(600,5)); card1.add(a7); author = new JLabel("Author:zhaoYuLong"); card1.add(author); // 详细步骤界面 card2 = new JPanel(); // 详细步骤面板 card2.setPreferredSize(new Dimension(500,500)); // 大小 text = new JTextArea(37,50); // 文本域大小 text.setEditable(false); // 设置为不可编辑 text.setLineWrap(true); // 自动换行 text.setWrapStyleWord(true); // 已完整单词换行 JScrollPane p = new JScrollPane(text); // 加入滚动条面板 card2.add(p) ; // 添加 // 将两个界面 加入 JTabbedPane tab = new JTabbedPane(JTabbedPane.TOP,JTabbedPane.WRAP_TAB_LAYOUT); tab.addTab(str1,card1); tab.addTab(str2,card2); // 将JTabbedPane加入窗体 frame.add(tab) ; frame.setExtendedState(Frame.MAXIMIZED_BOTH); // 最大化显示 frame.setVisible(true);// 显示 } //完成图信息保存至JLabel 集合 public static void labC (Shuma mm ,ArrayList<JLabel> lab ) { for(int i = 0 ; i < 9 ; i++) { if((int)mm.open.get(0).arr.get(i) == 0) { lab.add(new JLabel()); } else { lab.add(new JLabel(Integer.toString(mm.open.get(0).arr.get(i)))); } } } // 将9宫格中添加 9 个3*1的面板 public static void panC (ArrayList<JPanel> p ) { for(int i = 0 ; i < 9 ; i++) { JPanel pp = new JPanel(); pp.setLayout(new GridLayout(3, 1));; pp.setBorder(BorderFactory.createLineBorder(Color.BLACK, 1)); p.add(pp); } } // 将保存图信息的 JLabel 利用 排版面板 显示在格子中央 public static void pan (ArrayList<JLabel> lab ,ArrayList<JPanel> p ,JPanel panel) { for(int i = 0 ; i < 9 ; i++) { for(int j = 0 ; j < 3 ; j++) { JPanel pp = new JPanel(); if(j == 1) { pp.add(lab.get(i)); } p.get(i).add(pp); } panel.add(p.get(i)); } } // 将9宫格带数据完成初始化 public void csh () { labC(mm,lab); panC(pan); pan(lab,pan,panel9); } // 重置9宫格数据 public static void paint(Shuma mm) { for(int i = 0 ;i < 9 ; i++) { if((int)mm.open.get(0).arr.get(i) == 0) { lab.get(i).setText(null); } else { lab.get(i).setText(Integer.toString(mm.open.get(0).arr.get(i))); } } } } package com.zyl; import java.util.*; // 为了方便保存状态图 和 启发函数值 定义了单独 的一个类 public class Xmap { public ArrayList<Integer> arr = new ArrayList<>(); // 状态图用一个 ArrayList 集合表示 //（由于他方便遍历和可以使用Collections 工具类来洗牌） public ArrayList<Integer> father = new ArrayList<>(); // 保存父节点的 图 public int deep; // 保存节点深度 public int p; // 保存不在位将牌的距离和 public int f; // 保存启发函数值 public String dir = new String();// 保存父节点到该节点空格移动方向 } package com.zyl; public class Main { // 主方法 public static void main(String[] args) { // TODO 自动生成的方法存根 // 使用无参构造函数生成Xframe匿名对象 new Xframe(); } }工程文件 ：链接：http://pan.baidu.com/s/1kVdqZxd 密码：a74r
