重拍九宫问题JAVA实现——三种方法

package jiugong; import javax.swing.table.DefaultTableModel; import java.util.LinkedList; public class AStar { private static LinkedList open=new LinkedList(); private static LinkedList closed=new LinkedList(); private static LinkedList path=new LinkedList(); private static Node quicknode=null; private static int[][]d=new int[3][3]; private static class Node{ int value; int diff=0; int depth=-1; int data[][]; int row; int clumn; Node parent; Node(int data[][],Node parent,int row,int clumn,int depth,int diff){ this.data=data; this.parent=parent; this.row=row; this.clumn=clumn; this.depth=depth; this.diff=diff; this.value=depth+diff; } } private static int DiffValue(int[][] src,int[][] dest){ int diff=0; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(src[i][j]!=dest[i][j]){ diff++; } } } return diff; } private static void AStarMoveExtend(Node current){ int depth=current.depth+1; int row=current.row; int clumn=current.clumn; Node child; if(clumn!=0){ if(current.parent.row!=row||current.parent.clumn!=clumn-1){ int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0; if(data[row][clumn]==d[row][clumn]){ if(data[row][clumn-1]==d[row][clumn-1]){ diff=current.diff+2; }else{ diff=current.diff+1; } }else{ if(data[row][clumn]==d[row][clumn-1]){ if(data[row][clumn-1]==d[row][clumn]){ diff=current.diff-2; }else{ diff=current.diff-1; } }else{ if(data[row][clumn-1]==d[row][clumn]){ diff=current.diff-1; }else{ if(data[row][clumn-1]==d[row][clumn-1]){ diff=current.diff+1; }else{ diff=current.diff; } } } } int temp=data[row][clumn]; data[row][clumn]=data[row][clumn-1]; data[row][clumn-1]=temp; child=new Node(data,current,row,clumn-1,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{ open.add(child); } } } if(row!=0){ if(current.parent.row!=row-1||current.parent.clumn!=clumn){ int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0; if(data[row][clumn]==d[row][clumn]){ if(data[row-1][clumn]==d[row-1][clumn]){ diff=current.diff+2; }else{ diff=current.diff+1; } }else{ if(data[row][clumn]==d[row-1][clumn]){ if(data[row-1][clumn]==d[row][clumn]){ diff=current.diff-2; }else{ diff=current.diff-1; } }else{ if(data[row-1][clumn]==d[row][clumn]){ diff=current.diff-1; }else{ if(data[row-1][clumn]==d[row-1][clumn]){ diff=current.diff+1; }else{ diff=current.diff; } } } } int temp=data[row][clumn]; data[row][clumn]=data[row-1][clumn]; data[row-1][clumn]=temp; child=new Node(data,current,row-1,clumn,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{ open.add(child); } } } if(clumn!=2){ if(current.parent.row!=row||current.parent.clumn!=clumn+1){ int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0; if(data[row][clumn]==d[row][clumn]){ if(data[row][clumn+1]==d[row][clumn+1]){ diff=current.diff+2; }else{ diff=current.diff+1; } }else{ if(data[row][clumn]==d[row][clumn+1]){ if(data[row][clumn+1]==d[row][clumn]){ diff=current.diff-2; }else{ diff=current.diff-1; } }else{ if(data[row][clumn+1]==d[row][clumn]){ diff=current.diff-1; }else{ if(data[row][clumn+1]==d[row][clumn+1]){ diff=current.diff+1; }else{ diff=current.diff; } } } } int temp=data[row][clumn]; data[row][clumn]=data[row][clumn+1]; data[row][clumn+1]=temp; child=new Node(data,current,row,clumn+1,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{ open.add(child); } } } if(row!=2){ if(current.parent.row!=row+1||current.parent.clumn!=clumn){ int data[][]=new int[3][3]; data=Method.copy(current.data); int diff=0; if(data[row][clumn]==d[row][clumn]){ if(data[row+1][clumn]==d[row+1][clumn]){ diff=current.diff+2; }else{ diff=current.diff+1; } }else{ if(data[row][clumn]==d[row+1][clumn]){ if(data[row+1][clumn]==d[row][clumn]){ diff=current.diff-2; }else{ diff=current.diff-1; } }else{ if(data[row+1][clumn]==d[row][clumn]){ diff=current.diff-1; }else{ if(data[row+1][clumn]==d[row+1][clumn]){ diff=current.diff+1; }else{ diff=current.diff; } } } } int temp=data[row][clumn]; data[row][clumn]=data[row+1][clumn]; data[row+1][clumn]=temp; child=new Node(data,current,row+1,clumn,depth,diff); if(diff==-1||diff==-2){ quicknode=child; }else{ open.add(child); } } } } private static void SelectMin(){ int size=open.size(); int k=0; for(int i=1;i<size;i++){ if(((Node)open.get(k)).value>((Node)open.get(i)).value){ k=i; } } if(k!=0){ Node node=(Node)open.get(0); open.set(0, (Node)open.get(k)); open.set(k, node); } } private static void GetPath(Node node,Node supernode){ while(node.parent!=null){ path.addFirst(node); node=node.parent; } } public static void A_Star(MainFrame frame,DefaultTableModel src,DefaultTableModel dest){ open=new LinkedList(); closed=new LinkedList(); path=new LinkedList(); int s[][]; int location[]=new int[2]; s=Method.toTwoArray(src); d=Method.toTwoArray(dest); location=Method.Location(s, 0); if(Method.isSolutionExist(Method.toArray(src), Method.toArray(dest),s,d)){ frame.jTextArea1.setText("有解\n");