8数码问题 java 广度优先探索

以下是Java中使用广度优先搜索算法解决8数码问题的示例代码：

import java.util.*;

public class EightPuzzleBFS {
    private static final int[][] GOAL = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
    private static final int[] dx = {-1, 0, 1, 0};
    private static final int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        int[][] start = {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}};
        EightPuzzleBFS solver = new EightPuzzleBFS();
        List<int[][]> path = solver.solve(start);
        if (path == null) {
            System.out.println("No solution.");
        } else {
            for (int[][] board : path) {
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        System.out.print(board[i][j] + " ");
                    }
                    System.out.println();
                }
                System.out.println();
            }
        }
    }

    public List<int[][]> solve(int[][] start) {
        Map<String, Integer> dist = new HashMap<>();
        Map<String, int[][]> prev = new HashMap<>();
        Queue<int[][]> queue = new LinkedList<>();
        String startStr = toString(start);
        dist.put(startStr, 0);
        prev.put(startStr, null);
        queue.offer(start);
        while (!queue.isEmpty()) {
            int[][] curr = queue.poll();
            if (isGoal(curr)) {
                return buildPath(curr, prev);
            }
            int[] pos = findZero(curr);
            for (int i = 0; i < 4; i++) {
                int nx = pos[0] + dx[i];
                int ny = pos[1] + dy[i];
                if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                    int[][] next = clone(curr);
                    swap(next, pos[0], pos[1], nx, ny);
                    String nextStr = toString(next);
                    if (!dist.containsKey(nextStr)) {
                        dist.put(nextStr, dist.get(toString(curr)) + 1);
                        prev.put(nextStr, curr);
                        queue.offer(next);
                    }
                }
            }
        }
        return null;
    }

    private boolean isGoal(int[][] board) {
        return Arrays.deepEquals(board, GOAL);
    }

    private int[] findZero(int[][] board) {
        int[] pos = new int[2];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == 0) {
                    pos[0] = i;
                    pos[1] = j;
                    return pos;
                }
            }
        }
        return null;
    }

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

    private void swap(int[][] board, int x1, int y1, int x2, int y2) {
        int temp = board[x1][y1];
        board[x1][y1] = board[x2][y2];
        board[x2][y2] = temp;
    }

    private String toString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }

    private List<int[][]> buildPath(int[][] end, Map<String, int[][]> prev) {
        List<int[][]> path = new ArrayList<>();
        path.add(end);
        while (prev.get(toString(end)) != null) {
            end = prev.get(toString(end));
            path.add(0, end);
        }
        return path;
    }
}