8shuma.zip_八数码

#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; int m[9]; }node; node *open_out(node *head); int open_insert(node *head, node *item); int close_insert(node *head, node *item); int inv_pair(int m[]); void exchange(int *, int *); int operate(int m[], int op); int diff(int m[], int n[]); node *create_node(); int new_m(node *open, node *close, int m[]); node *copy_node(node *origin); void input_m(int m[]); void print_m(int m[]); int print_result(node *item); void free_queue(node *head); int main(int argc, char *argv[]) { node *open, *close; 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("输入起始节点：\n"); printf("\n"); input_m(p1->m); open_insert(open,p1); printf("输入目标节点：\n"); printf("\n"); input_m(final_m); printf("\n"); 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) { 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); } 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) exchange(m+blank,m+blank-3); break; case 2: /* down */ if (blank<6) exchange(m+blank,m+blank+3); break; case 3: /* left */ if (blank!=0 && blank!=3 && blank!=6) exchange(m+blank,m+blank-1); break; case 4: /* right */ if (blank!=2 && blank!=5 && blank!=8) exchange(m+blank,m+blank+1); break; default : return 1; } return 0; } void exchange(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, f; f=0; for (i=0; i<9; ++i) if (m[i]!=n[i]) f++; return f; } 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); }