A*算法求解8数码难题 要求Node类中有getHeuristicValue 方法 生成完整Java代码

以下是Java代码实现A*算法求解8数码难题，其中Node类中包含getHeuristicValue方法：

import java.util.PriorityQueue;
import java.util.HashSet;
import java.util.Set;

public class EightPuzzleSolver {

    private int[][] goalState = {{1,2,3},{4,5,6},{7,8,0}};

    private static class Node implements Comparable<Node> {
        int[][] state; // 当前状态
        int fScore; // f(n)
        int gScore; // g(n)
        int hScore; // h(n)
        Node parent; // 父节点

        public Node(int[][] state, int gScore, int hScore, Node parent) {
            this.state = state;
            this.gScore = gScore;
            this.hScore = hScore;
            this.fScore = gScore + hScore;
            this.parent = parent;
        }
        
        public int getHeuristicValue() {
            int h = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (state[i][j] != goalState[i][j]) {
                        h++;
                    }
                }
            }
            return h;
        }

        @Override
        public int compareTo(Node other) {
            return fScore - other.fScore;
        }

        @Override
        public boolean equals(Object other) {
            if (other instanceof Node) {
                Node o = (Node) other;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (state[i][j] != o.state[i][j]) {
                            return false;
                        }
                    }
                }
                return true;
            }
            return false;
        }

        @Override
        public int hashCode() {
            int hash = 7;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    hash = 31 * hash + state[i][j];
                }
            }
            return hash;
        }
    }

    public int[][] solve(int[][] initialState) {
        Node initialNode = new Node(initialState, 0, getHeuristicValue(initialState), null);
        Set<Node> visited = new HashSet<>();
        PriorityQueue<Node> frontier = new PriorityQueue<>();
        frontier.add(initialNode);

        while (!frontier.isEmpty()) {
            Node current = frontier.poll();
            if (isGoalState(current.state)) {
                return current.state; // 找到解
            }
            visited.add(current);
            for (Node neighbor : getNeighbors(current)) {
                if (!visited.contains(neighbor) && !frontier.contains(neighbor)) {
                    frontier.add(neighbor);
                } else if (frontier.contains(neighbor)) {
                    for (Node n : frontier) {
                        if (n.equals(neighbor) && neighbor.gScore < n.gScore) {
                            frontier.remove(n);
                            frontier.add(neighbor);
                            break;
                        }
                    }
                }
            }
        }
        return null; // 找不到解
    }

    private boolean isGoalState(int[][] state) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (state[i][j] != goalState[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private Set<Node> getNeighbors(Node node) {
        Set<Node> neighbors = new HashSet<>();
        int[][] state = node.state;
        int blankI = -1, blankJ = -1;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (state[i][j] == 0) {
                    blankI = i;
                    blankJ = j;
                    break;
                }
            }
        }
        if (blankI > 0) {
            int[][] newState = copy(state);
            swap(newState, blankI, blankJ, blankI - 1, blankJ);
            neighbors.add(new Node(newState, node.gScore + 1, getHeuristicValue(newState), node));
        }
        if (blankI < 2) {
            int[][] newState = copy(state);
            swap(newState, blankI, blankJ, blankI + 1, blankJ);
            neighbors.add(new Node(newState, node.gScore + 1, getHeuristicValue(newState), node));
        }
        if (blankJ > 0) {
            int[][] newState = copy(state);
            swap(newState, blankI, blankJ, blankI, blankJ - 1);
            neighbors.add(new Node(newState, node.gScore + 1, getHeuristicValue(newState), node));
        }
        if (blankJ < 2) {
            int[][] newState = copy(state);
            swap(newState, blankI, blankJ, blankI, blankJ + 1);
            neighbors.add(new Node(newState, node.gScore + 1, getHeuristicValue(newState), node));
        }
        return neighbors;
    }

    private static int[][] copy(int[][] state) {
        int[][] copy = new int[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                copy[i][j] = state[i][j];
            }
        }
        return copy;
    }

    private static void swap(int[][] state, int i1, int j1, int i2, int j2) {
        int temp = state[i1][j1];
        state[i1][j1] = state[i2][j2];
        state[i2][j2] = temp;
    }

    private int getHeuristicValue(int[][] state) {
        int h = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (state[i][j] != goalState[i][j]) {
                    h++;
                }
            }
        }
        return h;
    }

    public static void main(String[] args) {
        EightPuzzleSolver solver = new EightPuzzleSolver();

        // 测试用例
        int[][] initialState = {{1,2,3},{4,5,6},{7,0,8}};
        int[][] solution = solver.solve(initialState);
        if (solution == null) {
            System.out.println("No solution found.");
        } else {
            System.out.println("Solution found:");
            for (int i = 0; i < 3; i++) {
                System.out.println(solution[i][0] + " " + solution[i][1] + " " + solution[i][2]);
            }
        }
    }

}