C语言深度优先遍历解决骑士巡游问题

本代码使用C语言实现深度优先遍历算法解决骑士巡游问题，骑士巡游问题是指在一个8x8的棋盘上，骑士能否从一个起始位置出发，不重复地走遍所有格子。

代码

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

#define SIZE 8

// 骑士的八个方向移动
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};

// 判断当前位置是否合法
bool isSafe(int x, int y, int sol[SIZE][SIZE]) {
    return (x >= 0 && x < SIZE && y >= 0 && y < SIZE && sol[x][y] == -1);
}

// 打印解
void printSolution(int sol[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%2d ", sol[i][j]);
        }
        printf("\n");
    }
}

// 递归函数，用于深度优先遍历
bool solveKTUtil(int x, int y, int movei, int sol[SIZE][SIZE]) {
    // 如果所有格子都走过，则打印解并返回true
    if (movei == SIZE * SIZE) {
        printSolution(sol);
        printf("\n");
        return true;
    }

    // 遍历骑士的八个方向
    for (int k = 0; k < 8; k++) {
        int nextX = x + dx[k];
        int nextY = y + dy[k];
        // 如果下一个位置合法
        if (isSafe(nextX, nextY, sol)) {
            // 标记当前位置为已访问
            sol[nextX][nextY] = movei;
            // 递归调用
            if (solveKTUtil(nextX, nextY, movei + 1, sol))
                return true;
            else
                // 回溯，将当前位置标记为未访问
                sol[nextX][nextY] = -1;
        }
    }

    // 所有方向都无法继续前进，返回false
    return false;
}

// 解决骑士巡游问题
void solveKT() {
    // 初始化解数组
    int sol[SIZE][SIZE];
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            sol[i][j] = -1;
        }
    }

    // 获取起始位置
    int startX, startY;
    printf("Enter the starting position (0-7): ");
    scanf("%d %d", &startX, &startY);

    // 判断起始位置是否合法
    if (startX < 0 || startX >= SIZE || startY < 0 || startY >= SIZE) {
        printf("Invalid starting position!\n");
        return;
    }

    // 标记起始位置为已访问
    sol[startX][startY] = 0;

    // 调用递归函数解决问题
    if (!solveKTUtil(startX, startY, 1, sol)) {
        printf("No solution found!\n");
    }
}

int main() {
    solveKT();
    return 0;
}

代码解析

dx 和 dy 数组分别存储骑士在八个方向上的横坐标和纵坐标变化量。
isSafe 函数判断当前位置是否合法，即是否在棋盘范围内且未被访问过。
printSolution 函数打印骑士巡游的解，即骑士访问所有格子的顺序。
solveKTUtil 函数是递归函数，用于深度优先遍历，它接受当前位置 (x, y)、当前步数 movei 和解数组 sol 作为参数。
solveKT 函数初始化解数组，获取起始位置，并调用 solveKTUtil 函数解决骑士巡游问题。

总结

本代码使用深度优先遍历算法解决骑士巡游问题，代码结构清晰，注释详细，方便理解和学习。