八数码问题a*算法java

以下是使用A*算法解决八数码问题的Java代码示例：

import java.util.*;

public class EightPuzzle {
    private static final int[][] GOAL = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}}; // 目标状态
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
    private static final int N = 3; // 棋盘大小
    private static final int MAX_STATE = 1000000; // 最大状态数

    private static int[][] start = new int[N][N]; // 起始状态
    private static int[][] dist = new int[MAX_STATE][N]; // 到达每个状态的步数
    private static int[][] pre = new int[MAX_STATE][N]; // 记录每个状态的前驱状态
    private static int[][] vis = new int[MAX_STATE][N]; // 标记每个状态是否已经访问过
    private static int[] pos = new int[9]; // 记录每个数字所在的位置

    private static int getH(int[][] a) { // 计算估价函数h
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (a[i][j] == 0) continue;
                res += Math.abs(i - (a[i][j] - 1) / N) + Math.abs(j - (a[i][j] - 1) % N);
            }
        }
        return res;
    }

    private static int getId(int[][] a) { // 将状态转化为整数
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res = res * 10 + a[i][j];
            }
        }
        return res;
    }

    private static void printAns(int id) { // 输出解答
        if (id == -1) return;
        printAns(pre[id][0]);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(start[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                start[i][j] = sc.nextInt();
                pos[start[i][j]] = i * N + j;
            }
        }
        int startId = getId(start);
        int goalId = getId(GOAL);
        if ((getH(start) & 1) != (getH(GOAL) & 1)) { // 判断是否有解
            System.out.println("No solution!");
            return;
        }
        int hh = 0, tt = 0;
        int[] q = new int[MAX_STATE];
        Arrays.fill(dist, -1);
        Arrays.fill(vis, 0);
        dist[startId][0] = 0;
        vis[startId][0] = 1;
        q[0] = startId;
        while (hh <= tt) {
            int[][] cur = new int[N][N];
            int t = q[hh++];
            for (int i = N - 1; i >= 0; i--) {
                for (int j = N - 1; j >= 0; j--) {
                    cur[i][j] = t % 10;
                    t /= 10;
                }
            }
            if (getId(cur) == goalId) { // 到达目标状态
                System.out.println("Steps: " + dist[goalId][0]);
                printAns(goalId);
                return;
            }
            int x = pos[0] / N, y = pos[0] % N;
            for (int i = 0; i < 4; i++) { // 扩展状态
                int nx = x + DIRS[i][0], ny = y + DIRS[i][1];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                int[][] nxt = new int[N][N];
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < N; k++) {
                        nxt[j][k] = cur[j][k];
                    }
                }
                nxt[x][y] = nxt[nx][ny];
                nxt[nx][ny] = 0;
                int nxtId = getId(nxt);
                if (vis[nxtId][0] == 0) { // 新状态
                    vis[nxtId][0] = 1;
                    dist[nxtId][0] = dist[getId(cur)][0] + 1;
                    pre[nxtId][0] = getId(cur);
                    q[++tt] = nxtId;
                }
            }
        }
        System.out.println("No solution!"); // 无解
    }
}