eightdtbfs.java

九宫问题（八数码）的一个小软件

/*
 * EightDTBFS.java
 *
 * Created on February 13, 2006, 10:09 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package org.ray.ninegrid;

import java.util.Hashtable;
import java.util.Vector;
import org.ray.ninegrid.AbstractEightAnalyse.Operation;
import org.ray.ninegrid.AbstractEightAnalyse.Status;

/**
 *
 * @author Ray#
 */
public class EightDTBFS extends AbstractEightAnalyse{
    private Vector<Status> uqueue;
    private Vector<Status> dqueue;
    Status meet;
    private Operation next;
    
    /** Creates a new instance of EightDTBFS */
    private EightDTBFS() {
        hash=new Hashtable<Status,Operation>();
        uqueue=new Vector<Status>();
        dqueue=new Vector<Status>();
    }
    
    private static final EightDTBFS instance=new EightDTBFS();
    
    public static EightDTBFS getInstance(int[] st){
        instance.start=st;
        return instance;
    }
    
    public String search() {
        time=System.currentTimeMillis();
        Runtime.getRuntime().gc();
        mem=Runtime.getRuntime().freeMemory();
        Status a=new Status(start,0);
        Status b=new Status(end,0);
        clear();
        hash.put(a,new Operation('0',true));
        hash.put(b,new Operation('0',false));
        uqueue.add(a);
        dqueue.add(b);
        boolean flag=false;
        Status temp;
        do{
            temp=uqueue.remove(0);
            flag|=expand(temp.value,temp.level,true);
            temp=dqueue.remove(0);
            flag|=expand(temp.value,temp.level,false);
        }while(!flag);
        mem=Math.abs(mem-Runtime.getRuntime().freeMemory());
        oplist=result();
        time=System.currentTimeMillis()-time;
        return oplist;
    }
    
    private boolean expand(int[] status, int curLevel,boolean flag) {
        boolean f=false;
        if(status[9]>3){
            f|=valid(move(status,'u'),curLevel+1,'u',flag);
        }
        if(status[9]<7){
            f|=valid(move(status,'d'),curLevel+1,'d',flag);
        }
        if(status[9]%3!=0){
            f|=valid(move(status,'r'),curLevel+1,'r',flag);
        }
        if(status[9]%3!=1){
            f|=valid(move(status,'l'),curLevel+1,'l',flag);
        }
        return f;
    }
    
    @Override
            protected void valid(int[] s,int n,char o){}
    
    protected boolean valid(int[] nextStatus, int nextLevel, char operation,boolean flag) {
        Status temp=new Status(nextStatus,nextLevel);
        if(!hash.containsKey(temp)){
            hash.put(temp,new Operation(operation,flag));
            if(flag){
                uqueue.add(temp);
            }else{
                dqueue.add(temp);
            }
        }else{
            Operation t=hash.get(temp);
            if(t.flag^flag){
                meet=temp;
                next=new Operation(operation,flag);
                return true;
            }
        }return false;
    }
    
    protected String result() {
        StringBuffer st=new StringBuffer();
        Status a=new Status(start,0);
        Status b=new Status(end,0);
        Status res=meet;
        char op='1';
        if(next.flag){
            op=next.op;
            res=new Status(move(res.value,opposite(op)),0);
        }
        while(op!='0'){
            if(op!='1')
                st.append(op);
            op=hash.get(res).op;
            res=new Status(move(res.value,opposite(op)),0);
        }
        st.reverse();
        res=meet;
        op='1';
        if(!next.flag){
            op=opposite(next.op);
            res=new Status(move(res.value,op),0);
        }
        while(op!='0'){
            if(op!='1')
                st.append(op);
            op=opposite(hash.get(res).op);
            res=new Status(move(res.value,op),0);
        }
        return st.toString();
    }
    
    @Override
            public void clear(){
        super.clear();
        hash.clear();
        uqueue.clear();
        dqueue.clear();
    }
}