八数码深度优先c代码

以下是一个使用深度优先搜索（DFS）算法解决八数码问题的简单C代码：

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

#define N 3

// 全局变量
int goal[N][N] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};  // 目标状态
int start[N][N] = {{2, 8, 3}, {1, 5, 6}, {4, 7, 0}}; // 初始状态
int visited[4000000];                                // 记录已经访问过的状态
int path[4000000];                                   // 记录路径
int found = 0;                                       // 是否找到解

// 判断两个状态是否相等
bool isEqual(int a[N][N], int b[N][N])
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (a[i][j] != b[i][j])
            {
                return false;
            }
        }
    }
    return true;
}

// 深度优先搜索
void dfs(int state[N][N], int depth)
{
    if (isEqual(state, goal))
    {
        found = 1;
        return;
    }

    int x = 0, y = 0;
    // 找到0的位置
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (state[i][j] == 0)
            {
                x = i;
                y = j;
                break;
            }
        }
    }

    // 找到0可移动的位置
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < N && ny >= 0 && ny < N && depth < 30)
        {
            int newState[N][N];
            for (int m = 0; m < N; m++)
            {
                for (int n = 0; n < N; n++)
                {
                    newState[m][n] = state[m][n];
                }
            }
            int temp = newState[x][y];
            newState[x][y] = newState[nx][ny];
            newState[nx][ny] = temp;

            // 判断新状态是否已经访问过
            bool visitedBefore = false;
            for (int i = 0; i < depth; i++)
            {
                if (isEqual(newState, (int(*)[N])(&visited[i * N * N])))
                {
                    visitedBefore = true;
                    break;
                }
            }

            // 如果新状态未访问过，则递归搜索
            if (!visitedBefore)
            {
                for (int m = 0; m < N; m++)
                {
                    for (int n = 0; n < N; n++)
                    {
                        visited[depth * N * N + m * N + n] = newState[m][n];
                    }
                }
                path[depth] = i; // 保存移动方向
                dfs(newState, depth + 1);
                if (found == 1)
                    return;
            }
        }
    }
}

int main()
{
    dfs(start, 0);

    if (found == 1)
    {
        printf("找到解路径：");
        for (int i = 0; i <= N * N; i++)
        {
            if (path[i] == 0)
                printf("上 ");
            else if (path[i] == 1)
                printf("下 ");
            else if (path[i] == 2)
                printf("左 ");
            else if (path[i] == 3)
                printf("右 ");
        }
    }
    else
    {
        printf("未找到解");
    }

    return 0;
}

这段代码实现了对八数码问题的深度优先搜索（DFS）算法。通过递归实现状态的穷举搜索，每次递归会交换0和邻居位置的数字，直到找到与目标状态一致的解或所有状态都已访问过。若找到解，会输出移动的路径方向。