C语言解决六数码问题

我不是女神ヾ 2022-03-10 05:40 257阅读 0赞

**问题描述：**  
现有一串由数字1，2, 3, 4, 5, 6随机排列组成的数字串，需判断该数字串在经过有限次α变换和β变换后能否转换成数字串123456。  
α变换定义为：  
![在这里插入图片描述][20190309184740363.png]  
β变换定义为：  
![在这里插入图片描述][20190309185028613.png]  
**主要思路：**  
1.6个数字总共的排列组合状态数为6! = 720种，这些状态可以构成一个有向图，故可采用图的遍历算法来求解此问题；  
2.本程序采用的是有向图的广度优先遍历算法，关键点在于对状态访问的记录以及对新状态的判定；  
**注意：**  
用于广度优先遍历的状态访问记录数组visited\[\]此处被定义为了全局变量；因为用于标示访问是否的状态标志是用一个六位数表示的，该六位数的最大值为654321，故visited\[\]数组至少需要空间为654321 \* 4 = 2617284B；而C语言的占空间最大只有2MB左右，所以不能在函数体内部定义该数组。

/*------------------------------------------------
    功能：解决六数码问题
    描述：可实现对多组初始输入序列的判定，第一行为组数，
    变换成功输出Yes，否则输出No。
    输入示例：
    3
    6 5 4 3 2 1
    2 5 3 1 4 6
    2 3 6 1 5 4
    输出示例：
    Yes
    Yes
    Yes
    ---------------------------------------------------
    Author: Zhang Kaizhou
    Date: 2019-3-9 12:03:28
    --------------------------------------------------*/
    #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 res;
        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]);
            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->res = 1; // 转换成功;
                    return;
                }
                if(visited[pnew->state_flag] == 0){ // 若转换后为新的状态
                    in_queue(q, pnew);
                    visited[pnew->state_flag] = 1;
                }
            }
        }
        p->res = 0;
        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];
        }
        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];
        }
        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){
            if(phead->res == 1){
                printf("Yes\n");
            }
            phead = phead->pnext;
        }
        return;
    }

[20190309184740363.png]: /images/20220310/76f61b6fda5a4ccd945a6c3e2d2eb1c3.png
[20190309185028613.png]: /images/20220310/02b1cd043d8c498f948fbf8f17bb7584.png