java - Infinite execute in A* for 8 puzzle - Stack Overflow

admin管理员组

文章数量:1401615

This is the hint of my 8 puzzle problem (Tells player which tile they should move in this state). I tried to use the current board that the player are playing as an input(2D array) but it always caused an infinite loop. I don't know why because I've already check the recent node with hashSet.

Thank you to anyone that takes the time to help.

class HintGenerator {
    int[][] finalBoard = {
            {0, 1, 2},
            {3, 4, 5},
            {6, 7, 8}
    };
    int dimension;
    int[][] board;
    int[] moveRow = {-1, 1, 0, 0};
    int[] moveCol = {0, 0, -1, 1};
    Grid curGrid;

    HintGenerator(int[][] board, int dimension) {
        this.dimension = dimension;
        DeepCopy(board);
    }

    private void DeepCopy(int[][] board) {
        this.board = new int[dimension][dimension];
        for (int i = 0; i < dimension; i++) {
            this.board[i] = board[i].clone();
        }
    }

    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;
        }

    }

    private int Manhattan(int[][] b) {
        int distance = 0;
        for (int i = 0; i < dimension; i++) {
            for (int j = 0; j < dimension; j++) {
                if (b[i][j] == -1) continue;
                int negRow = (b[i][j] - 1) / 3;
                int negCol = (b[i][j] - 1) % 3;
                distance += Math.abs(negRow - i) + Math.abs(negCol - j);
            }
        }

        return distance;
    }

    private boolean isFinal(int[][] board) {
        for (int i = 0; i < dimension; i++) {
            for (int j = 0; j < dimension; j++) {
                if (board[i][j] != finalBoard[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }

    private int[] NegCoordinate(int target, int[][] b) {
        for (int i = 0; i < dimension; i++) {
            for (int j = 0; j < dimension; j++) {
                if (b[i][j] == -1) {
                    return new int[]{i, j};
                }
            }
        }

        return new int[]{-1, -1};
    }

    public void Hintgenerate() {
        PriorityQueue<Node> Tree = new PriorityQueue<>(
            new Comparator<Node>() {
                @Override
                public int compare(Node n1, Node n2) {
                    return n1.cost - n2.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()) {
            System.out.println("Hello from Tree Spanning");
            Node span = Tree.poll();
            board = span.board;

            if (DeadEnd.contains(span)) continue;

            if (isFinal(board)) {
                goal = span;
                return;
            }

            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] = 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("There is no goal");
            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.size() > 1) System.out.println(step.get(1));
    }
}

本文标签： javaInfinite execute in A* for 8 puzzleStack Overflow