回溯

回溯法，可理解为试探性搜索方法，在搜索到某一步的时候，如果发现不能满足条件，那么就退回到上一步，在上一步重新选择。它本质上是对暴力解法的一种优化，一种尝试失败则提前剪枝的算法。

回溯法是以深度优先方式来搜索问题的解，里面的每一步可以理解为一个结点，这些步骤串起来就是一棵树，也就是解空间树。

当搜索解空间树中的任何一个结点的时候，判断该结点是不是包含问题的解：

• 如果不包含，那么就把当前的结点以及剩下的节点步骤全部抛弃（也称为剪枝），然后往上一层的结点回溯，也就是退回上一步重新选择（之前的选择走不通）。

• 如果包含，说明当前结点是可能获取到解的，继续进入下一层子树进行深度优先搜索。

一般回溯法有两种做法：递归和递推，递归的设计思路简单但效率不高，递推的算法设计较复杂，但效率高。

八皇后问题

八皇后问题是要在8x8的国际象棋棋盘上放置八个皇后，使得它们互不攻击，即任何两个皇后都不能在同一行、同一列，或者同一斜线上，问一共有多少种摆法。

通常使用回溯法解决，步骤如下：

1. 按行放置，从第 0 行开始逐行放置皇后。

2. 尝试在该行的每一列放置皇后，检查是否符合规则：

   1. 是否与已有的皇后在同一列

   2. 是否在同一条对角线上

3. 如果满足要求，则递归处理下一行。

4. 如果当前行没有合法的放置方案，则回溯到上一行，尝试改变上一行皇后的位置。

代码实现如下：

public class Nqueens {
    public static void main(String[] args) {
        int n = 4;
        int[][] maps = new int[n][n];
        find_origin(maps, 0);
        find(n);
    }

    // 未优化的二维数组版回溯
    public static void find_origin(int[][] maps, int row) {
        // 所有行都放置完毕，找到一个解
        if(row == maps.length) {
            printMaps(maps);
            return;
        }
        // 对当前行，尝试每一列
        for(int col = 0; col < maps.length; col++) {
            // 验证是否可以放置
            if(isValid(maps, row, col)) {
                maps[row][col] = 1; // 放置
                find_origin(maps, row + 1); // 下一行递归
                maps[row][col] = 0; // 回溯
            }
        }
    }

    public static void printMaps(int[][] maps) {
        System.out.println(Arrays.deepToString(maps));
    }

    private static boolean isValid(int[][] maps, int row, int col) {
        // 对前面行检查
        for(int i = 0; i < row; i++) {
            // 是否列冲突
            if(maps[i][col] == 1)
                return false;
            // 行差
            int diff = row - i;
            // 斜线上元素的行差等于列差绝对值
            if(col - diff >= 0 && maps[i][col - diff] == 1) // 左上角斜线
                return false;
            if(col + diff < maps.length && maps[i][col + diff] == 1) // 右上角斜线
                return false;
        }
        return true;
    }

    // 优化后的一维数组版
    public static void find(int n) {
        int[] board = new int[n];
        Arrays.fill(board, -1); // 初始填充为 -1
        backtrack(board, 0);
    }

    public static void backtrack(int[] board, int row) {
        if(row == board.length) {
            System.out.println(Arrays.toString(board));
            return;
        }
        for(int col = 0; col < board.length; col++) {
            if(isSafe(board, row, col)) {
                board[row] = col;
                backtrack(board, row + 1);
                board[row] = -1;
            }
        }
    }

    private static boolean isSafe(int[] board, int row, int col) {
        for(int i = 0; i < row; i++) {
            // 是否位于同一列
            if(board[i] == col)
                return false;
            // 是否位于同一斜线上，即行差绝对值等于列差绝对值
            if(Math.abs(board[i] - col) == row - i)
                return false;
        }
        return true;
    }
}
/* output
[[0, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0], [0, 0, 1, 0]]
[[0, 0, 1, 0], [1, 0, 0, 0], [0, 0, 0, 1], [0, 1, 0, 0]]
[1, 3, 0, 2]
[2, 0, 3, 1]  */

