C语言宽度优先算法解决八数码问题

八数码问题是一种经典的搜索问题，它可以使用宽度优先搜索算法进行求解。下面是使用C语言实现的八数码问题的宽度优先算法解决方法。

首先，定义一个8个元素的数组，用于表示八数码问题的初始状态。例如，下面的代码表示了一个八数码问题的初始状态。

int start[3][3] = {{1, 2, 3}, {4, 5, 6}, {0, 7, 8}};

其中，0表示空白格子。

接下来，定义一个节点结构体，用于保存每一个状态的信息。节点包含了当前状态的数组、父节点指针和操作符等信息。

struct node {
    int state[3][3];
    struct node *parent;
    char op;
};

然后，定义一个队列，用于保存所有的状态节点。初始时，将初始状态节点加入队列中。

struct node *queue[10000];
int head = 0, tail = 0;
struct node *startNode = (struct node *)malloc(sizeof(struct node));
memcpy(startNode->state, start, sizeof(start));
startNode->parent = NULL;
startNode->op = '\0';
queue[tail++] = startNode;

接下来，使用while循环进行循环搜索。每次循环取出队列头部的节点，对其进行扩展操作。扩展操作包括上下左右四个方向的移动。如果移动后的状态是合法的，将其保存为一个新的节点，并加入队列中。如果移动后的状态是目标状态，则搜索结束。

while (head < tail) {
    struct node *p = queue[head++];
    if (memcmp(p->state, target, sizeof(target)) == 0) {
        printf("find solution\n");
        break;
    }
    int x, y;
    for (x = 0; x < 3; x++) {
        for (y = 0; y < 3; y++) {
            if (p->state[x][y] == 0) {
                break;
            }
        }
        if (y < 3) {
            break;
        }
    }
    if (x > 0) {
        struct node *newNode = (struct node *)malloc(sizeof(struct node));
        memcpy(newNode->state, p->state, sizeof(p->state));
        newNode->state[x][y] = newNode->state[x-1][y];
        newNode->state[x-1][y] = 0;
        newNode->parent = p;
        newNode->op = 'u';
        queue[tail++] = newNode;
    }
    if (x < 2) {
        struct node *newNode = (struct node *)malloc(sizeof(struct node));
        memcpy(newNode->state, p->state, sizeof(p->state));
        newNode->state[x][y] = newNode->state[x+1][y];
        newNode->state[x+1][y] = 0;
        newNode->parent = p;
        newNode->op = 'd';
        queue[tail++] = newNode;
    }
    if (y > 0) {
        struct node *newNode = (struct node *)malloc(sizeof(struct node));
        memcpy(newNode->state, p->state, sizeof(p->state));
        newNode->state[x][y] = newNode->state[x][y-1];
        newNode->state[x][y-1] = 0;
        newNode->parent = p;
        newNode->op = 'l';
        queue[tail++] = newNode;
    }
    if (y < 2) {
        struct node *newNode = (struct node *)malloc(sizeof(struct node));
        memcpy(newNode->state, p->state, sizeof(p->state));
        newNode->state[x][y] = newNode->state[x][y+1];
        newNode->state[x][y+1] = 0;
        newNode->parent = p;
        newNode->op = 'r';
        queue[tail++] = newNode;
    }
}

如果搜索结束后，找到了目标状态，可以通过遍历父节点指针，获取到从初始状态到目标状态的移动路径。

完整代码如下：

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

struct node {
    int state[3][3];
    struct node *parent;
    char op;
};

int start[3][3] = {{1, 2, 3}, {4, 5, 6}, {0, 7, 8}};
int target[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};

void printState(int state[3][3]) {
    int i, j;
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            printf("%d ", state[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main() {
    struct node *queue[10000];
    int head = 0, tail = 0;
    struct node *startNode = (struct node *)malloc(sizeof(struct node));
    memcpy(startNode->state, start, sizeof(start));
    startNode->parent = NULL;
    startNode->op = '\0';
    queue[tail++] = startNode;

    while (head < tail) {
        struct node *p = queue[head++];
        if (memcmp(p->state, target, sizeof(target)) == 0) {
            printf("find solution\n");
            struct node *q = p;
            while (q) {
                printState(q->state);
                q = q->parent;
            }
            break;
        }
        int x, y;
        for (x = 0; x < 3; x++) {
            for (y = 0; y < 3; y++) {
                if (p->state[x][y] == 0) {
                    break;
                }
            }
            if (y < 3) {
                break;
            }
        }
        if (x > 0) {
            struct node *newNode = (struct node *)malloc(sizeof(struct node));
            memcpy(newNode->state, p->state, sizeof(p->state));
            newNode->state[x][y] = newNode->state[x-1][y];
            newNode->state[x-1][y] = 0;
            newNode->parent = p;
            newNode->op = 'u';
            queue[tail++] = newNode;
        }
        if (x < 2) {
            struct node *newNode = (struct node *)malloc(sizeof(struct node));
            memcpy(newNode->state, p->state, sizeof(p->state));
            newNode->state[x][y] = newNode->state[x+1][y];
            newNode->state[x+1][y] = 0;
            newNode->parent = p;
            newNode->op = 'd';
            queue[tail++] = newNode;
        }
        if (y > 0) {
            struct node *newNode = (struct node *)malloc(sizeof(struct node));
            memcpy(newNode->state, p->state, sizeof(p->state));
            newNode->state[x][y] = newNode->state[x][y-1];
            newNode->state[x][y-1] = 0;
            newNode->parent = p;
            newNode->op = 'l';
            queue[tail++] = newNode;
        }
        if (y < 2) {
            struct node *newNode = (struct node *)malloc(sizeof(struct node));
            memcpy(newNode->state, p->state, sizeof(p->state));
            newNode->state[x][y] = newNode->state[x][y+1];
            newNode->state[x][y+1] = 0;
            newNode->parent = p;
            newNode->op = 'r';
            queue[tail++] = newNode;
        }
    }

    return 0;
}