八数码问题（C+数组（学艺不精，没敢用指针和结构体QAQ））

1. #include<stdio.h>
2. 
3. int BFS(int origin[],int n,int target []);
4. int KT( int s[]);
5. int InsertHash(int h,int sum);
6. int Expand(int n,int Target);
7. //主函数，输入初始状态和目标状态
8. int main()
9. {
10.   int origin[9]={1,2,3,4,5,6,7,8,0},target[9]={0,2,3,1,5,6,4,7,8};
11. /*  printf("请输入初始状态：例如：\n1 2 3\n4 5 6\n7 8 0\n------*请输入:*------\n");
12.   for(int i=0;i<9;i++)
13.   {
14.     scanf("%d",&origin[i]);
15.   }
16.   printf("请输入目标状态：例如：\n1 2 3\n4 5 6\n7 8 0\n------*请输入:*------\n");
17.   for(i=0;i<9;i++)
18.   {
19.     scanf("%d",&target[i]);
20.   }
21. */
22.   BFS(origin,8,target);
23.   return 0;
24. }
25. //BFS函数，接收origin和target并开始广度优先搜索，使用hash判重.
26. //用Hash实现判重
27. const int MAXHASHSIZE=1200;//362880
28. int queue[MAXHASHSIZE],hash[MAXHASHSIZE],loc0[MAXHASHSIZE];//loc0[]记录0的位置
29. int num,num2;//num记录队尾，num2记录队头
30. //0所在每个位置的可扩展的位置
31. int loc[9][5];
32. int Ceng[MAXHASHSIZE],C,C1;//记录层数
33. int BFS(int origin[],int n,int target [])//n记录0的初始位置
34. {
35. 
36.   //初始化
37.   int h=0,sum=0; num=num2=0;C=C1=0;Ceng[C]=1;
38.   int Target=0;
39.   Target=KT(target);
40.   //初始化0所在每个位置的可扩展的位置
41.   loc[0][0]=1;loc[1][0]=0;loc[2][0]=1;loc[3][0]=0;loc[4][0]=1;loc[5][0]=2;loc[6][0]=3;loc[7][0]=4;loc[8][0]=5;
42.   loc[0][1]=3;loc[1][1]=2;loc[2][1]=5;loc[3][1]=4;loc[4][1]=3;loc[5][1]=4;loc[6][1]=7;loc[7][1]=6;loc[8][1]=7;
43.         loc[1][2]=4;      loc[3][2]=6;loc[4][2]=5;loc[5][2]=8;      loc[7][2]=8;
44.                           loc[4][3]=7;
45.   //首元素放入队列
46.   sum=KT(origin);
47.   h=sum%MAXHASHSIZE;//得到哈希值
48.   queue[num]=sum;
49.   InsertHash(h,sum); 
50.   printf("%d",n);
51.     printf("\n");
52. 
53.     C1=C+1;
54.   //广度搜索
55.   loc0[num]=n;
56.   Expand(n,Target);
57.   if(InsertHash(h,sum))
58.   {
59.     num++;
60.     queue[num]=sum;
61.   }
62.   return 0;
63. }
64. int Expand(int n,int Target)
65. {
66.   ///逆康托展开
67.   int  fac[] = {1,1,2,6,24,120,720,5040,40320};
68.   int i, j, t, vst[8]={0},s[9]; 
69.   int k=queue[num2];
70.     k--;  
71. for (i=0; i<9; i++)
72.     {  
73.         t = k/fac[9-i-1];  
74.         k %= fac[9-i-1];  
75. for (j=0; j<9; j++)  
76. if (!vst[j])  
77.             {  
78. if(t==0)break;  
79.                 t--;  
80.             }  
81.         s[i] = j;  
82.         vst[j] = 1;
83.     }
84.   //显示最终结果
85.   if(queue[num2]==Target)
86.   {
87.     printf("\n");
88.     for(i=0;i<9;i++)
89.     {
90.       printf("%d",s[i]);
91.       if(i%3==2)
92.         printf("\n");
93.     }
94.     return 1;
95.   }
96.   int temp[9];
97.   //队头扩展
98.   int next=0;
99.   while(loc[n][next]!=NULL || (n==1&&next==0&&loc[n][next]==0) || (n==3&&next==0&&loc[n][next]==0))
100.  {
101.    printf("%d ",loc[n][next]); 
102.    //广度扩展
103.    for(i=0;i<9;i++)temp[i]=s[i];
104.    temp[n]=temp[loc[n][next]];
105.    temp[loc[n][next]]=0;
106.    //判断是否已存在
107.    int sum=KT(temp);
108.    int h=sum%MAXHASHSIZE;//得到哈希值
109.    if(InsertHash(h,sum))
110.    {
111.      //插入队列
112.      num++;
113.      queue[num]=sum;
114.      loc0[num]=loc[n][next];
115.      Ceng[C1]++;
116.    }
117.    next++;
118.  }
119.  printf("-");
120.  Ceng[C]--;
121.  if(Ceng[C]<=0)
122.  {
123.    printf("\n");
124.    C++;
125.    C1=C+1;
126.  }
127.  num2++;//读取下一个
128.  n=loc0[num2];
129.  if(Expand(n,Target))
130.    return 1;
131.  if(num2==362879)
132.    return 0;
133. }
134. /*  康托函数 */
135. int KT( int s[])  
136. {  
137.  int  fac[] = {1,1,2,6,24,120,720,5040,40320};
138. int i, j, t, sum;  
139.     sum = 0;  
140. for (i=0; i<9; i++)  
141.     {  
142.         t = 0;  
143. for (j=i+1; j<9; j++)  
144. if (s[j] < s[i])  
145.                 t++;  
146.         sum += t*fac[9-i-1];  
147.     }  
148. return sum+1;  
149. } 
150. //插入hash表函数
151. int InsertHash(int h,int sum)
152. {
153.  if(hash[h]==sum)    
154.    return 0;
155.  else
156.  {
157.    if(hash[h]==NULL)
158.    {
159.      hash[h]=sum;
160.      return 1;
161.    }
162.    h++;
163.    if(InsertHash(h,sum))
164.      return 1;
165.    else
166.      return 0;
167.  }
168. }