eightnum.java

来自「这是用netbeans开发的,里面有窗口之类的.请高手指点」· Java 代码 · 共 346 行

/*
 *
 *author wgq
 *
 * 八数码.java
 *
 * Created on 2007年9月29日, 上午11:27
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package text;

import java.io.*;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.StringTokenizer;

 
public class EightNum {
   
    String all=null;
    Node start;
    Node end;
    Node temp;
    Node 扩展结点[] = new Node[10000]; //保存父结点的四个子结点,顺序存储为上，下，左，右，为扩展的临时数组
    int f=0;//扩展结点的下标
    int judge=1;
    Node close[] = new Node[10000];  //扩展结点类
    Node 路径[]=new Node[10000];
   
    int opennum=0;//open表中结点的个数
   
    int closednum =0;//closed表中结点的个数s
    
    EightNum(){
   }
    EightNum(int a1[],int a2[])
    {
        
        
        start = new Node(a1);
     
        end = new Node(a2);
       
    }
    public class Node
    { 
       
        int Num[][] = new int[3][3];
       
       
        Node parent;
        public Node()
        {
         
          ;
        }
        public Node(Node n)
        {
           
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                        Num[i][j]=n.Num[i][j];
          
          
        }
        public Node(int a[])
        {
            int m=0;
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    {
                        Num[i][j]=a[m];
                        m=m+1;
                    }
           
           
           
            //System.out.println("测试4");//测试
        }

        public int[][] 取数值()
        {
            return Num;
        }

        public boolean equal(Node st)//只是数码不相等
        {
            int[][] s = st.取数值();
            int i,j;
            for (i = 0; i < 3; i++)
                for(j = 0 ; j<3 ;j++)
                if (s[i][j] != Num[i][j])
                    return false;
            return true;
        }
       
        public int[] 零点位置()
        {
            int 位置[] = new int[2];
            for(int i=0;i<3;i++)
                for(int j=0;j<3;j++)
                    if(this.Num[i][j]==0)
                        {位置[0]=i;位置[1]=j;}
            return 位置;               
        }
       
    }
   
    public static void printnode (Node h)
    {
        
         char k[]=new char[9];
         
        for(int i=0;i<3;i++)
        {
             System.out.print("             ");
            for(int j=0;j<3;j++)
                {          
                
                 System.out.print("  "+h.Num[i][j]+" "); 
                }
            System.out.println();
        }
         
    }
    public void kuozhan(Node n)
    {
        
      
        Node t = new Node();   
       
        int temp = 0;                 //交换数码的中间变量
        boolean 没找到 = true;
          
                if( n == start)
                {
                    close[opennum]=n;        // （状态位置,结点对象)
                    opennum=opennum+1;
                    closednum=closednum+1;
                 }
                 int[] p= n.零点位置();//知道0的位置                                
                System.out.println("=================待扩展的结点;======================");
                 printnode(n);
              
                // System.out.println("0点位置:"+p[0]+" "+p[1]);
                 if(p[0]==0 && p[1]==0)//如果0点在左上角
                 {                                    
                    //展开(待扩展的结点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时结点数组);
                    //向下扩展
                     if(judge!=0)
                     move(n,1,p,1,0,扩展结点) ; 
                    
                    //向右扩展 
                      if(judge!=0)
                     move(n,3,p,0,1,扩展结点) ;       

                 }
                 else if(p[0] == 0 && p[1] == 1)//如果0点在上中间的话
                 {
                     
                     //向下扩展
                      if(judge!=0)
                      move(n,1,p,1,1,扩展结点);            
                     //向左扩展
                      if(judge!=0)
                      move(n,2,p,0,0,扩展结点);           
                     //向右扩展
                      if(judge!=0)
                     move(n,3,p,0,2,扩展结点) ;        
                 }                
                 else if(p[0] == 0 && p[1] == 2)//如果0点在右上角
                 {
                   
                     //向下扩展
                      if(judge!=0)
                      move(n,1,p,1,2,扩展结点) ;          
                     //向左扩展
                      if(judge!=0)
                      move(n,2,p,0,1,扩展结点) ;                           
                 }
                 else if(p[0] == 1 && p[1] == 0)//如果 点在左边中间
                 {
                    
                     //向上扩展
                      if(judge!=0)
                     move(n,0,p,0,0,扩展结点) ;        
                     //向下扩展
                      if(judge!=0)
                     move(n,1,p,2,0,扩展结点);          
                     //向右扩展
                      if(judge!=0)
                     move(n,3,p,1,1,扩展结点) ;
                   
                 }
                 else if(p[0] == 1 && p[1] == 1)//如果 点在正中间
                 {
                     
                     //向上扩展
                      if(judge!=0)
                     move(n,0,p,0,1,扩展结点);       
                     //向下扩展
                      if(judge!=0)
                     move(n,1,p,2,1,扩展结点)  ;       
                     //向左扩展
                      if(judge!=0)
                     move(n,2,p,1,0,扩展结点) ;         
                     //向右扩展
                      if(judge!=0)
                      move(n,3,p,1,2,扩展结点) ;       
                 }
                 else if(p[0] == 1 && p[1] == 2)//如果 点在右边中间
                 {
                     
                     //向上扩展
                      if(judge!=0)
                      move(n,0,p,0,2,扩展结点);        
                     //向下扩展
                      if(judge!=0)
                      move(n,1,p,2,2,扩展结点) ;       
                     //向左扩展
                      if(judge!=0)
                     move(n,2,p,1,1,扩展结点);
                   
                 }
                 else if(p[0] == 2 && p[1] == 0)//如果 点在左下角
                 {
                   
                     //向上扩展
                      if(judge!=0)
                      move(n,0,p,1,0,扩展结点) ;         
                     //向右扩展
                      if(judge!=0)
                     move(n,3,p,2,1,扩展结点) ;           
                 }
                 else if(p[0] == 2 && p[1] == 1)//如果 点在下边中间
                 {
                    
                     //向上扩展
                      if(judge!=0)
                     move(n,0,p,1,1,扩展结点);             
                     //向左扩展
                      if(judge!=0)
                      move(n,2,p,2,0,扩展结点) ;           
                     //向右扩展
                      if(judge!=0)
                      move(n,3,p,2,2,扩展结点) ;         
                 }
                 else if(p[0] == 2 && p[1] == 2)//如果 点在右下角
                 {
                    
                     //向上扩展
                      if(judge!=0)
                      move(n,0,p,1,2,扩展结点) ;          
                     //向左扩展
                      if(judge!=0)
                      move(n,3,p,2,1,扩展结点) ;      
                 }
                
            
                 
                 
                 
    }
   
    public boolean 存在否(Node n)
    {
        for(int i=0;i<opennum;i++)
        {
            if(close[i].equal(n)) return true;
        }
        return false;
    }
       
    public void move(Node n,int k,int[] z,int q,int p,Node[] 扩展结点) //展开(待扩展的结点,扩展方向,0点位置,方向行坐标,方向纵坐标,扩展临时结点数组)
    {
        
 
        close[opennum]=n;
        /*扩展完结点进入close表*/
        
        opennum++;
       
       
        Node t = new Node(n);  // 用父结点扩展
     
        int flag = 0;
        int temp;
        temp = t.Num[z[0]][z[1]];
        t.Num[z[0]][z[1]] = t.Num[q][p];
        t.Num[q][p] = temp;
     
        
        
        if(!存在否(t))//如果不在close表中（测试此映射表中是否存在与指定值关联的键）
        {    
            String msg="";
        if(k==0){ msg = new String("向上扩展结果");}
        else if(k==1){ msg = new String("向下扩展结果");}
        else if(k==2){ msg = new String("向左扩展结果");}
        else if(k==3){ msg = new String("向右扩展结果");}
        System.out.println(msg);
        printnode(t);//测试
           
            
        
            if(t.equal(end))
            {
                end.parent=n;
                System.out.println("=======恭喜!终于找到目标结点了^-^!!!=======");
                printnode(t);//测试
                closednum = closednum+1;
                System.out.println("扩展的总结点的个数为"+f);
                 f=0;
                 judge=0;
                return ;
            }
            else {               
                扩展结点[f] = t;
                t.parent=n;
                f=f+1;
            }
           // System.out.println("该结点的深度:"+t.深度+"\n该结点的不同与目标结点的个数:"+t.不相同结点个数);
          
           // System.out.println("择优权值:"+r);
            System.out.println();
        }
        return ;
    }
   
   
    public static int 有值的个数(Node m[])
    {
        int n =0;
        for(int i=0;i<m.length;i++)
        {
            if(m[i] != null) n=n+1;
            if(m[i] == null) break;
        }         
        return n;
    }
    
   
}