八数码问题源代码

1、自己用宽度优先算法写的八数码问题，有代码，有注释，有截图中间动态变化过程截图省略源代码：EightDigital.javapackage eightDigitalProblem;import java.util.*;public class EightDigital public static void main(String args) / TODO Auto-generated method stub/EightDigital ed = new EightDigital();/ed.launch();MyFrame mf = new MyFrame();mf.launchMyFrame()

2、;public Node launch(int startData, int endData)/起始结点赋值 /结束结点赋值 int array0 = new int9;Node s0 = new Node(array0);Node s = new Node(startData);s.setDepth(0);s.setStep(0);s.setFatherNode(s0);LinkedList open = new LinkedList(); /open集合open.add(s); /添加初始点LinkedList closed = new LinkedList(); /closed集合Nod

3、e n;while(true) /循环if(open.isEmpty()System.out.println(fail);System.exit(0);n = open.getFirst();if(goal(n, endData)System.out.println(success); /找到目标结点了break;closed.add(n); /把结点加入到closed表中open.removeFirst(); /删除最前面的结点LinkedList m = expand(n); /扩展结点while(!m.isEmpty()open.add(m.removeFirst();/找到目标结点n.

4、display();return n;public boolean goal(Node n, int endData)int array = new int9;/目标结点赋初值array0 = 1;array1 = 2;array2 = 3;array3 = 8;array4 = 0;array5 = 4;array6 = 7;array7 = 6;array8 = 5;/Node s = new Node(array); /目标结点Node s = new Node(endData); /目标结点if(s.equals(n)return true;elsereturn false;publi

5、c LinkedList expand(Node n) /n结点向外扩展，返回扩展的结点集合LinkedList temp = new LinkedList();int zeroPosition = n.getZeroPosition(n); /记录0(空格)的位置if(rightMove(zeroPosition) /空格可以向右移动Node newNode = new Node(n); /创造一个新结点newNode.getArray()zeroPosition = newNode.getArray()zeroPosition+1; /空格右移newNode.getArray()zeroP

6、osition+1 = 0;if( !n.getFatherNode().equals(newNode) ) /新产生的结点不能是结点n的父节点temp.add(newNode); /将新结点添加到集合newNode.setFatherNode(n); /设置新结点的父结点newNode.setStep(n.getStep()+1); /设置新结点到此走过的步长newNode.setDepth(newNode.getFatherNode().getDepth()+1); /设置深度if(leftMove(zeroPosition) /空格可以向左移动Node newNode = new Nod

7、e(n); /创造一个新结点newNode.getArray()zeroPosition = newNode.getArray()zeroPosition-1; /空格左移newNode.getArray()zeroPosition-1 = 0;if( !n.getFatherNode().equals(newNode) ) /新产生的结点不能是结点n的父节点temp.add(newNode); /将新结点添加到集合newNode.setFatherNode(n); /设置新结点的父结点newNode.setStep(n.getStep()+1); /设置新结点到此走过的步长newNode.s

8、etDepth(newNode.getFatherNode().getDepth()+1); /设置深度if(upMove(zeroPosition) /空格可以向上移动Node newNode = new Node(n); /创造一个新结点newNode.getArray()zeroPosition = newNode.getArray()zeroPosition-3; /空格上移newNode.getArray()zeroPosition-3 = 0;if( !n.getFatherNode().equals(newNode) ) /新产生的结点不能是结点n的父节点temp.add(new

9、Node); /将新结点添加到集合newNode.setFatherNode(n); /设置新结点的父结点newNode.setStep(n.getStep()+1); /设置新结点到此走过的步长newNode.setDepth(newNode.getFatherNode().getDepth()+1); /设置深度if(downMove(zeroPosition) /空格可以向下移动Node newNode = new Node(n); /创造一个新结点newNode.getArray()zeroPosition = newNode.getArray()zeroPosition+3; /空格

10、下移newNode.getArray()zeroPosition+3 = 0;if( !n.getFatherNode().equals(newNode) ) /新产生的结点不能是结点n的父节点temp.add(newNode); /将新结点添加到集合newNode.setFatherNode(n); /设置新结点的父结点newNode.setStep(n.getStep()+1); /设置新结点到此走过的步长newNode.setDepth(newNode.getFatherNode().getDepth()+1); /设置深度return temp;public boolean right

11、Move(int p) /判断能否空格能否向右移动if(p%3 = 2) /第3列不能往右移动了，第3列除以3的余数为2return false;else /第1，2列可以向右移动return true;public boolean leftMove(int p) /判断能否空格能否向左移动if(p%3 = 0) /第0列不能往左移动了，第1列除以3的余数为0return false;else /第2，3列可以向左移动return true;public boolean upMove(int p)if(p 5) /第3行 p=6,7,8 不能向下移动了return false;else /第

12、1，2行 可以向下移动return true;public LinkedList sortByDepth(LinkedList list)LinkedList temp = new LinkedList();while(!list.isEmpty()Node deepestNode = list.getFirst();Iterator ite = list.iterator();while(ite.hasNext()Node node = ite.next();if(node.getDepth()deepestNode.getDepth()deepestNode = node;temp.add

13、(deepestNode);list.remove(deepestNode);return temp;MyFrame.javapackage eightDigitalProblem;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.*;import java.awt.*;import java.util.Stack;public class MyFrame extends JFrame implements ActionListenerprivate static

14、final long serialVersionUID = 1L;private JMenuBar jmenubar;private JMenu jmenu1;private JMenu jmenu2;private JMenuItem jmenuitem1;private JMenuItem jmenuitem2;private JPanel jpanel1;private JPanel jpanel2;private JPanel jpanel3;private JPanel jpanel4;private JLabel jlabel1; /初始值private JLabel jlabel

15、2; /结束值private JLabel jlabel3; /提示private JLabel jlabel4; /提示private JTextField jtextfield1;private JTextField jtextfield2;private JTextField jtextfield3;private JLabel l1;private JLabel l2;private JLabel l3;private JLabel l4;private JLabel l5;private JLabel l6;private JLabel l7;private JLabel l8;pr

16、ivate JLabel l9;private Font font;private Font font2;HelpFrame helpFrame;MyFrame()jmenubar = new JMenuBar();jmenu1 = new JMenu(选择算法);jmenu2 = new JMenu(帮助);jmenuitem1 = new JMenuItem(宽度优先);jmenuitem2 = new JMenuItem(使用说明);jpanel1 = new JPanel();jpanel2 = new JPanel();jpanel3 = new JPanel();jpanel4 =

17、 new JPanel();jlabel1 = new JLabel(初始值：,JLabel.CENTER);jlabel2 = new JLabel(结束值：,JLabel.CENTER);jlabel3 = new JLabel(,JLabel.LEFT); /提示jlabel4 = new JLabel(,JLabel.LEFT); /提示jtextfield1 = new JTextField();jtextfield2 = new JTextField();jtextfield3 = new JTextField(步数);jtextfield3.setBackground(new C

18、olor(238,238,238);l1 = new JLabel(,JLabel.CENTER);l2 = new JLabel(,JLabel.CENTER);l3 = new JLabel(,JLabel.CENTER);l4 = new JLabel(,JLabel.CENTER);l5 = new JLabel(,JLabel.CENTER);l6 = new JLabel(,JLabel.CENTER);l7 = new JLabel(,JLabel.CENTER);l8 = new JLabel(,JLabel.CENTER);l9 = new JLabel(,JLabel.CE

19、NTER);font = new Font(Font.DIALOG,Font.BOLD,22);font2 = new Font(Font.DIALOG,Font.BOLD,14);public void launchMyFrame()jmenuitem1.addActionListener(this);jmenuitem2.addActionListener(this);jmenu1.add(jmenuitem1);jmenubar.add(jmenu1);jmenu2.add(jmenuitem2);jmenubar.add(jmenu2);jpanel1.setLayout(new Gr

20、idLayout(1,2);jpanel1.add(jlabel1);jpanel1.add(jtextfield1);jpanel2.setLayout(new GridLayout(1,2);jpanel2.add(jlabel2);jpanel2.add(jtextfield2);jpanel3.setLayout(new GridLayout(3,3);jpanel3.add(l1);jpanel3.add(l2);jpanel3.add(l3);jpanel3.add(l4);jpanel3.add(l5);jpanel3.add(l6);jpanel3.add(l7);jpanel

21、3.add(l8);jpanel3.add(l9);jpanel4.setLayout(new GridLayout(2,2);jpanel4.add(jpanel1);jpanel4.add(jlabel3);jpanel4.add(jpanel2);jpanel4.add(jlabel4);/设置字体l1.setFont(font);l2.setFont(font);l3.setFont(font);l4.setFont(font);l5.setFont(font);l6.setFont(font);l7.setFont(font);l8.setFont(font);l9.setFont(

22、font);jtextfield3.setFont(font2);this.setLayout(new BorderLayout();this.add(jpanel4,BorderLayout.NORTH); /上面this.add(jpanel3,BorderLayout.CENTER); /中间this.add(jtextfield3,BorderLayout.SOUTH); /下面setJMenuBar(jmenubar);setSize(330,350); /设置大小setLocation(510,180); /设置位置setTitle(EightDigital); /设置标题setD

23、efaultCloseOperation(JFrame.EXIT_ON_CLOSE);setVisible(true); /设为可见Overridepublic void actionPerformed(ActionEvent e) / TODO Auto-generated method stubObject source=e.getSource();if(source = jmenuitem1)boolean flag = true;EightDigital ed;int array1 = new int9;int array2 = new int9;int attribute = 0;

24、/逆序数的奇偶性 0-偶 1-奇int reNum; /逆序数String startData = jtextfield1.getText().trim();if(startData.length() != 9) /长度必须为9jlabel3.setText(请输入0-8的一个排列！);flag = false;jpanel3.setVisible(false);else if(!isNumber(startData) /每个都必须是数字0-8jlabel3.setText(请输入0-8的一个排列！);flag = false;jpanel3.setVisible(false);elsejla

25、bel3.setText();for(int i=0; i9; i+) /将startData转化为整数数组Character c = startData.charAt(i);array1i = Integer.parseInt(c.toString();if(repeatNum(array1)flag = false;jlabel3.setText(有重复的数字！);jpanel3.setVisible(false);elsereNum = reverseNum(array1);jlabel3.setText(逆序数: + reNum);attribute = reNum%2; /0-偶 1

26、-奇String endData = jtextfield2.getText().trim();if(endData.length() != 9) /长度必须为9jlabel4.setText(请输入0-8的一个排列！);flag = false;jpanel3.setVisible(false);else if(!isNumber(endData) /每个都必须是数字0-8jlabel4.setText(请输入0-8的一个排列！);flag = false;jpanel3.setVisible(false);elsejlabel4.setText();for(int i=0; i9; i+)

27、 /将startData转化为整数数组Character c = endData.charAt(i);array2i = Integer.parseInt(c.toString();if(repeatNum(array2)flag = false;jlabel4.setText(有重复的数字！);jpanel3.setVisible(false);elsereNum = reverseNum(array2);jlabel4.setText(逆序数: + reNum);if(reNum%2 != attribute) /两个逆序数的奇偶性不一致flag = false;jlabel4.setTe

28、xt(逆序数: + reNum + + 奇偶不一致);jpanel3.setVisible(false);if(flag)ed = new EightDigital();jpanel3.setVisible(true);showProcess(ed.launch(array1,array2);else if(source = jmenuitem2)helpFrame = new HelpFrame();helpFrame.launchHelpFrame();public boolean isNumber(String data) /判断是否是数字0-8char array = data.toC

29、harArray();boolean flag = true;int temp;for(char c : array)/flag = Character.isDigit(c); /判断是否为数字if(flag = Character.isDigit(c)Character ch = c;temp = Integer.parseInt(ch.toString();if(temp = 9)flag = false;if(flag = false)break;System.out.println(flag = + flag); /testreturn flag;public boolean repe

30、atNum(int array) /判断是否有重复的数字boolean flag = false;int temp = new intarray.length;for(int i:array)tempi = 1; /有数字的地方标记为1for(int j:temp)if(j=0)flag = true; /有一个数字没有出现return flag;public void showProcess(final Node n) /展示搜索过程new Thread(new Runnable()Overridepublic void run() / TODO Auto-generated method

31、stubStack stack = new Stack();Node fatherNode = n.getFatherNode();stack.add(n);while(fatherNode != null)stack.add(fatherNode); /入栈fatherNode = fatherNode.getFatherNode();stack.pop();while(!stack.isEmpty() /从栈中去结点Node cnode = stack.pop();int array = cnode.getArray();l1.setText(array0+);l2.setText(arr

32、ay1+);l3.setText(array2+);l4.setText(array3+);l5.setText(array4+);l6.setText(array5+);l7.setText(array6+);l8.setText(array7+);l9.setText(array8+);jtextfield3.setText(第 + cnode.getStep() + 步); /显示步数tryThread.sleep(2000); /暂停一会catch(Exception e)e.printStackTrace();).start();public int reverseNum(int a

33、rray) /求逆序数int num = 0;for(int i=0; iarray.length-1; i+)for(int j=i+1; j0 & arrayj0 & arrayiarrayj)num+;return num;Node.javapackage eightDigitalProblem;import java.awt.event.ActionEvent;import java.awt.event.ActionListener;import javax.swing.*;import java.awt.*;import java.util.Stack;public class My

34、Frame extends JFrame implements ActionListenerprivate static final long serialVersionUID = 1L;private JMenuBar jmenubar;private JMenu jmenu1;private JMenu jmenu2;private JMenuItem jmenuitem1;private JMenuItem jmenuitem2;private JPanel jpanel1;private JPanel jpanel2;private JPanel jpanel3;private JPa

35、nel jpanel4;private JLabel jlabel1; /初始值private JLabel jlabel2; /结束值private JLabel jlabel3; /提示private JLabel jlabel4; /提示private JTextField jtextfield1;private JTextField jtextfield2;private JTextField jtextfield3;private JLabel l1;private JLabel l2;private JLabel l3;private JLabel l4;private JLabe

36、l l5;private JLabel l6;private JLabel l7;private JLabel l8;private JLabel l9;private Font font;private Font font2;HelpFrame helpFrame;MyFrame()jmenubar = new JMenuBar();jmenu1 = new JMenu(选择算法);jmenu2 = new JMenu(帮助);jmenuitem1 = new JMenuItem(宽度优先);jmenuitem2 = new JMenuItem(使用说明);jpanel1 = new JPa

37、nel();jpanel2 = new JPanel();jpanel3 = new JPanel();jpanel4 = new JPanel();jlabel1 = new JLabel(初始值：,JLabel.CENTER);jlabel2 = new JLabel(结束值：,JLabel.CENTER);jlabel3 = new JLabel(,JLabel.LEFT); /提示jlabel4 = new JLabel(,JLabel.LEFT); /提示jtextfield1 = new JTextField();jtextfield2 = new JTextField();jte

38、xtfield3 = new JTextField(步数);jtextfield3.setBackground(new Color(238,238,238);l1 = new JLabel(,JLabel.CENTER);l2 = new JLabel(,JLabel.CENTER);l3 = new JLabel(,JLabel.CENTER);l4 = new JLabel(,JLabel.CENTER);l5 = new JLabel(,JLabel.CENTER);l6 = new JLabel(,JLabel.CENTER);l7 = new JLabel(,JLabel.CENTE

39、R);l8 = new JLabel(,JLabel.CENTER);l9 = new JLabel(,JLabel.CENTER);font = new Font(Font.DIALOG,Font.BOLD,22);font2 = new Font(Font.DIALOG,Font.BOLD,14);public void launchMyFrame()jmenuitem1.addActionListener(this);jmenuitem2.addActionListener(this);jmenu1.add(jmenuitem1);jmenubar.add(jmenu1);jmenu2.

40、add(jmenuitem2);jmenubar.add(jmenu2);jpanel1.setLayout(new GridLayout(1,2);jpanel1.add(jlabel1);jpanel1.add(jtextfield1);jpanel2.setLayout(new GridLayout(1,2);jpanel2.add(jlabel2);jpanel2.add(jtextfield2);jpanel3.setLayout(new GridLayout(3,3);jpanel3.add(l1);jpanel3.add(l2);jpanel3.add(l3);jpanel3.a

41、dd(l4);jpanel3.add(l5);jpanel3.add(l6);jpanel3.add(l7);jpanel3.add(l8);jpanel3.add(l9);jpanel4.setLayout(new GridLayout(2,2);jpanel4.add(jpanel1);jpanel4.add(jlabel3);jpanel4.add(jpanel2);jpanel4.add(jlabel4);/设置字体l1.setFont(font);l2.setFont(font);l3.setFont(font);l4.setFont(font);l5.setFont(font);l

42、6.setFont(font);l7.setFont(font);l8.setFont(font);l9.setFont(font);jtextfield3.setFont(font2);this.setLayout(new BorderLayout();this.add(jpanel4,BorderLayout.NORTH); /上面this.add(jpanel3,BorderLayout.CENTER); /中间this.add(jtextfield3,BorderLayout.SOUTH); /下面setJMenuBar(jmenubar);setSize(330,350); /设置大

43、小setLocation(510,180); /设置位置setTitle(EightDigital); /设置标题setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);setVisible(true); /设为可见Overridepublic void actionPerformed(ActionEvent e) / TODO Auto-generated method stubObject source=e.getSource();if(source = jmenuitem1)boolean flag = true;EightDigital ed;in

44、t array1 = new int9;int array2 = new int9;int attribute = 0; /逆序数的奇偶性 0-偶 1-奇int reNum; /逆序数String startData = jtextfield1.getText().trim();if(startData.length() != 9) /长度必须为9jlabel3.setText(请输入0-8的一个排列！);flag = false;jpanel3.setVisible(false);else if(!isNumber(startData) /每个都必须是数字0-8jlabel3.setText

45、(请输入0-8的一个排列！);flag = false;jpanel3.setVisible(false);elsejlabel3.setText();for(int i=0; i9; i+) /将startData转化为整数数组Character c = startData.charAt(i);array1i = Integer.parseInt(c.toString();if(repeatNum(array1)flag = false;jlabel3.setText(有重复的数字！);jpanel3.setVisible(false);elsereNum = reverseNum(array1);jlabel3.setText(逆序数: + reNum);attribute = reNum%2; /0-偶 1-奇String endData = jtextfield2.getText().trim();if(endData.length() != 9) /长度必须为9jlabel4.setText(请输入0-8的一个排列！);flag = false;jpanel3.setVisible(false);else if(!isNumber(endData) /每个都必须是数字0-8jlabe