eight_puzzle.java

八数码问题和舰科技符合时刻记得和反馈记得和反馈及时反馈记得是

package zdg;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Eight_puzzle {
	// 成员变量
	private Status start;
	private Status finish;
	private Status min_cost;
	private ArrayList<Status> closed;// 用来存储已经移动过的最小状态
	private ArrayList<Status> resolution;// 存放求解路径

	public Eight_puzzle(Status start, Status finish) {// 初始化
		this.start = start;
		this.finish = finish;
		this.min_cost = start;
		this.closed = new ArrayList();
		// this.closed.add(start);//
		this.resolution = new ArrayList();
		this.resolution.add(start);
	}
	public void setMinCost(Status status) {
		this.min_cost = status;
	}

	public void setInitStatus(Status status) {
		this.start = status;
	}

	public void setFiniStatus(Status status) {
		this.finish = status;
	}

	public Status getInitStatus() {
		return this.start;
	}

	public Status getFinStatus() {
		return this.finish;
	}
	// 键盘输入并转换
	public static String getString() {
		BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("请输入九个一位数，其中只包含一个零，且不能有重复的数字，每个数字之间用空格隔开");
		String string = null;
		try {
			string = is.readLine();
		} catch (IOException ioe) {
			System.out.println("cuole ");
		}
		return string;
	}

	public static boolean convertStringToArray(String s, int array[]) {
		String result[] = s.split(" ");
		if (result.length > 9)
			System.out.println("您的输入超过了九个数字，位于数字" + result[9] + "之后的数字将被忽略。");
		int newarray[] = new int[9];
		int countOfZero = 0;
		for (int i = 0; i < 9; i++) {

			int j = Integer.parseInt(result[i]);
			if (j > 9 || j < 0) {
				System.out.print("不能输入大于九和小于零的数！");
				return false;
			} else if (j == 0) {
				countOfZero++;
			}
			array[i] = j;
		}
		if (countOfZero != 1) {
			System.out.println("您只能输入一个零。既不能输入多个零，也不能不输入零");
			return false;
		}
		for (int i = 0; i < 9; i++) {
			for (int j = i + 1; j < 9; j++)
				if (array[i] == array[j]) {
					System.out.println("您不能输入重复的数值！");
					return false;
				}
		}
		for (int i = 0; i < 9; i++)
			System.out.print(" " + array[i] + " ");
		return true;

	}

	public static int[][] covertOneToTwo(int a[]) {

		int array[][] = new int[3][3];
		for (int m = 0; m < a.length; m++) {
			array[m / 3][m % 3] = a[m];
		}
		return array;

	}

	// 计算二元数组的逆数值，以判断两个二元数组之间能否转换
	public int computeValue(Status stat) {
		int temp[][] = stat.getStatus().clone();
		int k = 0;
		int count = 0;
		int m = 0;
		int a[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++) {
				a[k++] = temp[i][j];
			}
		while (m < a.length - 1) {
			for (int h = m; h < a.length; h++) {
				if (a[m] == 0 || a[h] == 0) {
					continue;
				} else if (a[m] > a[h]) {
					count++;
				}
			}
			m++;
		}
		return count;
	}

	// 该函数测试初始状态和终止状态之间是不是有解路径
	public boolean isResolve(Status start, Status finish) {
		// 如果两股状态的逆数值相等则存在解路径
		if (computeValue(start) % 2 == computeValue(finish) % 2)
			return true;
		else
			return false;
	}

	// 输入二维数组

	// 判断两个状态是否相等
	public boolean isStateEqual(Status state1, Status state2) {
		boolean bool_temp = false;
		int array_temp1[][] = new int[3][3];
		int array_temp2[][] = new int[3][3];
		for (int i = 0; i < 3; i++) {
			array_temp1[i] = state1.getStatus()[i].clone();
			array_temp2[i] = state2.getStatus()[i].clone();
		}
		// int array_temp1[][]=state1.getStatus().clone();
		// int array_temp2[][]=state2.getStatus().clone();
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (array_temp1[i][j] != array_temp2[i][j])
					return false;
			}
		}

		return true;
	}

	// 判断当前获得的最小代价状态是否是被移动过，是则返回true，否则返回false
	public boolean isMoved(Status state, ArrayList closed) {

		for (int i = 0; i < closed.size(); i++) {
			if (isStateEqual(state, (Status) closed.get(i))) {
				return true;
			}
		}
		return false;

	}

	// 打印解路径
	public void printResolution(ArrayList resolution) {
		for (int i = 0; i < resolution.size(); i++) {

			this.resolution.get(i).printStatus();
			System.out.println();

		}
	}

	public void printClosed(ArrayList closed) {
		for (int i = 0; i < closed.size(); i++) {

			this.closed.get(i).printStatus();
			System.out.println();

		}
	}

	

	// 状态的四向移动，本算法的核心
	// 先将给定的当前对小代价进行四向移动
	// 每次移动都要先判断能否进行相应的移动
	// 然后，除了对初始状态要直接把min_cost设置为初始状态外，其他的移动都要判断移动后的代价和移动前的代价，
	// 如果移动后的代价更小，则再判断移动后的状态是不是已经经过四向移动，如果没有，则将其设置为min_cost，以便进行下次的移动
	// 每次进行四向移动后，都获得一个未曾移动过的最小代价状态，
	// 最后，还要把刚刚移动过的状态分别添加到resolution表和closd表中
	// 其实closed表就是resolution表去掉一个finish状态，为了保持两者一致，我们在主程序循环移动结束后，在closed表中加入finish状态
	public Status moveSelectMinCSost(Status status) {

		// 将status克隆给temp，一下所有的操作均对temp操作，不改变status，以便进行下次移动
		Status temp = new Status();
		temp = status.clone();

		// 设置临时变量存储四向移动后的状态
		Status up;
		Status down;
		Status left;
		Status right;
		if (status.isUp()) {

			up = temp.upMove().clone();
			System.out.println("上移之后的状态为：");
			up.printStatus();
			System.out.println("上移之后的代价为：" + up.getCost(this.finish));
			if (!this.isMoved(up.clone(), this.closed)) {

				this.min_cost = up.clone();// 将上移之后的状态作为当前最小代价的状态存储
			}

			System.out.println("上移后的最小代价状态：");// 打印上以后的最小状态
			this.min_cost.printStatus();
			temp = status.clone();
		}

		if (status.isDown()) {
			down = temp.downMove().clone();
			System.out.println("下移之后的状态为：");
			down.printStatus();
			System.out.println("下移之后的代价为：" + down.getCost(this.finish));
			if (down.getCost(this.finish) < this.min_cost.getCost(this.finish)) {

				System.out.println("isMoved  "
						+ this.isMoved(down.clone(), this.closed));
				if (!this.isMoved(down.clone(), this.closed)) {

					System.out.println("下移后更换了当前的最小状态");
					this.min_cost = down.clone();// 将上移之后的状态作为当前最小代价的状态存储
				}

			}
			System.out.println("下移之后的最小代价状态为:");
			this.min_cost.printStatus();
			temp = status.clone();
		}

		if (status.isLeft()) {
			left = temp.leftMove().clone();
			System.out.println("左移之后的状态为：");
			left.printStatus();
			System.out.println("左移之后的代价为：" + left.getCost(this.finish));
			if (left.getCost(this.finish) < this.min_cost.getCost(this.finish)) {

				if (!this.isMoved(left.clone(), this.closed)) {
					System.out.println("左移后更换了当前的最小状态");
					this.min_cost = left.clone();// 将上移之后的状态作为当前最小代价的状态存储
				}
				this.min_cost = left.clone();
			}
			System.out.println("左移之后最小代价状态为wwww：");
			this.min_cost.printStatus();

			temp = status.clone();
		}

		if (status.isRight()) { // 此处有个不明输出，不知道从哪儿来的

			right = temp.rightMove().clone();
			System.out.println("右移之后的状态为：");
			right.printStatus();
			System.out.println("右移之后的代价为：" + right.getCost(this.finish));
			if (right.getCost(this.finish) < this.min_cost.getCost(this.finish)) {

				if (!this.isMoved(right.clone(), this.closed)) {
					System.out.println("右移后更换了当前的最小状态");
					this.min_cost = right.clone();// 将上移之后的状态作为当前最小代价的状态存储
				}
				this.min_cost = right.clone();
			}
			System.out.println("右移之后最小代价状态为：");
			this.min_cost.printStatus();
			temp = status.clone();
		}
		System.out.println("经过四向移动之后的最小代价状态是：");
		this.min_cost.printStatus();
		System.out.println("当前的最小代价是：" + this.min_cost.getCost(this.finish));
		this.resolution.add(this.min_cost);
		this.closed.add(status);// 将刚移动完的状态放进closed表中
		return this.min_cost;

	}

	public static void main(String args[]) throws CloneNotSupportedException {

		// 设置初始变量

		int array[] = new int[9];
		int[][] start1 = new int[3][3];
		int[][] finish1 = new int[3][3];
		System.out.println();
		System.out.println("请输入初始状态：");
		while (!convertStringToArray(getString(), array)) {
			convertStringToArray(getString(), array);
		}
		start1 = covertOneToTwo(array);
		System.out.println();
		System.out.println("请输入终止状态：");
		while (!convertStringToArray(getString(), array)) {
			convertStringToArray(getString(), array);
		}
		finish1 = covertOneToTwo(array);
		Status start = new Status();
		Status finish = new Status();
		Status resolution_status = new Status();// 存储解路径中的状态以便循环输出
		start.setStatus(start1);// 初始化初始状态和结束状态和相应的cost
		finish.setStatus(finish1);

		// 建立E_P对象并初始化
		Eight_puzzle e_p = new Eight_puzzle(start, finish); // 定义Eight_puzzle对象并初始化其初始、结束、和解路径
		System.out.println("初始状态为:");
		e_p.start.printStatus();
		System.out.println("结束状态为");
		e_p.finish.printStatus();

		// 判断是否有解
		if (e_p.isResolve(e_p.start, e_p.finish))

		{
			System.out.println("该问题可解");

			// 将初始状态设置为当前代价最小的状态，然后对这个状态进行四向移动，并获得新的最小代价状态
			e_p.min_cost = e_p.start.clone();
			while (e_p.min_cost.getCost(e_p.finish) != 0) {
				e_p.min_cost = e_p.moveSelectMinCSost(e_p.min_cost);
				System.out.println("解路径");
				e_p.printResolution(e_p.resolution);
				System.out.println("closed");
				e_p.printClosed(e_p.closed);
			}
			// 其实closed表就是resolution表去掉一个finish状态，为了保持两者一致，我们在主程序循环移动结束后，在closed表中加入finish状态
			//e_p.closed.add(e_p.finish);
		} else
			System.out.println("该问题不可解");
	}

}