puzzle8i.java

用A star

			tempSquare[3][1][1] = tempSquare[3][2][1];
			tempSquare[3][2][1] = 0;
			b = 4;
		}
		else if (row == 1 && col == 2) {
			tempSquare[0][1][2] = tempSquare[0][0][2];
			tempSquare[0][0][2] = 0;
			tempSquare[1][1][2] = tempSquare[1][1][1];
			tempSquare[1][1][1] = 0;
			tempSquare[2][1][2] = tempSquare[2][2][2];
			tempSquare[2][2][2] = 0;
			b = 3;
		}
		else if (row == 2 && col == 0) {
			tempSquare[0][2][0] = tempSquare[0][1][0];
			tempSquare[0][1][0] = 0;
			tempSquare[1][2][0] = tempSquare[1][2][1];
			tempSquare[1][2][1] = 0;
			b = 2;
		}
		else if (row == 2 && col == 1) {
			tempSquare[0][2][1] = tempSquare[0][2][0];
			tempSquare[0][2][0] = 0;
			tempSquare[1][2][1] = tempSquare[1][1][1];
			tempSquare[1][1][1] = 0;
			tempSquare[2][2][1] = tempSquare[2][2][2];
			tempSquare[2][2][2] = 0;
			b = 3;
		}
		else if (row == 2 && col == 2) {
			tempSquare[0][2][2] = tempSquare[0][2][1];
			tempSquare[0][2][1] = 0;
			tempSquare[1][2][2] = tempSquare[1][1][2];
			tempSquare[1][1][2] = 0;
			b = 2;
		}
		return b;
	}

	int heuristic(int[][] square) {
		return ManhattenDistance(square);
	}
	
	int DFSContour(char[][] solution, int fLimit, int m, int[][] board) {
		boolean equal, skip;
		char[] tempSolution = new char[9];	
		int b, count, fCost, i, j, k, l, n, newF, nextF = Infinity;
		int[][][] tempSquare = new int[4][3][3];

		fCost = g + heuristic(board);
		for (i = k = 0; i < 3; i++)
			for (j = 0; j < 3; j++)
				solution[m][k++] = (char) (board[i][j] + '0');
		m++;
		if (m == MaxMoves)
			return Infinity;
		if (fCost > fLimit) {
			flag = 0;
			return fCost;
		}
		if (board[0][0] == 1 && board[0][1] == 2 && board[0][2] == 3 &&
			board[1][0] == 8 && board[1][1] == 0 && board[1][2] == 4 &&
			board[2][0] == 7 && board[2][1] == 6 && board[2][2] == 5) {
			flag = 1;
			moves = m;
			return fCost;
		}
		b = expand(board, tempSquare);
		nodesExpanded += b;
		for (i = 0; i < b; i++) {
			skip = false;
			for (j = m - 1; !skip && j < m; j++) {
				for (k = l = 0; k < 3; k++)
					for (n = 0; n < 3; n++)
						tempSolution[l++] = (char) (tempSquare[i][k][n] + '0');
				equal = tempSolution[0] == solution[j][0];
				for (k = 1; equal && k < 9; k++)
					equal = tempSolution[k] == solution[j][k];
				if (equal)
					skip = true;
			}
			if (!skip) {
				newF = DFSContour(solution, fCost, m, tempSquare[i]);
				if (flag == 1)
					return newF;
				nextF = newF < nextF ? newF : nextF;
			}
		}
		g++;
		return nextF;
	}

	int outOfPlace(int[][] square) {
		int i, j, oop = 0;
		int[][] goal = new int[3][3];
		
		goal[0][0] = 1;
		goal[0][1] = 2;
		goal[0][2] = 3;
		goal[1][0] = 8;
		goal[1][1] = 0;
		goal[1][2] = 4;
		goal[2][0] = 7;
		goal[2][1] = 6;
		goal[2][2] = 5;
		for (i = 0; i < 3; i++)
			for (j = 0; j < 3; j++)
				if (square[i][j] != goal[i][j])
					oop++;
		return oop;
	}

	int ManhattenDistance(int[][] square) {
		// city block or Manhatten distance heuristic
		int md = 0;

		if (square[0][0] == 1)
			md += 0;
		else if (square[0][0] == 2)
			md += 1;
		else if (square[0][0] == 3)
			md += 2;
		else if (square[0][0] == 4)
			md += 3;
		else if (square[0][0] == 5)
			md += 4;
		else if (square[0][0] == 6)
			md += 3;
		else if (square[0][0] == 7)
			md += 2;
		else if (square[0][0] == 8)
			md += 1;
		if (square[0][1] == 1)
			md += 1;
		else if (square[0][1] == 2)
			md += 0;
		else if (square[0][1] == 3)
			md += 1;
		else if (square[0][1] == 4)
			md += 2;
		else if (square[0][1] == 5)
			md += 3;
		else if (square[0][1] == 6)
			md += 2;
		else if (square[0][1] == 7)
			md += 3;
		else if (square[0][1] == 8)
			md += 2;
		if (square[0][2] == 1)
			md += 2;
		else if (square[0][2] == 2)
			md += 1;
		else if (square[0][2] == 3)
			md += 0;
		else if (square[0][2] == 4)
			md += 1;
		else if (square[0][2] == 5)
			md += 2;
		else if (square[0][2] == 6)
			md += 3;
		else if (square[0][2] == 7)
			md += 4;
		else if (square[0][2] == 8)
			md += 3;
		if (square[1][0] == 1)
			md += 1;
		else if (square[1][0] == 2)
			md += 2;
		else if (square[1][0] == 3)
			md += 3;
		else if (square[1][0] == 4)
			md += 2;
		else if (square[1][0] == 5)
			md += 3;
		else if (square[1][0] == 6)
			md += 2;
		else if (square[1][0] == 7)
			md += 1;
		else if (square[1][0] == 8)
			md += 0;
		if (square[1][1] == 1)
			md += 2;
		else if (square[1][1] == 2)
			md += 1;
		else if (square[1][1] == 3)
			md += 2;
		else if (square[1][1] == 4)
			md += 1;
		else if (square[1][1] == 5)
			md += 2;
		else if (square[1][1] == 6)
			md += 1;
		else if (square[1][1] == 7)
			md += 2;
		else if (square[1][1] == 8)
			md += 1;
		if (square[1][2] == 1)
			md += 3;
		else if (square[1][2] == 2)
			md += 2;
		else if (square[1][2] == 3)
			md += 1;
		else if (square[1][2] == 4)
			md += 0;
		else if (square[1][2] == 5)
			md += 1;
		else if (square[1][2] == 6)
			md += 2;
		else if (square[1][2] == 7)
			md += 3;
		else if (square[1][2] == 8)
			md += 2;
		if (square[2][0] == 1)
			md += 2;
		else if (square[2][0] == 2)
			md += 3;
		else if (square[2][0] == 3)
			md += 4;
		else if (square[2][0] == 4)
			md += 3;
		else if (square[2][0] == 5)
			md += 2;
		else if (square[2][0] == 6)
			md += 1;
		else if (square[2][0] == 7)
			md += 0;
		else if (square[2][0] == 8)
			md += 1;
		if (square[2][1] == 1)
			md += 3;
		else if (square[2][1] == 2)
			md += 2;
		else if (square[2][1] == 3)
			md += 3;
		else if (square[2][1] == 4)
			md += 2;
		else if (square[2][1] == 5)
			md += 1;
		else if (square[2][1] == 6)
			md += 0;
		else if (square[2][1] == 7)
			md += 1;
		else if (square[2][1] == 8)
			md += 2;
		if (square[2][2] == 1)
			md += 4;
		else if (square[2][2] == 2)
			md += 3;
		else if (square[2][2] == 3)
			md += 2;
		else if (square[2][2] == 4)
			md += 1;
		else if (square[2][2] == 5)
			md += 0;
		else if (square[2][2] == 6)
			md += 1;
		else if (square[2][2] == 7)
			md += 2;
		else if (square[2][2] == 8)
			md += 3;
		return md;
	}

	boolean solve(char[][] solution) {
		boolean found;
		int fCost, i, j, k, m = 0;
		
		fCost = DFSContour(solution, Infinity, 0, board);
		if (flag == 1)
			return true;
		else if (fCost == Infinity)
			return false;
		return false;
	}

	int getMoves() {
		return moves;
	}
}

class Puzzle8I implements Runnable {
	char[][] solution = null;
	int moves;
	PuzzleI puzzleI = null;

	public Puzzle8I () {
		solution = new char[PuzzleI.MaxMoves][9];
		do
			puzzleI = new PuzzleI();
		while (!puzzleI.solve(solution));
	}

	public void run() {
		Puzzle8IFrame puzzle8IFrame = new Puzzle8IFrame(solution[0]);
		
		moves = puzzleI.getMoves() - 1;
		System.out.println("moves = " + moves);
		for (int i = 1; i < moves + 1; i++) {
			while (!puzzle8IFrame.getNext())
				Thread.yield();
			puzzle8IFrame.setNext(false);
			puzzle8IFrame.draw(solution[i]);
		}
	}

	public static void main(String[] arg) {
		(new Puzzle8I()).run();
	}
}