abstracteightanalyse.java

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

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

package org.ray.ninegrid;

import java.util.Hashtable;

/**
 *
 * @author Ray#
 */
public abstract class AbstractEightAnalyse implements EightAnalyse{
    protected long time;
    protected long mem;
    protected String oplist;
    protected Hashtable<Status,Operation> hash;
    protected int[] start;
    public  int[] end={1,2,3,4,5,6,7,8,0,9};
    
    /** Creates a new instance of AbstractEightAnalyse */
    public AbstractEightAnalyse() {
        hash=new Hashtable<Status,Operation>();
    }
    
    public Hashtable<Status, Operation> getTree() {
        return hash;
    }
    
    public long getTraveledNodes() {
        return hash.size();
    }
    
    public long getTimeUsed() {
        return time;
    }
    
    public String getSolve() {
        return oplist;
    }
    
    public long getMemoryUsed() {
        return mem;
    }
    
    public void clear(){
        hash.clear();
        oplist=null;
    }
    
    /**
     * @return true if order is even, false if order is odd.
     */
    public static boolean order(int[] status) {
        boolean is=true;
        for(int i=0;i<9;i++){
            if(status[i]==0)continue;
            for(int j=0;j<i;j++){
                if(status[j]==0)continue;
                if(status[i]>status[j])
                    is=!is;
            }
        }return is;
    }
    
    protected void expand(int[] status, int curLevel) {
        if(status[9]>3){
            valid(move(status,'u'),curLevel+1,'u');
        }
        if(status[9]<7){
            valid(move(status,'d'),curLevel+1,'d');
        }
        if(status[9]%3!=0){
            valid(move(status,'r'),curLevel+1,'r');
        }
        if(status[9]%3!=1){
            valid(move(status,'l'),curLevel+1,'l');
        }
    }
    
    protected abstract void valid(int[] nextStatus, int nextLevel, char operation);
    
    protected static void swap(int[] status,int a,int b){
        int t=status[a];
        status[a]=status[b];
        status[b]=t;
    }
    
    public static int[] move(int[] status, char operation) {
        int[] next = new int[10];
        for(int i=0;i<10;i++)
            next[i]=status[i];
        switch (operation) {
            case 'u':
                swap(next,next[9]-1,next[9]-4);
                next[9]-=3;
                break;
            case 'r':
                swap(next,next[9]-1,next[9]);
                ++next[9];
                break;
            case 'd':
                swap(next,next[9]-1,next[9]+2);
                next[9]+=3;
                break;
            case 'l':
                swap(next,next[9]-1,next[9]-2);
                --next[9];
                break;
        }
        return next;
    }
    
    public static char opposite(char opera){
        switch (opera) {
            case 'u':
                return 'd';
            case 'r':
                return 'l';
            case 'l':
                return 'r';
            case 'd':
                return 'u';
        }
        return '0';
    }
    
    public boolean win(int[] status){
        for(int i=0;i<9;i++){
            if(status[i]!=end[i])return false;
        }
        return true;
    }
    
    protected abstract String result();
    
    public abstract String search();
    
    public static class Operation{
        char op;
        boolean flag;
        Operation(char t,boolean f){
            op=t;
            flag=f;
        }
        Operation(char t){
            op=t;
        }
    }
    
    public static class Status implements Comparable<Status>{
        public int[] value;
        public int level;
        public int man=-1;
        //public int dis=-1;
        
        Status(int[] value,int lev){
            this.value=value;
            level=lev;
        }
        
        public String toString(){
            String a="";
            for(int i=0;i<9;i++)
                a+=i+" ";
            return a;
        }
        
        int manhattan(int[] status) {
            if(man<0){
                int[] tx=new int[8];
                int[] ty=new int[8];
                for(int i=0;i<9;i++){
                    if(value[i]!=0){
                        tx[value[i]-1]=i;
                    }
                    if(status[i]!=0){
                        ty[status[i]-1]=i;
                    }
                }
                int d=0;
                for(int i=0;i<8;i++){
                    d+=Math.abs((tx[i])/3-(ty[i])/3)+Math.abs((tx[i])%3-(ty[i])%3);
                }
                man=d;
            }
            return man;
        }
        
        public int compareTo(Status a) {
            return man-a.man;
        }
        
        @Override
                public int hashCode() {
            int t=0;
            for(int i=0;i<9;i++){
                t*=10;
                t+=value[i];
            }
            return Integer.valueOf(t).hashCode();
        }
        
        @Override
                public boolean equals(Object a){
            if(a instanceof Status){
                Status b=(Status)a;
                for(int i=0;i<10;i++){
                    if(value[i]!=b.value[i])return false;
                }return true;
            }return super.equals(a);
        }
    }
}