若是 n 皇后问题，空间复杂度为 $O(n)$，这里使用剪枝（isSafe() 返回 true 才进行递归）情况下，实际的搜索节点大约是指数级的，接近 $O(c^N)$，其中 c 介于 1.5 到 2 之间，无剪枝，最坏情况下为 $O(N!)$。

装载问题

假设现在有一批共 n 个集装箱要装上一艘载重量为 c 的轮船，其中集装箱 i 的重量为 Wi，找出一种最优装载方案，将轮船尽可能装满，即在装载体积不受限制的情况下，将尽可能重的集装箱装上轮船。

这个问题是 0-1 背包问题的一个变种，目标是使得装上轮船的总重量尽可能接近但不超过载重量 c，可以使用动态规划或回溯法，这里先实现回溯法。

需要定义一个 boolean[] visited 数组表示货物是否被访问过，sum 表示当前装载的货物总的重量，result 为最终的最大总重量。

遍历每一件货物，尝试将当前货物加上总重量，如果不大于最大的重量，并且加上之后的总重量大于保存的最大实际载重，那么就更新最大实际载重，否则直接返回。接着，将当前的货物的状态置为已经访问过，执行对下一个货物的判断，执行完之后，将当前货物置为不被访问过，相当于回溯，退回上一步。实现代码如下：

public class ShipLoad {
    private static int result = 0;

    public static void main(String[] args) {
        int[] weights = {18, 7, 25, 36};
        int c = 80;
        System.out.println(find(weights, c));
    }

    public static int find(int[] weights, int c) {
        result = 0;
        backtrack(weights, c, 0, 0, new boolean[weights.length]);
        return result;
    }

    public static void backtrack(int[] weights, int c, int sum, int i, boolean[] visited) {
        for(; i < weights.length; i++) {
            if(!visited[i]) {
                // 尝试加上当前货物
                int load = sum + weights[i];
                if(load <= c) {
                    // 与保存的最大装载量对比更新
                    if(load > result)
                        result = load;
                } else continue; // 超过了就跳过当前货物
                visited[i] = true; // 当前货物已装过
                backtrack(weights, c, load, i + 1, visited); // 递归后面的货物
                visited[i] = false; // 去掉当前货物，递归其他的货物
            }
        }
    }
}
/* output
79  */

空间复杂度是 O(n)，时间复杂度是指数级别 O(n!)。

该回溯法的思路是通过 for 循环遍历所有可能的组合，也可以使用 0-1 背包中的朴素回溯方法，即“选或不选”递归。思路是先排序（大数优先），减少不必要搜索，然后按固定的“二叉决策树”深度优先搜索：

public class ShipLoad {
    private static int best = 0;

    public static void main(String[] args) {
        int[] weights = {18, 7, 25, 36};
        int c = 80;
        System.out.println(find(weights, c));
    }

    public static int find(int[] weights, int c) {
        best = 0;
        // 先对weights降序排序，加快搜索
        weights = IntStream.of(weights)
                .boxed()
                .sorted((w1, w2) -> w2 - w1)
                .mapToInt(Integer::intValue)
                .toArray();
        dfs(weights, c, 0, 0);
        return best;
    }
    // 0-1背包的朴素回溯方法（“选或不选“递归）
    public static void dfs(int[] weights, int c, int current, int i) {
        if(current > c)
            return; // 若当前总重过载，剪枝
        if(current > best)
            best = current; // 若当前总重大于历史最佳，则更新
        if(i == weights.length)
            return; // 所有集装箱已考虑
        // 选择装载当前集装箱
        dfs(weights, c, current + weights[i], i + 1);
        // 选择不装载当前集装箱
        dfs(weights, c, current, i + 1);
    }
}

