1、把數碼問題就是把一串數字變成下面這個樣子:1 2 38 0 4 7 6 5實現方法1.過程表示源代碼：#include<stdio.h>static int style9=1,2,3,6,7,4,5,8,0;/輸入的數碼/2,5,4,3,0,7,1,8,6 3,2,1,8,0,4,7,6,5 1,0,4,2,7,3,8,5,6 1,0,3,8,2,4,7,6,5static int arrayStep416=5,4,3,6,7,8;/第四步和第六步共用的數組，所以設為全局量static int arrayStep714=3,6,7,4;static int local;/空格的位置

2、int i,j;/所用到的變量int number=0;/記錄移動步數void print();void step1();void step2();void step3();void step4();void step5();void step6();void step7();void step8();void step9();void exchange(int x,int y);void judge();void judge()/判斷空格位置number = 0;for(i=0;i<9;i+)if(stylei=0)local=i;return;void exchange(int x,

3、int y)/交換兩個數int temp;print();temp=stylex;stylex=styley;styley=temp;local=y;number+;void step1()int arrayStep115=3,0,1,2,5;int arrayStep126=6,7,8,5,2,1;if(style2!=0)&&style2!=1)return;elseif(local=2)if(style1=1)exchange(2,5);elseexchange(2,1);return;elseif(local=4)exchange(4,1);i=2;while(loca

4、l!=5)exchange(arrayStep11i,arrayStep11i+1);i+;return;for(i=0;i<3;i+)if(arrayStep11i=local)while(local!=5)exchange(arrayStep11i,arrayStep11i+1);i+;return;for(i=0;i<4;i+)if(arrayStep12i=local)while(local!=1)exchange(arrayStep12i,arrayStep12i+1);i+;return;return;void step2()int arrayStep218=0,3,6

