eightfigure.java

使用java重新解决八数码问题

//执行算法类
import java.io.*;
import java.util.Timer;

public class EightFigure {
	static int TARGET[][] = {{1,2,3},{8,0,4},{7,6,5}};
	static void mySwap(EightData e,int i,int j,int m,int n) {
		int temp = e.state[i][j];
		e.state[i][j] = e.state[m][n];
		e.state[m][n] = temp;
	}
	
	static EightQueue generateSon(EightData e) {
		EightQueue son = new EightQueue();
		for(int i= 0;i<3;i++)
			for(int j=0;j<3;j++) {
				if(e.state[i][j] == 0) {
					e.curXorZero = i;
					e.curYofZero = j;				}
			}
		if(e.curXorZero > 0) {
			if(e.curXorZero-1 != e.preXofZero) {
				mySwap(e,e.curXorZero-1,e.curYofZero,e.curXorZero,e.curYofZero);
				
				EightData son1 = new EightData(e);
				son1.preXofZero = e.curXorZero;
				son1.preYofZero = e.curYofZero;
				son1.former = e;
				//e.latter = son1;
				son.push(son1);
				mySwap(e,e.curXorZero-1,e.curYofZero,e.curXorZero,e.curYofZero);
			}
		}
		if(e.curXorZero < 2) {
			if(e.curXorZero+1 != e.preXofZero) {
				mySwap(e,e.curXorZero+1,e.curYofZero,e.curXorZero,e.curYofZero);
				
				EightData son2 = new EightData(e);
				son2.preXofZero = e.curXorZero;
				son2.preYofZero = e.curYofZero;
				son2.former = e;
				//e.latter = son2;
				son.push(son2);
				mySwap(e,e.curXorZero+1,e.curYofZero,e.curXorZero,e.curYofZero);
			}
		}
		if(e.curYofZero > 0) { 
			if(e.curYofZero-1 != e.preYofZero) {
				mySwap(e,e.curXorZero,e.curYofZero-1,e.curXorZero,e.curYofZero);
				
				EightData son3 = new EightData(e);
				son3.preXofZero = e.curXorZero;
				son3.preYofZero = e.curYofZero;
				son3.former = e;
				//e.latter = son3;
				son.push(son3);
				mySwap(e,e.curXorZero,e.curYofZero-1,e.curXorZero,e.curYofZero);
			}
		}
		if(e.curYofZero < 2) {
			if(e.curYofZero+1 != e.preYofZero) {
				mySwap(e,e.curXorZero,e.curYofZero+1,e.curXorZero,e.curYofZero);
				
				EightData son4 = new EightData(e);
				son4.preXofZero = e.curXorZero;
				son4.preYofZero = e.curYofZero;
				son4.former = e;
				//e.latter = son4;
				son.push(son4);
				mySwap(e,e.curXorZero,e.curYofZero+1,e.curXorZero,e.curYofZero);
			}
		}
		return son;
	}
	
	static int difference(EightData e) {
		int sum = 0;
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++) {
				//if(e.state[i][j] != TARGET[i][j])
					//sum++;
				switch(e.state[i][j]){
				case 0:
					sum += Math.abs(i-1) + Math.abs(j-1);
					break;
				case 1:
					sum += Math.abs(i) + Math.abs(j);
					break;
				case 2:
					sum += Math.abs(i) + Math.abs(j-1);
					break;
				case 3:
					sum += Math.abs(i) + Math.abs(j-2);
					break;
				case 4:
					sum += Math.abs(i-1) + Math.abs(j-2);
					break;
				case 5:
					sum += Math.abs(i-2) + Math.abs(j-2);
					break;
				case 6:
					sum += Math.abs(i-2) + Math.abs(j-1);
					break;
				case 7:
					sum += Math.abs(i-2) + Math.abs(j);
					break;
				case 8:
					sum += Math.abs(i-1) + Math.abs(j);
					break;
				default:
					break;
				}
			}
		return sum;
	}
	
	public static void main(String args[]) throws IOException{
		EightData eD = new EightData();
		EightData t1 = new EightData();
		EightData t2 = new EightData();
		EightQueue open = new EightQueue();
		EightQueue closed = new EightQueue();
		EightQueue sonGenerated = new EightQueue();	
		boolean solvedOrNot = true;

		String fileName = null;
        System.out.println("Please input the filename:");
        BufferedReader buf;
        buf = new BufferedReader(new InputStreamReader(System.in));
        try {
            fileName = buf.readLine();
        } 
        catch (IOException e) {
            System.out.println("Filename input error!");
            System.exit(0);
        }

        EightFileRead newFile = new EightFileRead(fileName); 

        for(int i=0;i<3;i++)
        	for(int j=0;j<3;j++) {
        		eD.state[i][j] = newFile.readFileNum();
        	}
		newFile.close();
		open.push(eD);
		
		System.out.println(new java.util.Date() + "        任务开始");   
		
		int toCheck[] = {0,0,0,0,0,0,0,0};
		int index = 0,sumOfReverse = 0;
		for(int i=0;i<3;i++)
			for(int j=0;j<3;j++) {
				if(eD.state[i][j]==0)
					continue;
				else {
					toCheck[index] = eD.state[i][j];
					index++;
				}
			}
		for(int i=0;i<8;i++)
			for(int j=i+1;j<8;j++) {
				if(toCheck[i]>toCheck[j])
					sumOfReverse++;
			}
		
		if(sumOfReverse%2==0) {
			System.out.println("No solution(s)!");
			System.out.println(new java.util.Date() + "        任务结束");
			solvedOrNot = false;
		}
		
		int depth = 0;  //搜索深度
		
		while(!open.isEmpty() && solvedOrNot) {
			eD = open.getAt(0);
			open.removeAt(0);
			if(difference(eD) == 0) {
				eD.displayResult(eD);
				System.out.println(new java.util.Date() + "        任务结束");
				solvedOrNot = true;
				return ;
			}
			sonGenerated = generateSon(eD);
			depth++;
			if(sonGenerated.getSize() != 0) {
				for(int i=0;i<sonGenerated.getSize();i++) {
					t1 = sonGenerated.getAt(i);
					t1.f = depth + difference(t1);
					if(!open.existOrNot(t1) && !closed.existOrNot(t1)) {
						open.push(t1);
					}
					else if(open.existOrNot(t1)) {
						int pos = open.getIndex(sonGenerated.getAt(i));
						t2 = open.getAt(pos);
						if(t1.f < t2.f) {
							open.setAt(t1, pos);
						}
					}
					else if(closed.existOrNot(t1)) {
						int pos = closed.getIndex(t1);
						t2 = closed.getAt(pos);
						if(t1.f < t2.f) {
							closed.remove(sonGenerated.getAt(i));
							open.push(t1);
						}
					}
				}
			}
			closed.push(eD);
			// 给open排序
			/*
			for(int i=1;i<open.getSize();i++)
				for(int j=0;j<i;j++) {
					if(open.getAt(j).f > open.getAt(j+1).f) {
						EightData temp = new EightData();
						temp = open.getAt(j);
						open.setAt(open.getAt(j+1), j);
						open.setAt(temp, j+1);
					}
				}
				*/
			EightData temp = new EightData(open.getAt(0));
			int pos = 0;
			for(int i=1;i<open.getSize();i++) {
				if(open.getAt(i).f < temp.f) {
					temp = open.getAt(i);
					pos = i;
				}
			}
			open.setAt(open.getAt(0), pos);	
			open.setAt(temp, 0);
		}		
	}
}