用Java编写：用A*算法实现八数码难题(九宫重排)的搜索。

好的，以下是使用Java编写的A*算法实现八数码难题的搜索的示例代码：

import java.util.*;

public class EightPuzzleSolver {

    // 表示八数码难题的矩阵
    private int[][] board;

    // 初始状态
    private int[][] initialBoard = {
            {2, 8, 3},
            {1, 6, 4},
            {7, 0, 5}
    };

    // 目标状态
    private int[][] targetBoard = {
            {1, 2, 3},
            {8, 0, 4},
            {7, 6, 5}
    };

    // 启发函数类型
    private static final int MANHATTAN_DISTANCE = 1;
    private static final int MISPLACED_TILES = 2;

    // 启发函数类型，默认为曼哈顿距离
    private int heuristicType = MANHATTAN_DISTANCE;

    // 构造函数
    public EightPuzzleSolver() {
        this.board = initialBoard;
    }

    // 构造函数
    public EightPuzzleSolver(int[][] board) {
        this.board = board;
    }

    // 设置启发函数类型
    public void setHeuristicType(int type) {
        this.heuristicType = type;
    }

    // 获取启发函数类型
    public int getHeuristicType() {
        return heuristicType;
    }

    // 获取当前状态的深度
    private int getDepth(int[][] board) {
        int depth = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] != 0) {
                    depth++;
                }
            }
        }
        return depth;
    }

    // 计算曼哈顿距离
    private int calculateManhattanDistance(int[][] board) {
        int distance = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] != 0) {
                    int row = (board[i][j] - 1) / 3;
                    int col = (board[i][j] - 1) % 3;
                    distance += Math.abs(row - i) + Math.abs(col - j);
                }
            }
        }
        return distance;
    }

    // 计算错位数
    private int calculateMisplacedTiles(int[][] board) {
        int count = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] != 0 && board[i][j] != targetBoard[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }

    // 计算启发函数值
    private int calculateHeuristicValue(int[][] board) {
        switch (heuristicType) {
            case MANHATTAN_DISTANCE:
                return calculateManhattanDistance(board);
            case MISPLACED_TILES:
                return calculateMisplacedTiles(board);
            default:
                return 0;
        }
    }

    // 判断当前状态是否为目标状态
    private boolean isGoalState(int[][] board) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] != targetBoard[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    // 交换两个位置的值
    private void swap(int[][] board, int row1, int col1, int row2, int col2) {
        int temp = board[row1][col1];
        board[row1][col1] = board[row2][col2];
        board[row2][col2] = temp;
    }

    // 生成后继状态
    private List<int[][]> generateSuccessors(int[][] board) {
        List<int[][]> successors = new ArrayList<>();
        int row = -1, col = -1;
        // 找到空格的位置
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == 0) {
                    row = i;
                    col = j;
                    break;
                }
            }
        }
        // 向上移动空格
        if (row > 0) {
            int[][] successor = new int[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    successor[i][j] = board[i][j];
                }
            }
            swap(successor, row, col, row - 1, col);
            successors.add(successor);
        }
        // 向下移动空格
        if (row < 2) {
            int[][] successor = new int[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    successor[i][j] = board[i][j];
                }
            }
            swap(successor, row, col, row + 1, col);
            successors.add(successor);
        }
        // 向左移动空格
        if (col > 0) {
            int[][] successor = new int[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    successor[i][j] = board[i][j];
                }
            }
            swap(successor, row, col, row, col - 1);
            successors.add(successor);
        }
        // 向右移动空格
        if (col < 2) {
            int[][] successor = new int[3][3];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    successor[i][j] = board[i][j];
                }
            }
            swap(successor, row, col, row, col + 1);
            successors.add(successor);
        }
        return successors;
    }

    // A*算法求解八数码难题
    public List<int[][]> solve() {
        // 初始化priority queue
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 将初始状态加入priority queue
        pq.add(new Node(board, null, 0, calculateHeuristicValue(board)));
        // 初始化visited set
        Set<String> visited = new HashSet<>();
        visited.add(Arrays.deepToString(board));
        // 进行搜索
        while (!pq.isEmpty()) {
            // 取出f(n)最小的状态
            Node node = pq.poll();
            // 判断是否为目标状态
            if (isGoalState(node.board)) {
                // 构造路径
                List<int[][]> path = new ArrayList<>();
                while (node.parent != null) {
                    path.add(node.board);
                    node = node.parent;
                }
                path.add(node.board);
                Collections.reverse(path);
                return path;
            }
            // 生成后继状态
            List<int[][]> successors = generateSuccessors(node.board);
            for (int[][] successor : successors) {
                // 判断后继状态是否已经访问过
                if (!visited.contains(Arrays.deepToString(successor))) {
                    // 计算g(n)和h(n)
                    int g = node.g + 1;
                    int h = calculateHeuristicValue(successor);
                    // 加入priority queue
                    pq.add(new Node(successor, node, g, h));
                    // 标记为已访问
                    visited.add(Arrays.deepToString(successor));
                }
            }
        }
        // 无解
        return null;
    }

    // 内部类，表示搜索树中的一个节点
    private class Node implements Comparable<Node> {
        int[][] board;  // 状态矩阵
        Node parent;    // 父节点
        int g;          // 从初始状态到达当前状态的代价
        int h;          // 从当前状态到达目标状态的估算代价

        public Node(int[][] board, Node parent, int g, int h) {
            this.board = board;
            this.parent = parent;
            this.g = g;
            this.h = h;
        }

        // 比较两个节点的f(n)值
        public int compareTo(Node other) {
            return (g + h) - (other.g + other.h);
        }
    }

    // 测试
    public static void main(String[] args) {
        EightPuzzleSolver solver = new EightPuzzleSolver();
        solver.setHeuristicType(MANHATTAN_DISTANCE);
        List<int[][]> path = solver.solve();
        if (path != null) {
            for (int[][] board : path) {
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        System.out.print(board[i][j] + " ");
                    }
                    System.out.println();
                }
                System.out.println();
            }
        } else {
            System.out.println("No solution found!");
        }
    }
}

在上面的代码中，我们定义了一个`EightPuzzleSolver`类，表示八数码难题的求解器。在构造函数中，我们可以指定初始状态，如果不指定，则默认为：

2 8 3 
1 6 4 
7 0 5 

我们还可以使用`setHeuristicType`方法来设置启发函数类型（曼哈顿距离或错位数），默认为曼哈顿距离。

在`solve`方法中，我们实现了A*算法的框架，包括初始化priority queue和visited set，取出f(n)最小的状态，判断是否为目标状态，生成后继状态，计算g(n)和h(n)，加入priority queue和visited set等操作。

在`generateSuccessors`方法中，我们实现了生成后继状态的函数，具体实现方式为向上、下、左、右四个方向移动空格，生成四个后继状态。

在`Node`类中，我们定义了搜索树中的一个节点，表示一个状态，其中包括状态矩阵、父节点、从初始状态到达当前状态的代价和从当前状态到达目标状态的估算代价。我们还实现了`compareTo`方法，用于比较两个节点的f(n)值，以便在priority queue中进行排序。

最后，在`main`方法中，我们创建了一个`EightPuzzleSolver`对象，设置了启发函数类型为曼哈顿距离，并调用`solve`方法求解八数码难题。如果求解成功，则输出求解路径，否则输出"No solution found!"。