启发式搜索算法a*搜索求解8数码问题 生成Java代码

以下是针对8数码问题的A*搜索算法Java代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;

public class EightPuzzle {

    private final int[][] goal = {{1,2,3},{4,5,6},{7,8,0}};
    private int[][] initial;
    private int dimension;
    private int cost = 0;

    public EightPuzzle(int[][] initial) {
        this.initial = initial.clone();
        dimension = initial.length;
    }

    public int getCost() {
        return cost;
    }

    public void setInitial(int[][] initial) {
        this.initial = initial.clone();
    }

    public boolean isSolvable() {
        int inversions = 0;
        List<Integer> temp = new ArrayList<>();
        for(int i=0;i<dimension;i++) {
            for(int j=0;j<dimension;j++) {
                temp.add(initial[i][j]);
            }
        }
        for(int i=0;i<(dimension*dimension)-1;i++) {
            for(int j=i+1;j<(dimension*dimension);j++) {
                if(temp.get(i)>temp.get(j)) {
                    inversions++;
                }
            }
        }
        return (inversions%2==0);
    }

    private int getHeuristic(int[][] state) {
        int h=0;
        for(int i=0;i<dimension;i++) {
            for(int j=0;j<dimension;j++) {
                if(state[i][j]!=0) {
                    h += Math.abs(i-(state[i][j]-1)/dimension);
                    h += Math.abs(j-(state[i][j]-1)%dimension);
                }
            }
        }
        return h;
    }

    public boolean isGoal(int[][] state) {
        return Arrays.deepEquals(goal, state);
    }

    private boolean isMoveValid(int i, int j) {
        return (i>=0 && j>=0 && i<dimension && j<dimension);
    }

    private int[][] makeMove(int[][] state, int i1,int j1, int i2, int j2) {
        int[][] newState = new int[dimension][dimension];
        for(int i=0;i<dimension;i++) {
            System.arraycopy( state[i], 0, newState[i], 0, dimension );
        }
        newState[i2][j2] = state[i1][j1];
        newState[i1][j1] = state[i2][j2];
        return newState;
    }

    public void solve() {
        if(!isSolvable()) {
            System.out.println("Not solvable");
            return;
        }
        PriorityQueue<PuzzleNode> priorityQueue = new PriorityQueue<>();
        PuzzleNode rootNode = new PuzzleNode(initial, null, 0, getHeuristic(initial));
        priorityQueue.add(rootNode);
        while(!priorityQueue.isEmpty()) {
            PuzzleNode node = priorityQueue.poll();
            cost = node.getCost();
            System.out.println(Arrays.deepToString(node.getState()));
            if(isGoal(node.getState())) {
                break;
            }
            int i=-1, j=-1;
            for(int row=0;row<dimension;row++) {
                for(int col=0;col<dimension;col++) {
                    if(node.getState()[row][col]==0) {
                        i = row;
                        j = col;
                        break;
                    }
                }
            }
            int[][] directions = {{0, -1},{-1, 0},{0, 1},{1, 0}};
            for(int[] direction: directions) {
                int newI = i+direction[0];
                int newJ = j+direction[1];
                if(isMoveValid(newI, newJ)) {
                    int[][] newState = makeMove(node.getState(), newI,newJ, i, j);
                    int newCost = node.getCost()+1;
                    PuzzleNode newNode = new PuzzleNode(newState, node, newCost, getHeuristic(newState));
                    priorityQueue.add(newNode);
                }
            }
        }
    }

    private class PuzzleNode implements Comparable<PuzzleNode>{
        private int[][] state;
        private PuzzleNode parent;
        private int cost;
        private int heuristic;

        public PuzzleNode(int[][] state, PuzzleNode parent, int cost, int heuristic) {
            this.state = state;
            this.parent = parent;
            this.cost = cost;
            this.heuristic = heuristic;
        }

        public int[][] getState() {
            return state;
        }

        public PuzzleNode getParent() {
            return parent;
        }

        public int getCost() {
            return cost;
        }

        public int getHeuristic() {
            return heuristic;
        }

        public int getTotalCost() {
            return cost + heuristic;
        }

        @Override
        public int compareTo(PuzzleNode node) {
            return getTotalCost() - node.getTotalCost();
        }
    }

    public static void main(String[] args) {
        int[][] initial = {{1,2,3},{4,0,6},{7,5,8}};
        EightPuzzle puzzle = new EightPuzzle(initial);
        puzzle.solve();
    }
}