bashuma.c

八数码问题 解决人工只能的八数码问题可以用

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

typedef struct s_node {
        struct s_node *father;
        struct s_node *prev;
        struct s_node *next;
        int step; 
        int diff;
        int weight; /* weight=step+diff */
        int m[9];  /* value of m should be in 0..8, 0 stands for blank */
}node;
        
/* 返回open表里的第一个节点并删除 */
node *open_out(node *head);


/*向open队列里插入节点*/
int open_insert(node *head, node *item); 


/*向close队列里插入节点*/
int close_insert(node *head, node *item);


/* return number inverse pairs */
int inv_pair(int m[]);

/* swap two char variables */
void swap(int *, int *);

/* do operate op on m */
int operate(int m[], int op);

/* return number of different grids */
int diff(int m[], int n[]);
node *create_node();
/* check whether the new node has appeared before */
int new_m(node *open, node *close, int m[]);

node *copy_node(node *origin);

void input_m(int m[]);
void print_m(int m[]);

/*return steps */
int print_result(node *item);
void free_queue(node *head);

int main(int argc, char *argv[])
{
    node *open, *close; /*open and close are heads of queues. */
    node *p1, *p2, *p3; 
    int op;
    int node_num,total_step;    
    int final_m[9];
    open=create_node();
    close=create_node();
    open->prev=close->prev=open->next=close->next=NULL;
    
    /* 初使化，输入初始状态 */
    p1=create_node();
    p1->father=NULL;
    p1->step=0;
    printf("Input original status\n");
    printf("Please input 3 lines of number ranging 0 to 8:\n");
    printf("\n");
    input_m(p1->m);  /* 存储 */

    open_insert(open,p1);    /* 插入到open队列中 */ 

     /* 输入目标状态 */
    printf("Input final status\n");
    printf("Please input 3 lines of number ranging 0 to 8:\n");    
    input_m(final_m); 	/* 存储 */
    printf("\n");
    
    /* check */
    if ((inv_pair(p1->m)%2)!=(inv_pair(final_m)%2)) {
        printf("No solution!\n");
        return 0;
    }
    node_num=1;
    p1=open_out(open);
    while (p1!=NULL) {
        close_insert(close,p1);
        /*生成新接点 */
        for (op=1; op<=4; ++op) {
            p2=copy_node(p1);
            operate(p2->m, op);            
            if (new_m(open,close,p2->m)) {
                p2->father=p1;
                p2->step=p1->step+1;
                p2->diff=diff(p2->m,final_m);
                p2->weight=p2->step+p2->diff;
                if (diff(p2->m,final_m)==0) {  /* Solution found! */
                    total_step=print_result(p2);
                    printf("Total step: %d\n",total_step);
                    free_queue(open);
                    free_queue(close);
                    return 0;
                } else {
#ifdef DEBUG
                    ++node_num;
                    printf("%d\n",node_num);
#endif
                    open_insert(open,p2);
                }
            } else {
                free(p2);
            }
        }
        p1=open_out(open);
    }/* end of while */
    printf("No solution!\n");        
    return 0;
}


int open_insert(node *head, node *item)
{
    node *p,*q;
    p=head->next; q=head;
    while (p!=NULL && item->weight > p->weight ) {
          q=p; 
          p=p->next;
    }
    q->next=item;
    item->prev=q;
    item->next=p;
    if (p!=NULL) {
        p->prev=item;
    }
    return 0;
}
          
node *open_out(node *head)
{
    node *p;
    if (head->next==NULL)
        return NULL;
    p=head->next;
    head->next=p->next;
    if (p->next!=NULL)
        p->next->prev=head;
    p->prev=NULL;
    p->next=NULL;
    return p;
}

int close_insert(node *head, node *item)
{
    item->next=head->next;
    item->prev=head;
    head->next=item;
    if (item->next!=NULL)
        item->next->prev=item;
    return 0;
}

int operate(int m[], int op)
{
    int blank;
    blank=0;
    while (m[blank]!=0 && blank<9 )
        ++blank;
    if (blank==9)
        return 1;
    
    switch (op) {
        case 1: /* up */
            if (blank>2)
                swap(m+blank,m+blank-3);
            break;
        case 2: /* down */
            if (blank<6)
                swap(m+blank,m+blank+3);
            break;
        case 3: /* left */
            if (blank!=0 && blank!=3 && blank!=6)
                swap(m+blank,m+blank-1);
            break;
        case 4: /* right */
            if (blank!=2 && blank!=5 && blank!=8)
                swap(m+blank,m+blank+1);
            break;
        default : return 1;
    }
    return 0;
}
       
void swap(int *a, int *b)
{
    int c;
    c=*a;
    *a=*b;
    *b=c;
}

int inv_pair(int m[])
{
    int i, j, total;
    total=0;
    for (i=1; i<9; ++i)
        for (j=0; j<i; ++j)
            if (m[i]!=0 && m[j]!=0 && m[j]<m[i])
                ++total;
    return total;
}

int diff(int m[], int n[])
{
    int i, d;
    d=0;
    for (i=0; i<9; ++i)
        if (m[i]!=n[i])
            ++d;
    return d;
}

node *create_node()
{
    return (node *)malloc(sizeof(node));
}

void input_m(int m[])
{
    int i;
    for (i=0; i<9; ++i)
        scanf("%d",m+i);
}

void print_m(int m[])
{
    int i;
    for (i=0; i<9; ++i) {
        printf("%d ",m[i]);
        if ((i%3)==2)
            printf("\n");
    }
}
    
int new_m(node *open, node *close, int m[])
{
    node *p;
    int same;
    int i;
    p=open->next;
    while (p!=NULL) {
        same=1;
        for (i=0; i<9; ++i)
            if (p->m[i]!=m[i])
                same=0;
        if (same)
            return 0;
        p=p->next;
    }
    p=close->next;
    while (p!=NULL) {
        same=1;
        for (i=0; i<9; ++i)
            if (p->m[i]!=m[i])
                same=0;
        if (same)
            return 0;
        p=p->next;
    }
    return 1;
}

node *copy_node(node *origin)
{
    node *p;
    int i;
    p=create_node();
    p->step=origin->step;
    p->diff=origin->diff;
    p->weight=origin->weight;
    for (i=0; i<9; ++i)
        (p->m)[i]=(origin->m)[i];
    return p;
}

int print_result(node *item)
{
    node *p;
    int step;
    p=item;
    if (p!=NULL) {
        step=print_result(p->father);
        printf("\n");
        print_m(p->m);
        return step+1;
    } else {
        return -1;
    }
}

void free_queue(node *head)
{
    node *p,*q;
    p=head->next;
    while (p!=NULL) {
        q=p->next;
        free(p);
        p=q;
    }
    free(head);
}