C语言解决六数码问题，求解最少变换次数

蔚落 2022-03-09 20:29 263阅读 0赞

**问题描述：**  
关于六数码问题在上一篇文章中已经介绍过，可参考[C语言解决六数码问题][C]。  
**改进：**  
本次代码的功能是求解最少的变换次数。因为本程序的核心是基于数码状态所构成的图的广度优先遍历算法设计的，且每次变换的权值都为1，所以首次找到的变换策略即为拥有最少变换次数的方案。故只需在每次状态发生变化时累加1即可记录变换次数信息。

/*-------------------------------------------------
    功能：解决六数码问题
    描述：可实现对多组初始输入序列的判定，第一行为组数，
    若变换成功，则输出最少变换次数，若失败，则输出-1。
    输入示例：
    3
    6 5 4 3 2 1
    2 5 3 1 4 6
    2 3 6 1 5 4
    输出示例：
    5
    1
    2
    ---------------------------------------------------
    Author: Zhang Kaizhou
    Date: 2019-3-9 22:00:22
    --------------------------------------------------*/
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #define MAXSIZE 1000
    
    int visited[700000] = { 0 }; // 定义一个全局访问数组，用于记录每个状态的访问情况
    
    typedef struct node{ // 定义一个结点数据类型
        int data[6];
        int state_flag;
        int time; // 变换次数
        struct node * pnext;
    } Node;
    
    typedef struct{ // 定义一个队列数据类型
        Node * state[MAXSIZE]; // 指针数组用于存放各结点指针
        int head;
        int tail;
    } Queue;
    
    void state_to_flag(Node * p);
    void search_result(Node * p);
    void in_queue(Queue * q, Node * p);
    void out_queue(Queue * q, Node ** pcur);
    void state_transform(Node * pcur, int i, Node * pnew);
    void alpha_transform(Node * pcur, Node * pnew);
    void beta_transform(Node * pcur, Node * pnew);
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p);
    void list_print(Node * phead);
    
    int main(){
        Node * phead = NULL, * ptail = NULL;
        int n, i;
        scanf("%d", &n);
        for(i = 0; i < n; i++){
            Node * p = (Node *)calloc(1, sizeof(Node));
            scanf("%d %d %d %d %d %d", &p->data[5], &p->data[4], &p->data[3], &p->data[2], &p->data[1], &p->data[0]);
            p->time = 0; // 变换次数初始化为0
            state_to_flag(p);
            search_result(p);
            list_tail_insert(&phead, &ptail, p);
        }
        list_print(phead);
    
        return 0;
    }
    
    void state_to_flag(Node * p){
        int i, sum = 0;
        for(i = 5; i >= 0; i--){
            sum += p->data[i] * pow(10, i);
        }
        p->state_flag = sum;
        return;
    }
    
    void search_result(Node * p){ // 基于状态的广度优先遍历算法
        Queue * q = (Queue *)calloc(1, sizeof(Queue)); // 申请一个环形队列，并初始化
        q->head = 0;
        q->tail = 0;
        Node * pcur;
        Node * pnew = (Node *)calloc(1, sizeof(Node));
        int i;
        in_queue(q, p);
        visited[p->state_flag] = 1;
        while(q->tail != q->head){ // 当队列非空时
            out_queue(q, &pcur);
            for(i = 0; i < 2; i++){
                state_transform(pcur, i, pnew);
                if(pnew->state_flag == 123456){
                    p->time = pnew->time; // 转换成功，保存变换次数
                    return;
                }
                if(visited[pnew->state_flag] == 0){ // 若转换后为新的状态
                    in_queue(q, pnew);
                    visited[pnew->state_flag] = 1;
                }
            }
        }
        p->time = -1; // 转换失败，转换次数为-1
        free(q); q = NULL;
        free(pcur); pcur = NULL;
        free(pnew); pnew = NULL;
        return;
    }
    
    void in_queue(Queue * q, Node * p){
        if((q->tail + 1) % MAXSIZE == q->head){
            printf("The queue is full!\n");
        }else{
            q->tail = (q->tail + 1) % MAXSIZE;
            q->state[q->tail] = p;
        }
        return;
    }
    
    void out_queue(Queue * q, Node ** pcur){
        if(q->tail == q->head){
            printf("The queue is empty!\n");
        }else{
            q->head = (q->head + 1) % MAXSIZE;
            * pcur = q->state[q->head];
        }
        return;
    }
    
    void state_transform(Node * pcur, int i, Node * pnew){
        switch(i){
        case 0: alpha_transform(pcur, pnew); break;
        case 1: beta_transform(pcur, pnew); break;
        }
        return;
    }
    
    void alpha_transform(Node * pcur, Node * pnew){
        int i;
        for(i = 5; i >= 0; i--){
            pnew->data[i] = pcur->data[i];
        }
        pnew->time = pcur->time + 1; // 每次变换后，新状态变化次数加1
        int temp = pnew->data[5];
        pnew->data[5] = pnew->data[2];
        pnew->data[2] = pnew->data[1];
        pnew->data[1] = pnew->data[4];
        pnew->data[4] = temp;
        state_to_flag(pnew);
        return;
    }
    
    void beta_transform(Node * pcur, Node * pnew){
        int i;
        for(i = 5; i >= 0; i--){
            pnew->data[i] = pcur->data[i];
        }
        pnew->time = pcur->time + 1; // 每次变换后，新状态变化次数加1
        int temp = pnew->data[4];
        pnew->data[4] = pnew->data[1];
        pnew->data[1] = pnew->data[0];
        pnew->data[0] = pnew->data[3];
        pnew->data[3] = temp;
        state_to_flag(pnew);
        return;
    }
    
    void list_tail_insert(Node ** pphead, Node ** pptail, Node * p){
        if(* pphead == NULL){
            * pphead = p;
            * pptail = p;
        }else{
            (* pptail)->pnext = p;
            * pptail = p;
        }
        return;
    }
    
    void list_print(Node * phead){
        while(phead != NULL){
            printf("%d\n", phead->time);
            phead = phead->pnext;
        }
        return;
    }

[C]: https://blog.csdn.net/weixin_38679924/article/details/88370182