5、,7,8,5,4,1;for(i=0;i<8;i+)if(arrayStep21i=local)while(style0!=1)exchange(arrayStep21i%8,arrayStep21(i+1)%8);i+;break;void step3()int arrayStep318=2,1,4,3,6,7,8,5;for(i=0;i<8;i+)if(arrayStep31i=local)while(style1!=2)exchange(arrayStep31i%8,arrayStep31(i+1)%8);i+;break;void step4()for(i=0;i<6

6、;i+)if(arrayStep41i=local)while(style4!=3)exchange(arrayStep41i%6,arrayStep41(i+1)%6);i=(i+1)%6;while(local!=3)exchange(arrayStep41i%6,arrayStep41(i+5)%6);i=(i+5)%6;break;void step5()int arrayStep519=3,0,1,4,5,2,1,0,3;i=0;doexchange(arrayStep51i,arrayStep51i+1);i+;while(local!=3);void step6()for(i=0

7、;i<6;i+)if(arrayStep41i=local)while(style5!=4)exchange(arrayStep41i%6,arrayStep41(i+1)%6);i+;if(local=8)exchange(8,7);break;return;void step7()for(i=0;i<4;i+)if(arrayStep71i=local)while(style4!=5)exchange(arrayStep71i%4,arrayStep71(i+1)%4);i=(i+1)%4;while(local!=3)exchange(arrayStep71i%4,array

8、Step71(i+3)%4);i=(i+3)%4;break;void step8()int arrayStep8113=3,0,1,2,5,4,7,8,5,2,1,0,3;i=0;doexchange(arrayStep81i,arrayStep81i+1);i+;while(local!=3);void step9()for(i=0;i<4;i+)if(arrayStep71i=local)while(style7!=6)exchange(arrayStep71i%4,arrayStep71(i+1)%4);i=(i+1)%4;while(local!=4)exchange(arra

9、yStep71i%4,arrayStep71(i+3)%4);i=(i+3)%4;break;void print()for(j=0;j<9;j+)if(stylej=0)printf(" t");elseprintf("%dt",stylej);if(j+1)%3=0)printf("n");printf("* %d *n",number);void loop()printf("請輸入數碼：n");for(i=0;i<9;i+)scanf("%d",&s

10、tylei);judge();step1();step2();step3();if(style2!=3)step4();step5();step6();if(style8!=5)step7();step8();step9();print();if(!(style3=8)&&(style6=7)printf("用書上所給算法來看此數碼錯誤！n");void main()while(1)loop();2. 深度優先實現/*說明* 用寬度優先搜索算法實現八數碼問題 */#include<iostream>#include<stdio.h>#

11、include<fstream>#include<stdlib.h> #include "string.h" #include "assert.h" #include "windows.h" using namespace std;int wholeStyle9 = 2,8,3,1,6,4,7,0,5;int standard19 = 1,2,3,8,0,4,7,6,5;int local,i,j;int startKey = 0,endKey = 0,equalKey = 1,tempSpace;struct

12、 node *openHead,*open; /open表struct node *closedHead,*closed; /closed表struct node *tempNode; /臨時節點struct node *answer; /找到的路徑int num = 0;struct nodeint style9;struct node *next;struct node *father;void updateData() /更新要判斷數據int i;printf("請輸入八數碼原始狀態：n");for(i = 0;i < 9;i+)scanf("%d&q

13、uot;,&wholeStylei);printf("請輸入八數碼最終狀態：n");for(i = 0;i < 9;i+)scanf("%d",&standard1i);void judge1(struct node *head)/判斷空格位置for(i = 0;i < 9;i+)if(head->stylei = 0)local = i;return;int judge2(struct node *head) /判斷是否與標準八數碼相等，不相等返回值為0for(i = 0;i < 9;i+)if(head->

14、;stylei != standard1i)if(i = 3)&&(head->style3 = standard16);else if(i = 6)&&(head->style6 = standard13);else return 0;return 1;void judge3() /判斷新生成的八數碼是否就是最終狀態或者在open、closed表中出現if(judge2(tempNode)endKey = 1;elsewhile(openHead->next->next->style0 != 9)for(i = 0;i <

15、9;i+)if(openHead->next->next->stylei != tempNode->stylei)equalKey = 1;break;elseequalKey = 0;if(equalKey)/不相等openHead = openHead->next;elsebreak;openHead = open->next;if(equalKey)/不相等while(closedHead->next->style0 != 9)for(i = 0;i < 9;i+)if(closedHead->next->stylei !

16、= tempNode->stylei)equalKey = 1;break;elseequalKey = 0;if(!equalKey)/相等break;elseclosedHead = closedHead->next;closedHead = closed->next;if(equalKey)/不相等open->next = tempNode;tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;void print(struct node

17、*temp) /輸出八數碼表for(j = 0;j < 9;j+)if(temp->stylej = 0)printf(" t");elseprintf("%dt",temp->stylej);if(j + 1) % 3 = 0)printf("n");void write2txt()ofstream out("F:out_details.txt",ios:app);if( out.fail() )cerr<<"未找到文件"<<endl;out<&

18、lt;" 第"<<+num<<"步n"out<<"open table：n"while(openHead->next->style0 != 9)for(i = 0;i < 9;i +)out<<openHead->next->stylei<<"t"if(i+1) % 3 = 0)out<<"n"out<<"n"openHead = openHead->nex

19、t;openHead = openHead->next;out<<"*n"out<<"closed table：n"while(closedHead->next->style0 != 9)for(i = 0;i < 9;i +)out<<closedHead->next->stylei<<"t"if(i + 1) % 3 =0)out<<"n"out<<"n"closedHead = cl

20、osedHead->next;closedHead = closedHead->next;out<<"-n"out.close();void main()/updateData();/輸入八數碼數據for(i = 0;i < 9;i+) /判斷初始狀態是否已經為最終狀態if(wholeStylei = standard1i);elseif(i = 3)&&(wholeStylei = standard16);else if(i = 6)&&(wholeStylei = standard13);else start

21、Key = 1;break;if(!startKey)printf("不用判斷！n");return;printf("要判斷！n");openHead = new node();open = new node();openHead->style0 = 9;openHead->next = open;for(i = 0;i < 9;i+)open->stylei = wholeStylei;open->next = openHead;open->father = openHead;closedHead = new nod

22、e();closed = new node();closedHead->style0 = 9;closedHead->next = closedHead;closed = closedHead;while(open->style0 != 9)/當open表不為空時一直循環judge1(openHead->next);if(local % 3 > 0)/右移equalKey = 1;tempNode = new node();for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->style