在 dfs() 中，先剪枝，避免后续无意义的计算，再更新 best，确保 current 未超载的情况下才更新，最后检查是否遍历完，如果所有集装箱都考虑过了，就返回。这样的顺序保证了正确性和效率的平衡。

最后，还可以使用 0-1 背包问题的动态规划算法，这里使用优化后的一维数组，定义 dp[j] 表示载重量不超过 j 时的最大装载重量：

• 初始化：dp[j] = 0；

• 遍历每个集装箱重量 Wi，逆序更新 dp[j]：dp[j] = max(dp[j], dp[j - Wi] + Wi) （如果 j >= Wi）；

• 结果是 dp[c]，即不超过 c 的最大装载重量。

实现如下：

public static int dpOneDim(int[] weights, int c) {
    int[] dp = new int[c + 1];
    for(int weight : weights) {
        for(int j = c; j >= weight; j--) // 逆序遍历
            dp[j] = Math.max(dp[j], dp[j - weight] + weight);
    }
    return dp[c];
}

时间复杂度 O(nc)，适合 c 不太大的情况。

0-1 背包

前面已经介绍了 0-1 背包问题的动态规划以及递归+备忘录的解法，现在介绍回溯法。

对每一件物品都尝试性加入，在加入之前，我们需要判断是否被添加过，加入后的总重量会不会超重，如果符合条件，则判断加入的总价值是否为当前最大，符合则保存最大的价值，反之，跳过当前物品（相当于减枝）。然后尝试对后面的物品进行相同的判断，处理完成之后，需要将该物品拿出来（相当于不放该物品，回溯的做法），接着判断后续的物品。实现如下：

class Item {
    int weight;
    int value;

    public Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

public class Knapsack01 {
    private static int maxValue = 0;

    public static void main(String[] args) {
        List<Item> items = new ArrayList<>();
        items.add(new Item(10, 32));
        items.add(new Item(5, 12));
        items.add(new Item(8, 4));
        items.add(new Item(3, 32));
        int capacity = 13;
        System.out.println(findMaxValue(items, capacity));
    }

    public static int findMaxValue(List<Item> items, int c) {
        maxValue = 0;
        backtrack_origin(items, c, 0, 0, 0, new boolean[items.size()]);
        return maxValue;
    }

    public static void backtrack_origin(List<Item> items, int c, int sumValue, int sumWeight, int i, boolean[] visited) {
        for(; i < items.size(); i++) {
            Item item = items.get(i);
            if(!visited[i]) {
                int currentWeight = sumWeight + item.weight;
                int currentValue = sumValue + item.value;
                if(currentWeight <= c) {
                    if(currentValue > maxValue)
                        maxValue = currentValue;
                } else continue; // 注意，必须得continue跳过当前，不能直接return跳过所有
                visited[i] = true;
                backtrack_origin(items, c, currentValue, currentWeight, i + 1, visited);
                visited[i] = false;
            }
        }
    }
}
/* output
64  */

时间复杂度是 $O(n^n)$。

其实可以不用 visited 数组，优化后的回溯法如下：

public static void backtrack(List<Item> items, int c, int sumValue, int sumWeight, int i) {
    if(sumWeight > c) return; // 剪枝：重量超过背包容量，立即返回
    // 更新最大价值
    if(sumValue > maxValue)
        maxValue = sumValue;

    // 从当前索引 i 开始尝试选取物品
    for(int j = i; j < items.size(); j++) {
        Item item = items.get(j);
        backtrack(items, c, sumValue + item.value, sumWeight + item.weight, j + 1);
    }
}

for 循环用于枚举物品，但递归时 j + 1，避免重复选择。每次递归考虑两种情况：

• 选当前物品：递归调用 backtrack，更新 sumValue 和 sumWeight。

• 不选当前物品：递归自然跳过当前 j，因为 j + 1 传入。

剪枝优化，如果 sumWeight > c，直接 return，避免无效计算。

旅行售货员问题

某售货员要到若干城市去推销商品，已知各城市之间的路程（或旅费）。他要选定一条从驻地出发，经过每个城市一次，使总的路程（或总旅费）最小。（假设不回到驻地）

使用使用二维数据存储每两个节点之间的路程，比如 distances[0][2] 和 distances[2][0] 都表示节点 1 和节点 3 之间的距离。除此外，还要存储城市的数量、路程最小值、当前路程值、被访问的城市。

从第 0 个城市开始，判断步数是否走完所有地方，如果满足并且路径路程比当前最小路程还小，那么就保存当前的路径。接着执行下一步，遍历后续的地方，如果没有被访问过，并且可达，那么就尝试走到该节点，递归遍历，递归完成后，需要回退上一步，接着执行下一个节点。代码如下：

public class TSP_Variant {
    int count; // 城市数量
    int[] currRoutes; // 当前路径
    int[] minRoutes; // 最短路径
    int currDistance; // 当前路程
    int minDistance = Integer.MAX_VALUE; // 最小路程
    boolean[] visited; // 是否被访问过
    int[][] distances; // 城市间距离

