用c语言写回溯法的农夫过河问题

好的，这是一个经典的回溯法例题，下面是用 C 语言实现的农夫过河问题（假设农夫、狼、羊、菜分别用 1、2、3、4 表示）：

#include <stdio.h>
#include <stdbool.h>

// 判断状态是否合法
bool is_valid(int state) {
    int farmer = state & 1;        // 农夫的位置
    int wolf = (state >> 1) & 1;   // 狼的位置
    int sheep = (state >> 2) & 1;  // 羊的位置
    int cabbage = (state >> 3) & 1;  // 菜的位置

    // 判断狼、羊、菜是否会发生冲突
    if ((wolf == sheep && farmer != wolf) ||
        (sheep == cabbage && farmer != sheep)) {
        return false;
    }

    return true;
}

// 输出状态
void print_state(int state) {
    int farmer = state & 1;        // 农夫的位置
    int wolf = (state >> 1) & 1;   // 狼的位置
    int sheep = (state >> 2) & 1;  // 羊的位置
    int cabbage = (state >> 3) & 1;  // 菜的位置

    printf("农夫 %s, ", farmer ? "在右岸" : "在左岸");
    printf("狼 %s, ", wolf ? "在右岸" : "在左岸");
    printf("羊 %s, ", sheep ? "在右岸" : "在左岸");
    printf("菜 %s\n", cabbage ? "在右岸" : "在左岸");
}

// 求解农夫过河问题
void solve(int state) {
    if (state == 0b1111) {  // 如果所有物品都在右岸，则找到了一组解
        printf("找到一组解：\n");
        return;
    }

    for (int i = 1; i <= 8; i++) {
        if ((state & (1 << (i - 1))) == 0) {  // 如果第 i 个物品还不在右岸
            int new_state = state | (1 << (i - 1));  // 将第 i 个物品移到右岸
            if (is_valid(new_state)) {  // 如果新状态合法
                print_state(new_state);  // 输出新状态
                solve(new_state);  // 继续搜索
            }
        }
    }
}

int main() {
    int state = 0b0000;  // 初始状态，所有物品都在左岸
    printf("初始状态：\n");
    print_state(state);
    printf("\n");
    solve(state);  // 求解农夫过河问题
    return 0;
}

这段代码中，`is_valid` 函数用来判断状态是否合法，根据题目描述，只有当农夫不在场时，狼和羊在一起或者羊和菜在一起，就会发生冲突。

`print_state` 函数用来输出状态，方便调试和查看结果。

`solve` 函数是回溯函数，用来求解农夫过河问题。在每一次搜索时，我们从左岸开始，尝试将每个物品移到右岸，对于每个新状态，我们都判断一下是否合法，如果合法就输出状态并继续搜索。如果所有物品都在右岸，就找到了一组解。

在 `main` 函数中，我们首先输出初始状态，然后调用 `solve` 函数求解问题。