八数码问题A*算法提示生成器无限循环问题求助

核心问题及修复方案： #

• Node类未重写equals和hashCode方法
  HashSet判断对象是否存在依赖这两个方法，默认的Object.equals只比较引用地址，导致同一个棋盘状态的不同Node实例会被判定为不同对象，已访问节点无法被正确过滤，最终引发无限循环。
  修复：给Node类重写这两个方法，基于棋盘的内容来计算哈希值和判断相等。

• 曼哈顿距离计算错误
  finalBoard中空格是0，但你的代码里把数字n的目标位置计算为(n-1)/3和(n-1)%3，比如数字1的目标位置会被算成(0,0)，但finalBoard里1在(0,1)，这会导致启发函数失效，A*算法无法向目标方向搜索，进而陷入循环。
  修复：根据finalBoard的实际布局计算每个数字的目标坐标。

• 全局board变量被错误修改
  在Hintgenerate方法中，你执行了board = span.board;，这会把全局的board替换为当前节点的棋盘，后续生成新节点时会基于错误的棋盘操作，导致状态混乱。
  修复：去掉这个赋值，直接使用span.board即可。

• 找到目标后直接return，路径回溯代码未执行
  当isFinal(board)为true时，你设置goal = span;后直接return，导致后面的路径回溯、输出提示的代码完全没运行。
  修复：找到目标后跳出循环，继续执行后续逻辑。

• 路径输出逻辑错误
  你用step.get(1)来输出第一步要移动的数字，这是错误的，反转后的step列表第一个元素就是第一步应该移动的数字，而且当只有一步时step.size()>1会跳过输出。
  修复：改为判断列表非空时取第一个元素。

关键修复代码示例： #

Node类重写equals和hashCode：

class Node {
    int[][] board;
    int coRow, coCol, cost, depth;
    Node parent;

    Node(int[][] b, int x, int y, int d, Node node) {
        this.board = new int[b.length][b.length];
        for (int i = 0; i < b.length; i++) {
            this.board[i] = b[i].clone();
        }
        coRow = x; coCol = y;
        cost = Manhattan(b) + d; depth = d;
        parent = node;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Node node = (Node) o;
        for (int i = 0; i < dimension; i++) {
            for (int j = 0; j < dimension; j++) {
                if (this.board[i][j] != node.board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    @Override
    public int hashCode() {
        StringBuilder sb = new StringBuilder();
        for (int[] row : board) {
            for (int num : row) {
                sb.append(num).append(",");
            }
        }
        return sb.toString().hashCode();
    }
}

修正后的曼哈顿距离方法：

private int Manhattan(int[][] b) {
    int distance = 0;
    for (int i = 0; i < dimension; i++) {
        for (int j = 0; j < dimension; j++) {
            int num = b[i][j];
            if (num == -1) continue;
            int targetRow = 0, targetCol = 0;
            outer:
            for (int x = 0; x < dimension; x++) {
                for (int y = 0; y < dimension; y++) {
                    if (finalBoard[x][y] == num) {
                        targetRow = x;
                        targetCol = y;
                        break outer;
                    }
                }
            }
            distance += Math.abs(targetRow - i) + Math.abs(targetCol - j);
        }
    }
    return distance;
}

修正后的Hintgenerate方法关键部分：

public void Hintgenerate() {
    PriorityQueue<Node> Tree = new PriorityQueue<>(
        Comparator.comparingInt(n -> n.cost)
    );
    HashSet<Node> DeadEnd = new HashSet<>();
    ArrayList<Integer> step = new ArrayList<>();

    int[] negCo = NegCoordinate(-1, board);
    Tree.add(new Node(board, negCo[0], negCo[1], 0, null));

    Node goal = null;

    while (!Tree.isEmpty()) {
        Node span = Tree.poll();

        if (DeadEnd.contains(span)) continue;

        if (isFinal(span.board)) {
            goal = span;
            break;
        }

        DeadEnd.add(span);

        for (int i = 0; i < 4; i++) {
            int nextRow = span.coRow + moveRow[i];
            int nextCol = span.coCol + moveCol[i];
            if (nextCol > -1 && nextCol < dimension && nextRow > -1 && nextRow < dimension) {
                int[][] instBoard = new int[dimension][dimension];
                for (int r = 0; r < dimension; r++) {
                    instBoard[r] = span.board[r].clone();
                }

                instBoard[span.coRow][span.coCol] = instBoard[nextRow][nextCol];
                instBoard[nextRow][nextCol] = -1;

                Node newNode = new Node(instBoard, nextRow, nextCol, span.depth + 1, span);
            
                if (!DeadEnd.contains(newNode)) {
                    Tree.add(newNode);
                }
            }
        }
    }

    if (goal == null) {
        System.out.println("无解");
        return;
    }

    Node cur = goal;
    while (cur.parent != null) {
        step.add(cur.parent.board[cur.coRow][cur.coCol]);
        cur = cur.parent;
    }

    Collections.reverse(step);
    if (!step.isEmpty()) {
        System.out.println("应移动数字：" + step.get(0));
    } else {
        System.out.println("已处于目标状态");
    }
}

内容的提问来源于stack exchange，提问作者wsn