23、i;tempSpace = tempNode->stylelocal - 1;tempNode->stylelocal - 1 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;if(local > 2)/下移equalKey = 1;tempNode = new node();for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->stylei;tempSpace = temp

24、Node->stylelocal - 3;tempNode->stylelocal - 3 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;if(local % 3 < 2)/左移equalKey = 1;tempNode = new node();for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->stylei;tempSpace = tempNode->style

25、local + 1;tempNode->stylelocal + 1 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;if(local < 6)/上移equalKey = 1;tempNode = new node();/tempNode = malloc(sizeof(struct node);for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->stylei;tempSpace

26、 = tempNode->stylelocal + 3;tempNode->stylelocal + 3 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;closed->next = openHead->next;/把open的標頭添加到closed表中openHead->next = openHead->next->next; closed = closed->next;closed->next = closedH

27、ead;write2txt();open->next = tempNode;/把找到的新節點添加到open表中tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;closed->next = openHead->next;/把open的標頭添加到closed表中openHead->next = openHead->next->next; closed = closed->next;closed->next = close

28、dHead;write2txt();answer = new node();tempNode = new node();tempNode = open;while(tempNode->style0 != 9)/將結果路徑存于answeranswer = tempNode;tempNode = tempNode->father;tempNode->next = answer;num = 0;while(answer->next->style0 != 9)/輸出answerprintf("*第%d步*n",num+);print(answer);a

29、nswer = answer->next;printf("n");printf("*第%d步*n",num+);print(answer);if(answer->style3 != standard13)printf("n!輸入的八數碼不合法，不能從初始狀態到最終狀態nnnn");return;3. 寬度優先：/*說明* 用寬度優先搜索算法實現八數碼問題 */#include<iostream>#include<stdio.h>#include<fstream>#include<s

30、tdlib.h> #include "string.h" #include "assert.h" #include "windows.h" using namespace std;int wholeStyle9 = 2,8,3,1,6,4,7,0,5;int standard19 = 1,2,3,8,0,4,7,6,5;int local,i,j;int startKey = 0,endKey = 0,equalKey = 1,tempSpace;struct node *openHead,*open; /open表struct

31、 node *closedHead,*closed; /closed表struct node *tempNode; /臨時節點struct node *answer; /找到的路徑int num = 0;struct nodeint style9;struct node *next;struct node *father;void updateData() /更新要判斷數據int i;printf("請輸入八數碼原始狀態：n");for(i = 0;i < 9;i+)scanf("%d",&wholeStylei);printf("

32、;請輸入八數碼最終狀態：n");for(i = 0;i < 9;i+)scanf("%d",&standard1i);void judge1(struct node *head)/判斷空格位置for(i = 0;i < 9;i+)if(head->stylei = 0)local = i;return;int judge2(struct node *head) /判斷是否與標準八數碼相等，不相等返回值為0for(i = 0;i < 9;i+)if(head->stylei != standard1i)if(i = 3)&

33、;&(head->style3 = standard16);else if(i = 6)&&(head->style6 = standard13);else return 0;return 1;void judge3() /判斷新生成的八數碼是否就是最終狀態或者在open、closed表中出現if(judge2(tempNode)endKey = 1;elsewhile(openHead->next->next->style0 != 9)for(i = 0;i < 9;i+)if(openHead->next->next-

34、>stylei != tempNode->stylei)equalKey = 1;break;elseequalKey = 0;if(equalKey)/不相等openHead = openHead->next;elsebreak;openHead = open->next;if(equalKey)/不相等while(closedHead->next->style0 != 9)for(i = 0;i < 9;i+)if(closedHead->next->stylei != tempNode->stylei)equalKey = 1;

35、break;elseequalKey = 0;if(!equalKey)/相等break;elseclosedHead = closedHead->next;closedHead = closed->next;if(equalKey)/不相等open->next = tempNode;tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;void print(struct node *temp) /輸出八數碼表for(j = 0;j < 9;j+

36、)if(temp->stylej = 0)printf(" t");elseprintf("%dt",temp->stylej);if(j + 1) % 3 = 0)printf("n");void write2txt()ofstream out("F:out_details.txt",ios:app);if( out.fail() )cerr<<"未找到文件"<<endl;out<<" 第"<<+num<&l

37、t;"步n"out<<"open table：n"while(openHead->next->style0 != 9)for(i = 0;i < 9;i +)out<<openHead->next->stylei<<"t"if(i+1) % 3 = 0)out<<"n"out<<"n"openHead = openHead->next;openHead = openHead->next;out&

38、lt;<"*n"out<<"closed table：n"while(closedHead->next->style0 != 9)for(i = 0;i < 9;i +)out<<closedHead->next->stylei<<"t"if(i + 1) % 3 =0)out<<"n"out<<"n"closedHead = closedHead->next;closedHead = clos

