算法谜题1，狼羊菜过河 使用回溯法解决 java 编写

好的，下面是使用 Java 编写的狼羊菜过河问题的回溯法解决方案：

public class Main {
    public static void main(String[] args) {
        int[] state = {0, 0, 0, 0};  // 初始状态，0表示这个人和狼、羊、菜都在左岸
        boolean success = backtrack(state, 0);  // 调用回溯函数
        if (success) {
            System.out.println("找到了符合条件的解！");
            for (int i = 0; i < 4; i++) {
                System.out.println("位置 " + i + " 的状态是：" + state[i]);
            }
        } else {
            System.out.println("无法找到符合条件的解！");
        }
    }

    public static boolean backtrack(int[] state, int pos) {
        // 判断当前状态是否符合条件
        if (pos == 4 && state[0] == 0 && state[1] == 0 && state[2] == 0 && state[3] == 0) {
            return true;  // 找到了符合条件的解
        }

        // 尝试所有可能的状态
        for (int i = 0; i < 5; i++) {
            if (is_valid(state, pos, i)) {  // 判断当前状态是否合法
                state[pos] = i;  // 更新状态
                if (backtrack(state, pos + 1)) {
                    return true;  // 找到了符合条件的解
                }
                state[pos] = -1;  // 回溯到上一个状态
            }
        }

        return false;  // 没有找到符合条件的解
    }

    public static boolean is_valid(int[] state, int pos, int val) {
        if (pos == 0) {  // 起点状态，不需要判断
            return true;
        }
        if (val == state[pos - 1]) {  // 不能带上上一次带过来的动物或菜
            return false;
        }
        if (state[0] != state[1]) {  // 人必须在带走动物或菜的岸边
            return false;
        }
        if (state[1] == 0 && (state[2] == 1 && state[3] == 1)) {  // 狼吃羊的情况
            return false;
        }
        if (state[1] == 0 && (state[1] == 2 && state[3] == 4)) {  // 羊吃菜的情况
            return false;
        }
        if (state[1] == 1 && (state[2] == 0 && state[3] == 0)) {  // 狼羊都在右岸而人在左岸的情况
            return false;
        }
        if (state[1] == 1 && (state[1] == 2 && state[3] == 4)) {  // 羊菜都在右岸而人在左岸的情况
            return false;
        }
        return true;
    }
}

在这个代码中，`state`数组表示当前的状态，`pos`表示当前搜索到的位置，`is_valid`函数用来判断当前状态是否合法，如果当前状态合法，就更新状态数组并继续往下搜索，否则就回溯到上一个状态重新尝试其他可能的状态。

注意，在判断状态是否合法时，我们需要根据题目要求对每种情况进行判断，例如，不能带上上一次带过来的动物或菜，人必须在带走动物或菜的岸边，狼不能和羊在同一岸边等等。

最后，我们可以调用`backtrack`函数来解决狼羊菜过河问题，例如：

int[] state = {0, 0, 0, 0};  // 初始状态，0表示这个人和狼、羊、菜都在左岸
boolean success = backtrack(state, 0);  // 调用回溯函数
if (success) {
    System.out.println("找到了符合条件的解！");
} else {
    System.out.println("无法找到符合条件的解！");
}

这样就可以找到符合条件的解，或者确定无解了。