用c语言实现深度优先搜索八数码问题

好的，以下是用 C 语言实现深度优先搜索八数码问题的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODE_NUM 362880 // 9!，所有状态数量

struct Node {
    int state[9]; // 状态
    int space; // 空格位置
    int depth; // 深度
    int parent; // 父节点索引
    int direction; // 移动方向
};

int visited[MAX_NODE_NUM]; // 记录已经访问的状态
struct Node queue[MAX_NODE_NUM]; // 存放状态的队列
int front = 0, rear = 0; // 队列的头尾指针

// 计算当前状态的哈希值
int hash(struct Node node) {
    int hash_value = 0, i, j, k;
    for (i = 0; i < 9; ++i) {
        k = 1;
        for (j = i + 1; j < 9; ++j) {
            if (node.state[j] < node.state[i]) {
                ++k;
            }
        }
        hash_value += k * factorial(8 - i);
    }
    return hash_value;
}

// 计算阶乘
int factorial(int n) {
    int result = 1, i;
    for (i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

// 判断状态是否已经访问过
int is_visited(struct Node node) {
    int index = hash(node);
    return visited[index];
}

// 记录状态
void record(struct Node node) {
    int index = hash(node);
    visited[index] = 1;
}

// 将状态加入队列
void enqueue(struct Node node) {
    queue[rear++] = node;
}

// 从队列中取出一个状态
struct Node dequeue() {
    return queue[front++];
}

// 判断是否达到目标状态
int is_target(struct Node node, struct Node target) {
    int i;
    for (i = 0; i < 9; ++i) {
        if (node.state[i] != target.state[i]) {
            return 0;
        }
    }
    return 1;
}

// 初始化状态
void init_node(struct Node* node, int* state, int space, int depth, int parent, int direction) {
    int i;
    for (i = 0; i < 9; ++i) {
        node->state[i] = state[i];
    }
    node->space = space;
    node->depth = depth;
    node->parent = parent;
    node->direction = direction;
}

// 打印解路径
void print_path(struct Node* node, struct Node* nodes) {
    int path[100], length = 0, i;
    while (node->parent != -1) {
        path[length++] = node - nodes;
        node = &nodes[node->parent];
    }
    printf("共%d步\n", length);
    for (i = length - 1; i >= 0; --i) {
        node = &nodes[path[i]];
        switch (node->direction) {
            case 0:
                printf("上\n");
                break;
            case 1:
                printf("下\n");
                break;
            case 2:
                printf("左\n");
                break;
            case 3:
                printf("右\n");
                break;
        }
    }
}

// 深度优先搜索
void dfs(struct Node* start, struct Node* target) {
    int i, j, space, depth = 0, parent = -1, direction;
    init_node(start, target->state, target->space, depth, parent, -1);
    record(*start);
    enqueue(*start);
    while (front < rear) {
        struct Node node = dequeue();
        if (is_target(node, *target)) {
            print_path(&node, queue);
            return;
        }
        space = node.space;
        depth = node.depth + 1;
        parent = node - queue;
        if (space > 2) {
            init_node(&queue[rear], node.state, space - 3, depth, parent, 0);
            if (!is_visited(queue[rear])) {
                record(queue[rear]);
                enqueue(queue[rear]);
            }
        }
        if (space < 6) {
            init_node(&queue[rear], node.state, space + 3, depth, parent, 1);
            if (!is_visited(queue[rear])) {
                record(queue[rear]);
                enqueue(queue[rear]);
            }
        }
        if (space % 3 > 0) {
            init_node(&queue[rear], node.state, space - 1, depth, parent, 2);
            if (!is_visited(queue[rear])) {
                record(queue[rear]);
                enqueue(queue[rear]);
            }
        }
        if (space % 3 < 2) {
            init_node(&queue[rear], node.state, space + 1, depth, parent, 3);
            if (!is_visited(queue[rear])) {
                record(queue[rear]);
                enqueue(queue[rear]);
            }
        }
    }
}

int main() {
    int i, j, space = -1;
    struct Node start, target;
    printf("请输入初始状态，用空格隔开：\n");
    for (i = 0; i < 9; ++i) {
        scanf("%d", &start.state[i]);
        if (start.state[i] == 0) {
            space = i;
        }
    }
    start.space = space;
    start.depth = 0;
    start.parent = -1;
    start.direction = -1;
    printf("请输入目标状态，用空格隔开：\n");
    for (i = 0; i < 9; ++i) {
        scanf("%d", &target.state[i]);
        if (target.state[i] == 0) {
            target.space = i;
        }
    }
    target.depth = -1;
    target.parent = -1;
    target.direction = -1;
    memset(visited, 0, sizeof(visited));
    memset(queue, 0, sizeof(queue));
    dfs(&start, &target);
    return 0;
}

以上是一个简单的深度优先搜索八数码问题的实现，仅供参考。