39、edHead->next;out<<"-n"out.close();void main()/updateData();/輸入八數碼數據for(i = 0;i < 9;i+) /判斷初始狀態是否已經為最終狀態if(wholeStylei = standard1i);elseif(i = 3)&&(wholeStylei = standard16);else if(i = 6)&&(wholeStylei = standard13);else startKey = 1;break;if(!startKey)printf(&

40、quot;不用判斷！n");return;printf("要判斷！n");openHead = new node();open = new node();openHead->style0 = 9;openHead->next = open;for(i = 0;i < 9;i+)open->stylei = wholeStylei;open->next = openHead;open->father = openHead;closedHead = new node();closed = new node();closedHead-

41、>style0 = 9;closedHead->next = closedHead;closed = closedHead;while(open->style0 != 9)/當open表不為空時一直循環judge1(openHead->next);if(local % 3 > 0)/右移equalKey = 1;tempNode = new node();for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->stylei;tempSpace = tempNode->styleloc

42、al - 1;tempNode->stylelocal - 1 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;if(local > 2)/下移equalKey = 1;tempNode = new node();for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->stylei;tempSpace = tempNode->stylelocal - 3;tempNode-&g

43、t;stylelocal - 3 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;if(local % 3 < 2)/左移equalKey = 1;tempNode = new node();for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->stylei;tempSpace = tempNode->stylelocal + 1;tempNode->stylelocal +

44、 1 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;if(local < 6)/上移equalKey = 1;tempNode = new node();/tempNode = malloc(sizeof(struct node);for(i = 0;i < 9;i+)tempNode->stylei = openHead->next->stylei;tempSpace = tempNode->stylelocal + 3;temp

45、Node->stylelocal + 3 = tempNode->stylelocal;tempNode->stylelocal = tempSpace;judge3();if(endKey)break;closed->next = openHead->next;/把open的標頭添加到closed表中openHead->next = openHead->next->next; closed = closed->next;closed->next = closedHead;write2txt();open->next = tem

46、pNode;/把找到的新節點添加到open表中tempNode->next = openHead;tempNode->father = openHead->next;open = open->next;closed->next = openHead->next;/把open的標頭添加到closed表中openHead->next = openHead->next->next; closed = closed->next;closed->next = closedHead;write2txt();answer = new node

47、();tempNode = new node();tempNode = open;while(tempNode->style0 != 9)/將結果路徑存于answeranswer = tempNode;tempNode = tempNode->father;tempNode->next = answer;num = 0;while(answer->next->style0 != 9)/輸出answerprintf("*第%d步*n",num+);print(answer);answer = answer->next;printf(&quo

48、t;n");printf("*第%d步*n",num+);print(answer);if(answer->style3 != standard13)printf("n!輸入的八數碼不合法，不能從初始狀態到最終狀態nnnn");return;4. A算法/*說明* * A算法實現八數碼問題 * */#include<iostream>#include<fstream>#include<iomanip>using namespace std;void print(struct node *temp);in

49、t wholeStyle9 = 2,8,3,1,6,4,7,0,5;int standard19 = 1,2,3,8,0,4,7,6,5;int local,i,j;int tempSpace;struct node *openHead,*open; /open表struct node *closedHead,*closed; /closed表struct node *tempNode; /臨時節點struct node *answer; /找到的路徑int num = 0;bool endKey;struct nodeint depth;int judgement_based;int style9;struct node *next;struct node *father;void updateData() /更新要判斷數據int i;cout<<"請輸入八數碼原始狀態："<<endl;for(i = 0;i < 9;i+)cin>>wholeStylei;cout<<"請輸入八數碼最終狀態："<<endl;for(i = 0;i < 9;i+)cin>>standard1i;int judge1(struct node