    public TSP_Variant(int count) {
        this.count = count;
        currRoutes = new int[count];
        minRoutes = new int[count];
        visited = new boolean[count];
        distances = new int[count][count];
        currDistance = 0;
        Arrays.fill(currRoutes, -1);
    }

    public static void main(String[] args) {
        TSP_Variant travel = new TSP_Variant(4);
        travel.distances[0][0] = -1;
        travel.distances[0][1] = 30;
        travel.distances[0][2] = 6;
        travel.distances[0][3] = 4;

        travel.distances[1][0] = 30;
        travel.distances[1][1] = -1;
        travel.distances[1][2] = 5;
        travel.distances[1][3] = 10;

        travel.distances[2][0] = 6;
        travel.distances[2][1] = 5;
        travel.distances[2][2] = -1;
        travel.distances[2][3] = 20;

        travel.distances[3][0] = 4;
        travel.distances[3][1] = 10;
        travel.distances[3][2] = 20;
        travel.distances[3][3] = -1;

        // 从城市0出发
        travel.currRoutes[0] = 0;
        travel.visited[0] = true;
        travel.travel(1);

        System.out.println(Arrays.toString(travel.minRoutes));
    }

    public void travel(int step) {
        if(step >= count) { // 是否遍历完所有城市，假设不回到原点
            if(currDistance < minDistance) {
                // 更新最短路程
                minRoutes = Arrays.copyOf(currRoutes, count);
                minDistance = currDistance;
                System.out.println("min distance: " + minDistance);
            }
            // 若想回到原点，只需加上回程即可，使用temp不要直接加到currDistance全局变量上
//            int temp = currDistance + distances[currRoutes[step - 1]][currRoutes[0]];
//            if(temp < minDistance) {
//                minRoutes = Arrays.copyOf(currRoutes, count);
//                minDistance = temp;
//                System.out.println("min distance: " + minDistance);
//            }
            return;
        }
        // 继续走下一个城市
        for(int i = 0; i < count; i++) {
            // 下一步没有走过，并且可达，则选中，currRoutes[step-1]是当前城市的索引
            if(!visited[i] && distances[currRoutes[step - 1]][i] != -1) {
                int ifgo = currDistance + distances[currRoutes[step - 1]][i];
                if(ifgo < minDistance) { // 剪枝
                    currRoutes[step] = i;
                    visited[i] = true;
                    currDistance += distances[currRoutes[step - 1]][i];
                    travel(step + 1);
                    // 回溯到上一步
                    currRoutes[step] = -1;
                    visited[i] = false;
                    currDistance -= distances[currRoutes[step - 1]][i];
                }
            }
        }
    }
}
/* output
min distance: 55
min distance: 21
min distance: 19
[0, 3, 1, 2]

为了不必要的多余遍历，当当前路程值加上到另一节点的路程值大于最小路程值时，直接跳过，进行剪枝操作。注意，这里使用了 step 变量指示走了多少个城市，当 step 等于城市数时，说明遍历结束。

另外，如果不需要回到起始点，也可以直接使用 visited[] 数组判断是否还有没访问的城市，如下：

public class TSP_Try {
    int[][] distances;
    int cityNum;
    boolean[] visited;
    int minDis = Integer.MAX_VALUE;

    public TSP_Try(int num) {
        cityNum = num;
        distances = new int[cityNum][cityNum];
        visited = new boolean[cityNum];
    }

    public static void main(String[] args) {
        TSP_Try travel = new TSP_Try(4);
        // ... distances 初始化

        // 从城市0出发
        travel.travelOnce(0, 0);
        System.out.println(travel.minDis);
    }

    public void travelOnce(int start, int totalDis) {
        // 只遍历完，假设不回到原点
        if(isAllVisited()) {
            if(totalDis < minDis)
                minDis = totalDis;
            return;
        }
        for(int i = 0; i < cityNum; i++) {
            if(distances[start][i] != -1 && !visited[i]) {
                int currentDis = totalDis + distances[start][i];
                if(currentDis < minDis) {
                    // 在回溯过程中，visited 仅在内部被修改，这样才能确保回溯逻辑正确
                    visited[i] = true;
                    travelOnce(i, currentDis);
                    visited[i] = false;
                }
            }
        }
    }

    public boolean isAllVisited() {
        for(boolean visit : visited)
            if(!visit)
                return false;
        return true;
    }
}

自动走迷宫

输入一个迷宫的地图，用程序判断迷宫是否有解，如果有解的话，需要输出解的路径图。

给定如下迷宫，1 表示是墙，不可以走，0 表示可以走：

0 0 0 0 1
1 0 1 0 1
1 1 0 0 0
1 0 0 1 0
1 0 1 1 0

在上下左右都可以走的情况下，我们会选择一个方向来走，每次抉择都是如此，遇到前面走不通，我们就退回到上一步尝试其他方向。如果一个点的四个方向都尝试过了，都不行，还不能到达终点，那么说明这条路是行不通的。

需要用一个同样大小的数组来保存每一个点是否被访问过，用栈来保存访问路径。

首先尝试将 (0, 0) 位置加入堆栈，然后循环判断栈是不是不为空，且没有到达终点：分别尝试上下左右四个方向上的元素是否符合要求（该元素存在、没有被访问过、不是墙），若符合要求，就放入堆栈，并标识已访问过。若都不符合，那么就把堆栈第一个元素弹出，也就是相当于回溯到上一步，此时如果堆栈不为空，那么更新当前位置为栈顶元素的坐标，继续循环。

最后判断堆栈是否为空，如果为空，说明没有解，否则把堆栈反转，从头部取出元素，打印路径。

实现如下：

class Position {
    int row;
    int col;
    public Position(int row, int col) {
        this.row = row;
        this.col = col;
    }
    @Override public String toString() {
        return "(" + row + "," + col + ")";
    }
}

public class Maze {
    int[][] maze;
    Deque<Position> stack;
    boolean[][] visited;
    int row;
    int col;

    public Maze(int row, int col) {
        this.row = row;
        this.col = col;
        maze = new int[row][col];
        stack = new ArrayDeque<>();
        visited = new boolean[row][col];
    }

    public static void main(String[] args) {
        Maze m = new Maze(5, 5);
        m.maze = new int[][]{
                {0, 0, 0, 0, 1},
                {1, 0, 1, 0, 1},
                {1, 1, 0, 0, 0},
                {1, 0, 0, 1, 0},
                {1, 0, 1, 1, 0}
        };
        System.out.println(m.hasPath());
        m.visited = new boolean[5][5];
        m.findAllPath();
    }

    public boolean hasPath() {
        int i = 0;
        int j = 0;
        stack.push(new Position(i, j));
        visited[i][j] = true;

        while (!stack.isEmpty() && !((i == row - 1) && (j == col - 1))) {
            if(j + 1 < col && !visited[i][j + 1] && maze[i][j + 1] == 0) {
                stack.push(new Position(i, j + 1));
                visited[i][j + 1] = true;
            } else if(i + 1 < row && !visited[i + 1][j] && maze[i + 1][j] == 0) {
                stack.push(new Position(i + 1, j));
                visited[i + 1][j] = true;
            } else if(j - 1 >= 0 && !visited[i][j - 1] && maze[i][j - 1] == 0) {
                stack.push(new Position(i, j - 1));
                visited[i][j - 1] = true;
            } else if(i - 1 >= 0 && !visited[i - 1][j] && maze[i - 1][j] == 0) {
                stack.push(new Position(i - 1, j));
                visited[i - 1][j] = true;
            }
            Position top = stack.peek();
            if(top != null && top.row == i && top.col == j) {
                stack.pop();
            }
            if(!stack.isEmpty()) {
                i = stack.peek().row;
                j = stack.peek().col;
            } else break;
        }
        if(stack.isEmpty())
            return false;
        else {
            stack.reversed().forEach(p -> {
                System.out.print("(" + p.row + "," + p.col + ")" + "->");
            });
        }
        return true;
    }
}
/* output
(0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(2,3)->(2,4)->(3,4)->(4,4)->true

这里借助了双向链表以及二维数组，空间复杂度为 $O(N^2)$，时间复杂度是 $O(n^2)$，之前都是使用递归来实现回溯，这里用堆栈来替换了递归，时间复杂度有所减低。

如果想要打印出所有的迷宫出口路径，需要先定义出口的条件，比如“出口在最后一行”，然后使用深度优先搜索：

// 深度优先搜索找所有可到达“出口”的路径
public void findAllPath() {
    List<Position> path = new ArrayList<>();
    dfs(0, 0, path);
}

private void dfs(int i, int j, List<Position> path) {
    if(i < 0 || i > row - 1 || j < 0 || j > col - 1 || visited[i][j] || maze[i][j] == 1)
        return;

    path.add(new Position(i, j));
    visited[i][j] = true;

    if(isExit(i, j)) { // 使用给定的出口规则
        System.out.println(path);
    } else {
        dfs(i - 1, j, path);
        dfs(i + 1, j, path);
        dfs(i, j - 1, path);
        dfs(i, j + 1, path);
    }

    // 回溯
    path.removeLast();
    visited[i][j] = false;
}

// 假设出口在最后一行
boolean isExit(int i, int j) {
    return (i == row - 1) && !(i == 0 && j == 0);
}

图的 m 着色

给定无向连通图 G 和 m 种不同的颜色。用这些颜色为图 G 的各顶点着色，每个顶点着一种颜色。如果有一种着色法使 G 中每条边的 2 个顶点着不同颜色，则称这个图是 m 可着色的。图的 m 着色问题是对于给定图 G 和 m 种颜色，找出所有不同的着色法。

需要找到所有可能的颜色分配方案，使得相邻的两个顶点颜色不同。可以使用回溯算法来尝试所有可能的颜色组合，并通过剪枝来排除无效的路径，从而高效地找到所有合法的着色方案。

这里使用邻接矩阵表示图，使用一个数组 colored 来记录每个顶点的颜色，初始时所有顶点颜色为 -1，表示未着色。

从第一个节点开始进行尝试，对它进行所有可能颜色的选择。在选择某种颜色时，需要确保与该节点相邻的所有节点中没有已经使用这种颜色的。如果满足这个条件，就可以继续对下一个节点进行相同的操作：为其选择一个在相邻节点中未被使用的颜色。如此递归进行，直到所有节点都被成功着色，每完成一次这样的过程，就是一种有效的着色方案。实现如下：

public class MColors_opt {
    int m; // m种颜色
    int n; // n个节点
    int[][] graph; // 邻接矩阵
    int[] colored; // 指示节点涂的颜色
    Set<String> results = new HashSet<>();

    public MColors_opt(int m, int n) {
        this.m = m;
        this.n = n;
        graph = new int[n][n];
        colored = new int[n];
        Arrays.fill(colored, -1);
    }

    public static void main(String[] args) {
        MColors_opt mc = new MColors_opt(4, 5);
        mc.graph = new int[][] {
                {0, 1, 1, 1, 0},
                {1, 0, 1, 1, 0},
                {1, 1, 0, 1, 1},
                {1, 1, 1, 0, 0},
                {0, 0, 1, 0, 0}
        };
        mc.backtrack(0);
        System.out.println(mc.results.size());
    }

    public void backtrack(int i) {
        if(i == n) {
            results.add(Arrays.toString(colored));
            return;
        }
        // 对每一种颜色
        for(int color = 0; color < m; color++) {
            if(isValid(i, color)) {
                colored[i] = color; // 染色
                backtrack(i + 1); // 递归下一个节点
                colored[i] = -1; // 回溯
            }
        }
    }

    private boolean isValid(int node, int color) {
        for(int j = 0; j < node; j++) {
            if(graph[node][j] == 1 && colored[j] == color)
                return false;
        }
        return true;
    }
}

backtrack 方法中递归处理每个顶点。当处理到最后一个顶点时，保存当前颜色方案。对于每个顶点，尝试所有可能的颜色，合法时继续递归处理下一个顶点，否则回溯。使用 isValid 方法检查当前顶点 node 是否可以分配颜色 color，遍历所有已处理的相邻顶点（索引小于 node），如果存在相邻顶点颜色相同，则返回 False，否则返回 True。

空间复杂度是 $O(n^2)$，时间复杂度是 $O(m^n)$。

猜汉字代表的数字

观察下面的加法算式：

      祥 瑞 生 辉
   +  三 羊 献 瑞
----------------------
=  三 羊 生 瑞 气

其中相同的汉字代表相同的数字，不同的汉字代表不同的数字。请你写出这8个字各自代表的数字（答案唯一）。

这是经典的回溯法问题，可以给“三羊献瑞祥生辉气”编号 01234567，然后每一个都需要去尝试从 0 到 9，当尝试到最后一个编号的数字时，需要判断等式是否成立。

实现如下：

public class HanziExpression {
    public static void main(String[] args) {
        int[] hanzis = new int[8]; // 分别代表“三羊献瑞祥生辉气”
        find(0, 8, hanzis);
    }

    public static void find(int i, int n, int[] hanzis) {
        if(i == n) {
            if(check(hanzis))
                System.out.println(Arrays.toString(hanzis));
            return;
        }
        for(int num = 0; num < 10; num++) {
            // 对每一位尝试每一个数字
            hanzis[i] = num;
            if(isValid(hanzis, i)) {
                // 如果合法，就继续下一个
                find(i + 1, n, hanzis);
            }
        }
    }

    // 检查第i个字是否合法（数字首不为0，第i个数字在之前未被使用过）
    public static boolean isValid(int[] hanzis, int i) {
        if(i == 0 && hanzis[i] == 0) {
            return false;
        }
        for(int j = 0; j < i; j++) {
            if(hanzis[j] == hanzis[i])
                return false;
        }
        if(i == 4 && hanzis[i] == 0)
            return false;
        return true;
    }

    // 检查这8个子是否满足加法式
    public static boolean check(int[] hanzis) {
        int a = hanzis[4] * 1000 + hanzis[3] * 100 + hanzis[5] * 10 + hanzis[6];
        int b = hanzis[0] * 1000 + hanzis[1] * 100 + hanzis[2] * 10 + hanzis[3];
        int c = hanzis[0] * 10000 + hanzis[1] * 1000 + hanzis[5] * 100 + hanzis[3] * 10 + hanzis[7];
        return a + b == c;
    }
}
/* output
[1, 0, 8, 5, 9, 6, 7, 2]  */