上学期用广搜和字符串写的，作为学习Java的一个练手，感觉很多地方还可以优化，之后看有没有空吧，再改改。

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class EightNumberProblem {
    //初始空格位置
    static int xs;
    static int ys;

    //集合、队列
    static Set<String> s = new HashSet<>();
    static Queue<Node> q = new LinkedBlockingQueue<>();

    //下、右、上、左
    static int[] dx = {0, 1, 0, -1};
    static int[] dy = {1, 0, -1, 0};

    //节点
    static class Node {
        public int first;
        public int second;
        public String[] map;
        public Node fmap;

        //构造方法
        public Node(int x, int y, String[] map, Node fmap) {
            this.first = x;
            this.second = y;
            this.map = map.clone();
            this.fmap = fmap;
        }
    }

    //判断边界
    static boolean pd(int x, int y) {
        if (x < 0) {
            return false;
        } else if (x > 2) {
            return false;
        } else if (y < 0) {
            return false;
        } else if (y > 2) {
            return false;
        } else {
            return true;
        }
    }

    //广度优先算法
    static void BFS(String[] start, String[] end) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (start[i].charAt(j) == '#') {
                    xs = i;
                    ys = j;
                    Node node = new Node(xs, ys, start, null);
                    q.add(node);
                    s.add(Arrays.toString(start));
                }
            }
        }

        while (q.size() != 0) {
            Node tempNode = q.poll();
            if (Arrays.equals(tempNode.map, end)) {
                printResult(tempNode);
                return;
            }
            for (int i = 0; i < 4; i++) {
                int x = tempNode.first + dx[i];
                int y = tempNode.second + dy[i];
                if (pd(x, y)) {
                    String[] temp = tempNode.map.clone();
                    char c = temp[x].charAt(y);
                    StringBuilder sb1 = new StringBuilder(temp[x]);
                    sb1.setCharAt(y, '#');
                    temp[x] = sb1.toString();
                    StringBuilder sb2 = new StringBuilder(temp[tempNode.first]);
                    sb2.setCharAt(tempNode.second, c);
                    temp[tempNode.first] = sb2.toString();
                    if (!s.contains(Arrays.toString(temp))) {
                        Node node = new Node(x, y, temp, tempNode);
                        q.add(node);
                        s.add(Arrays.toString(temp));
                    }
                }
            }
        }
        System.out.println("无解！");
    }

    //打印结果
    static void printResult(Node node) {
        if (node == null) {
            return;
        }
        printResult(node.fmap);
        for (int i = 0; i < 3; i++) {
            System.out.println(node.map[i]);
        }
        System.out.println();
    }

    //main方法
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] start = new String[3];
        System.out.println("初始状态：");
        for (int i = 0; i < 3; i++) {
            start[i] = sc.next();
        }
        String[] end = new String[3];
        System.out.println("目标状态：");
        for (int i = 0; i < 3; i++) {
            end[i] = sc.next();
        }
        System.out.println();
        BFS(start, end);
    }
}

输入和输出的格式如下：

/*
初始状态：
123
456
78#

目标状态：
123
#46
758

答案：
123
456
78#

123
456
7#8

123
4#6
758

123
#46
758
*/