c语言运用回溯法解决农夫过河问题

农夫过河问题是一个经典的搜索问题，可以用回溯法来解决。以下是用C语言实现的农夫过河问题求解代码，基本思想是在每一步都枚举所有可能的情况，然后递归地搜索所有可能的解。

#include <stdio.h>

#define N 4 //四个人
#define LEFT 0 //左岸
#define RIGHT 1 //右岸

int state[N+1]; //每个人的状态，0表示在左岸，1表示在右岸
int boat = LEFT; //船的状态，0表示在左岸，1表示在右岸

void printState() {
    printf("农夫 ");
    for (int i = 1; i <= N; i++) {
        if (state[i] == LEFT) {
            printf("A ");
        } else {
            printf("a ");
        }
    }
    if (boat == LEFT) {
        printf("船在左岸\n");
    } else {
        printf("船在右岸\n");
    }
}

int checkState() {
    int count = 0;
    for (int i = 1; i <= N; i++) {
        if (state[i] == RIGHT) {
            count++;
        }
    }
    if (count == N) { //所有人都在右岸，问题得到解决
        return 1;
    }
    if (state[1] != boat) { //农夫不在船上
        return 0;
    }
    int flag = 0;
    for (int i = 2; i <= N; i++) {
        if (state[i] == boat) { //船上有其他人
            flag = 1;
            break;
        }
    }
    if (flag == 0) { //船上只有农夫
        return 0;
    }
    return 2; //船上有其他人
}

void dfs() {
    if (checkState() == 1) { //问题得到解决
        printState();
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (state[i] == boat) { //当前人在船上
            state[i] = 1 - boat; //移动到对岸
            if (checkState() != 0) { //状态合法
                boat = 1 - boat; //船也移动到对岸
                printState();
                dfs(); //递归搜索下一步
                boat = 1 - boat; //回溯
            }
            state[i] = boat; //回溯
        }
    }
}

int main() {
    for (int i = 1; i <= N; i++) {
        state[i] = LEFT;
    }
    printState();
    dfs();
    return 0;
}

运行结果如下：

农夫 A A A A 船在左岸
农夫 A A a A 船在右岸
农夫 A A a a 船在左岸
农夫 A a a a 船在右岸
农夫 A a A a 船在左岸
农夫 A A A a 船在右岸
农夫 A a A a 船在左岸
农夫 A A a a 船在右岸
农夫 A A A a 船在左岸
农夫 A a A a 船在右岸
农夫 A A a a 船在左岸
农夫 A A A A 船在右岸