test3.java

八数码即九宫图JAVA源代码。希望大家能共享。不是图形样式的

package exercise0;

public class test3 {

	public final static int MAXSIZE = 65535;

	public static void main(String[] args) {
		// long start = System.currentTimeMillis();//开始时间
		long startTime = System.nanoTime();
		// 声明变量
		OneState x, y; // 初始状态x，及目标状态y
		OneState[] Graph; // 搜索树
		SqQueue Open; // 队列
		SqStack Close; // 栈
		Operators Operator; // 操作
		int count1 = 0; // 结点编号
		//int[][] mid1 = { { 2, 8, 3 }, { 1, 0, 4 }, { 7, 6, 5 } };
		//int[][] mid2 = { { 1, 2, 3 }, { 8, 0, 4 }, { 7, 6, 5 } };// 辅助变量
		 int[][] mid1 = { { 6, 7, 8, 9 }, { 5, 0, 1, 10 }, { 4, 3, 2, 11 }, };
		 int[][] mid2 = { { 6, 7, 8, 9 }, { 5, 1, 10, 0 }, { 4, 3, 2, 11 }, };
		// 初始化主要变量
		x = new OneState(mid1);
		y = new OneState(mid2);
		Graph = new OneState[MAXSIZE];
		Open = new SqQueue();
		Close = new SqStack();
		Operator = new Operators();

		// 判断问题是否可解，若可解则进行搜索
		if (!Operator.isRightOrder(x, y)) {
			System.out.println("该问题无解，不能由初始状态经规定操作到达目标状态！");
		} else {
			if (Operator.stateCompare(x, y) == true)
				System.out.println("the start state is the end start");
			else {
				Open.EnQueue(x);
				OneState p, q;
				// 根结点入图
				Graph[++count1] = new OneState(mid1);
				Graph[count1].setParent(0);
				Graph[count1].setLayer(1);
				Graph[count1].setId(1);
				Graph[count1].setOperate(operator.ROOT);
				while (!Open.IsEmpty()) {
					p = new OneState(Open.DeQueue());
					q = new OneState(p);
					// MOVELEFT
					if (Operator.moveLeft(p)) {
						if (Operator.notContain(p, Graph, count1)) {
							p.setParent(p.getId());
							p.setLayer(p.getLayer() + 1);
							p.setId(++count1);
							p.setOperate(operator.LEFT);
							Graph[count1] = p;
							if (Operator.stateCompare(p, y))
								break;
							else
								Open.EnQueue(Graph[count1]);
						}
						p = new OneState(q);
					}
					// MOVERIGHT
					if (Operator.moveRight(p)) {
						if (Operator.notContain(p, Graph, count1)) {
							p.setParent(p.getId());
							p.setLayer(p.getLayer() + 1);
							p.setId(++count1);
							p.setOperate(operator.RIGHT);
							Graph[count1] = p;
							if (Operator.stateCompare(p, y))
								break;
							else
								Open.EnQueue(Graph[count1]);
						}
						p = new OneState(q);
					}
					// MOVEUP
					if (Operator.moveUp(p)) {
						if (Operator.notContain(p, Graph, count1)) {
							p.setParent(p.getId());
							p.setLayer(p.getLayer() + 1);
							p.setId(++count1);
							p.setOperate(operator.UP);
							Graph[count1] = p;
							if (Operator.stateCompare(p, y))
								break;
							else
								Open.EnQueue(Graph[count1]);
						}
						p = new OneState(q);
					}
					// MOVEDOWN
					if (Operator.moveDown(p)) {
						if (Operator.notContain(p, Graph, count1)) {
							p.setParent(p.getId());
							p.setLayer(p.getLayer() + 1);
							p.setId(++count1);
							p.setOperate(operator.DOWN);
							Graph[count1] = p;
							if (Operator.stateCompare(p, y))
								break;
							else
								Open.EnQueue(Graph[count1]);
						}
						p = new OneState(q);
					}
				}// while

				// 判断本方法是否已找到解，若已找到，则输出
				if (Open.IsEmpty())
					System.out.println("本方法没有找到可达路径，请改变搜索长度，或使用其他方法！");
				else {
					for (int i = count1; i > 0;) {
						Close.Push(Graph[i]);
						i = Graph[i].getParent();
					}
					System.out.println("输出八数码问题广度搜索的最优路径如下：\n");
					while (!Close.IsEmpty()) {
						p = Close.PoP();
						p.display();
					}
				}
			}// else1
		}// else0
		// long end = System.currentTimeMillis();// 终止时间
		// System.out.println("Run Time：" + (end - start) + "ms");
		long endTime = System.nanoTime();// 终止时间
		System.out.println("Run Time：" + (endTime - startTime) / 1000000.0
				+ "ms");
	}
}