八數(shù)碼問題課程設(shè)計報告-1504092011-曹志

..XX學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告2016～2017學(xué)年第2學(xué)期課程數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計名稱八數(shù)碼問題求解學(xué)生姓名曹志學(xué)號1504092011專業(yè)班級軟件工程2班指導(dǎo)教師王駿2017年2月題目八數(shù)碼問題求解[問題描述]八數(shù)碼問題：在3×3的方格棋盤上,擺放著1到8這八個數(shù)碼,有1個方格是空的,其初始狀態(tài)如圖1所示,要求對空格執(zhí)行空格左移、空格右移、空格上移和空格下移這四個操作使得棋盤從初始狀態(tài)到目標狀態(tài)。圖一請使用一種盲目搜索算法〔深度或廣度優(yōu)先搜索和一種啟發(fā)式搜索方法編程求解八數(shù)碼問題,并對兩種算法的搜索步驟,搜索時間進行分析對比。問題分析和任務(wù)定義1.1問題分析由題目知給出一個初始狀態(tài)和一個目標狀態(tài),找出一種從初始轉(zhuǎn)變成目標狀態(tài)的移動步驟。所謂問題的一個狀態(tài)就是棋子在棋盤上的一種擺法。解八數(shù)碼問題實際上就是找出從初始狀態(tài)到達目標狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。要求分別采用廣度優(yōu)先搜索和啟發(fā)式搜索兩種方法對八數(shù)碼問題進行求解。且棋盤通過空格的上、下、右四種操作來改變狀態(tài)。所以需要解決的問題為每個狀態(tài)的表示和每個狀態(tài)變化的操作,設(shè)計出適合相應(yīng)搜索的數(shù)據(jù)結(jié)構(gòu),完成相應(yīng)算法思想。1.2任務(wù)定義<1>完成棋盤狀態(tài)表示。<2>完成空格上下左右移動操作變化的表示。<3>分別完成適應(yīng)于廣度優(yōu)先搜索,啟發(fā)式搜索的數(shù)據(jù)結(jié)構(gòu)設(shè)計。<4>得出兩種搜索的搜索路徑,及時間進行對比分析。數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計2.1廣度優(yōu)先搜索<1>廣度優(yōu)先搜索思想介紹從初始節(jié)點h開始逐層的對其進行擴展,并考察其其是否為目的節(jié)點,若不是將其放入待考察隊列中,在第n層節(jié)點沒有完全進行考察并擴展完成前,不對第n+1層進行擴展。隊列中節(jié)點總是按照先后順序進行排列,先進的排在前面,后進的排在后面。由此可知我們可以通過隊列的思想完成搜索,其具體搜索過程如下。1>初始化頭結(jié)點front,front=real;2>若front==null,問題無解,程序結(jié)束。3>對front指向的節(jié)點進行考察,若為目的節(jié)點程序結(jié)束。4>判斷front指向的節(jié)點的空格是否可以上下左右移動若可以,擴展節(jié)點置于隊尾。重復(fù)操作<2>。<2>數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計1>棋盤狀態(tài)的表示因為每一個棋盤狀態(tài)是靜止且確定的所以采取一個一維數(shù)組便可將其狀態(tài)表示出來,數(shù)組按照下標順序從左至右從上至下依次對應(yīng)?？崭窨捎闪銇肀硎?。圖二此狀態(tài)可表示為intnum[9]={2,5,4,3,0,7,1,8,6}。搜索結(jié)構(gòu)設(shè)計根據(jù)算法要求,需要對棋盤不斷的進行動態(tài)擴展,且盲目搜索產(chǎn)生的數(shù)據(jù)巨大,所以不能采用靜態(tài)鏈表或數(shù)組存儲,因此選擇采用動態(tài)鏈表來存儲搜索過程中的每一個狀態(tài)。因為搜索是根據(jù)一種狀態(tài)對其進行擴展,直至達到目的狀態(tài),由于要返回一個最優(yōu)路徑因此需要確定擴展關(guān)系,我選擇用一個*parent來記錄此關(guān)系。此時存儲結(jié)構(gòu)可由此圖表示圖三當擴展至目的狀態(tài)時可通過parent指針找到路徑。由此我們可以設(shè)置節(jié)點類型為typedefstructNode{structNode*parent;intnum[9];Node*next;}QNode；2.2啟發(fā)式搜索〔1啟發(fā)式搜索的思想介紹搜索算法可分為兩大類：無信息的搜索算法和有信息的搜索算法。無信息的搜索又稱盲目搜索,盲目搜索不考慮節(jié)點好壞,而對于八數(shù)碼問題的解決過程是有跡可循的,我們通過是否接近目標狀態(tài)來判斷節(jié)點的好壞,因此可以通過啟發(fā)式搜索中的A*算法來解決這個問題。簡單來說A*就是將估值函數(shù)分成兩個部分,一個部分是路徑價值,另一個部分是一般性啟發(fā)價值,合在一起算估整個結(jié)點的價值。在本實驗中使用A*算法求解。A*搜索是一種效的搜索算法,它把到達節(jié)點的耗散g<n>和從該節(jié)點到目標節(jié)點的消耗h<n>結(jié)合起來對節(jié)點進行評價：f<n>=g<n>+h<n>。由此設(shè)計如下把起始節(jié)點放到OPEN表中,并計算節(jié)點S的如果OPEN是空表,則失敗退出,無解；從OPEN表中選擇一個值最小的節(jié)點。如果有幾個節(jié)點值相同,當其中有一個為目標節(jié)點時,則選擇此目標節(jié)點；否則就選擇其中任一個節(jié)點作為節(jié)點；把節(jié)點從OPEN表中移出,并把它放入CLOSED的已擴展節(jié)點表中;如果是個目標節(jié)點,則成功退出,求得一個解；擴展節(jié)點,生成其全部后繼節(jié)點。對于的每一個后繼節(jié)點：計算；如果既不在OPEN表中,又不在CLOCED表中,則用估價函數(shù)把它添入OPEN表中。從加一指向其父節(jié)點的指針,以便一旦找到目標節(jié)點時記住一個解答路徑；如果已在OPEN表或CLOSED表中,則比較剛剛對計算過的和前面計算過的該節(jié)點在表中的值。如果新的較小,則<I>以此新值取代舊值。<II>從指向,而不是指向他的父節(jié)點。<III>如果節(jié)點在CLOSED表中,則把它移回OPEN表中。轉(zhuǎn)向〔2。流程圖如下圖四數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計由于搜索特點,采用的基礎(chǔ)存儲結(jié)構(gòu)和廣度優(yōu)先搜索相同,不同之處為啟發(fā)式搜索使用兩條鏈表,所以設(shè)計一個表結(jié)構(gòu),用來聲明兩條鏈表。節(jié)點結(jié)構(gòu)typedefstructNode{doubleg,f;structNode*parent;intnum[9];}Node；表結(jié)構(gòu)typedefstructStack{ Node*npoint;//指向狀態(tài)節(jié)點,相當于表節(jié)點的數(shù)據(jù)域。 structStack*next;}Stack；詳細設(shè)計和編碼3.1廣度優(yōu)先搜索〔1相關(guān)函數(shù)1空格移動函數(shù)intmove_up<intnum[]>;intmove_down<intnum[]>;intmove_left<intnum[]>;intmove_right<intnum[]>;以上移為例,找到0的位置將其與下標比其小三的值交換,且下標為0,1,2的數(shù)字不可移動。2搜索過程函數(shù)intbfs<intinit[],inttarget[]>；接收初始狀態(tài)和目的狀態(tài)總領(lǐng)搜索過程。intcansolve<intnum1[],intnum2[]>；判斷兩個數(shù)列的逆序數(shù)奇偶性,從而判斷八數(shù)碼問題是否可解voidget_num<QNode*node,inttemp[]>；將節(jié)點中的數(shù)組獲取出來。voidset_num<QNode*node,inttemp[]>；設(shè)置節(jié)點中數(shù)組的數(shù)據(jù)。voidprint<QNode*node>；輸出節(jié)點中信息〔2>算法偽碼輸入初始狀態(tài)數(shù)組unit,目標狀態(tài)數(shù)組targetIf<問題可解>While<隊頭指針非空時&&未找到目的節(jié)點>If<隊頭節(jié)點為目的節(jié)點>結(jié)束循環(huán)；Endif對隊頭節(jié)點進行擴展,將擴展節(jié)點加入隊尾；隊頭指針后移；EndwhileEndif3.2啟發(fā)式搜索設(shè)計〔1所用函數(shù)intEqual<Node*suc,Node*goal>；判斷節(jié)點是否相等,相等,不相等。Node*Belong<Node*suc,Lstack*list>判斷節(jié)點是否屬于OPEN表或CLOSED表,是則返回節(jié)點地址,否則返回空地址。voidPutinto<Node*suc,Lstack*list>把節(jié)點放入OPEN或CLOSED表中。doubleFvalue<Nodesuc,Nodegoal,floatspeed>計算f值。doubleDistance<Nodesuc,Nodegoal,inti>計算方格的錯位距離。intBelongProgram<Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed>判斷子節(jié)點是否屬于OPEN或CLOSED表并作出相應(yīng)的處理。intCanspread<Nodesuc,intn>判斷空格可否向該方向移動,表示空格向上向下向左向右移。voidSpreadchild<Node*child,intn>擴展child節(jié)點的字節(jié)點n表示方向表示空格向上向下向左向右移。intSpread<Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed>擴展后繼節(jié)點總函數(shù)。Node*Process<Lnode*org,Lnode*goal,Lstack*Open,Lstack*Closed,floatspeed>總執(zhí)行函數(shù)。voidqf<intinit[9],inttarget[9]>啟發(fā)式搜索總函數(shù)?！?搜索過程偽碼輸入：初始狀態(tài),目標狀態(tài)輸出：從初始狀態(tài)到目標狀態(tài)的一系列過程算法描述：Begin： 讀入初始狀態(tài)和目標狀態(tài),并計算初始狀態(tài)評價函數(shù)值f； 根據(jù)初始狀態(tài)和目標狀態(tài),判斷問題是否可解； If<問題可解> 把初始狀態(tài)加如open表中； While〔未找到解&&狀態(tài)表非空①在open表中找到評價值最小的節(jié)點,作為當前結(jié)點,；②判斷當前結(jié)點狀態(tài)和目標狀態(tài)是否一致,若一致,跳出循環(huán)；否則跳轉(zhuǎn)到③；③對當前結(jié)點,分別按照上、下、左、右方向移動空格位置來擴展新的狀態(tài)結(jié)點,并在并計算新擴展結(jié)點的評價值f并記錄其父節(jié)點若；④對于新擴展的狀態(tài)結(jié)點,判斷其是否重復(fù),若不重復(fù),把其加入到open表中；⑤把當前結(jié)點從open表中移至Close表； Endwhile Endif輸出結(jié)果； End上機調(diào)試過程4.1遇到的問題和分析〔1本次課程設(shè)計過程是兩種搜索方式分開開發(fā),因此在綜合在一起的時候兩種方式的代碼合在一起略顯雜糅,程序可讀性較差?！?在做啟發(fā)式搜索時,發(fā)現(xiàn)效率并未達到預(yù)期,查閱資料得知h值取得不好,沒有完全切合搜索規(guī)律,h值應(yīng)為每個方格到其正確位置的路徑之和,而我僅統(tǒng)計的是錯位之和同時發(fā)現(xiàn)若h值取得越大其搜索速度越快單難以保證得出的是最優(yōu)解。因此我設(shè)計了一個系數(shù)1000來進行加速?！?在設(shè)計廣度優(yōu)先搜索時指針操作出現(xiàn)失誤,導(dǎo)致進度一度停滯,后放棄改為數(shù)組操作才完成程序4.2時空效率分析廣度優(yōu)先搜索是一種十分浪費空間的搜索方法,有時會陷入死循環(huán)。同時在時間效率上廣度優(yōu)先搜索效率不穩(wěn)定,若搜索深度過大則時間效率異常緩慢。但可確定找到最優(yōu)解。啟發(fā)式搜索效率較穩(wěn)定,當搜素深度較小時時間效率不及廣度優(yōu)先但在深度搜索表現(xiàn)優(yōu)異,同時啟發(fā)式搜索有選擇的創(chuàng)建節(jié)點,大大節(jié)省空間效率。測試結(jié)果及其分析圖五圖六圖七圖八圖九圖十圖十一圖十二圖十〔1實驗結(jié)果實驗數(shù)據(jù)廣度優(yōu)先啟發(fā)式搜索時間最優(yōu)節(jié)點數(shù)時間最優(yōu)節(jié)點數(shù)初始狀態(tài)283164705目標狀態(tài)1238047654ms6109ms6初始狀態(tài)254307186目標狀態(tài)123804765無解0無解無解無解初始狀態(tài)123456780目標狀態(tài)1234056784399ms15196ms15初始狀態(tài)123456780目標狀態(tài)01382547648ms9128ms9初始狀態(tài)123456780目標狀態(tài)12304567812537ms16300ms28初始狀態(tài)183265470目標狀態(tài)836107245112ms11347ms25表一〔2結(jié)果分析。當最優(yōu)解步驟較小時,廣度優(yōu)先時間效能更好。造成這種現(xiàn)象的原因為當搜素深度小時,啟發(fā)式搜索由于有較多的查重和鏈表操作導(dǎo)致時間性能下降,而當搜索深度較深時啟發(fā)式搜索對節(jié)點優(yōu)劣的考察使其在時間上展現(xiàn)出較大優(yōu)勢。但啟發(fā)式搜索可能無法獲取最優(yōu)解。用戶使用說明在輸入八數(shù)碼狀態(tài)時將八數(shù)碼上數(shù)字從上至下從左至右,依次輸入其中空格用0代替,且每個數(shù)字用空格隔開。參考文獻[1]錢瑩．基于廣度優(yōu)先的八數(shù)碼問題解決方案．電腦學(xué)習(xí),2008:45-46[2]張鴻．人工智能中求解八數(shù)碼問題算法與實現(xiàn)．軟件導(dǎo)刊,2009:62-64附錄#include"stdio.h"#include<stdlib.h>#include<time.h>#include<math.h>#include<process.h>typedefstructNode{structNode*parent;doublef,g;intnum[9];//intstep;Node*next;}QNode,*Lnode;typedefstructStack{//OPENCLOSED表結(jié)構(gòu)體 Node*npoint; structStack*next;}Stack,*Lstack;intcansolve<intnum1[],intnum2[]>;voidinput<intnum[]>;intmove_up<intnum[]>;intmove_down<intnum[]>;intmove_left<intnum[]>;intmove_right<intnum[]>;voidget_num<QNode*node,inttemp[]>;voidset_num<QNode*node,inttemp[]>;voidprint<QNode*node>;intisequal<QNode*node,inttemp[]>;intbfs<intinit[9],inttarget[9]>;Node*Minf<Lstack*Open>;Node*Belong<Node*suc,Lstack*list>;voidPutinto<Node*suc,Lstack*list>;intEqual<Node*suc,Node*goal>;intCanspread<Nodesuc,intn>;voidSpreadchild<Node*child,intn>;voidPutinto<Node*suc,Lstack*list>;doubleDistance<Nodesuc,Nodegoal,inti>;voidSpreadchild<Node*child,intn>;intBelongProgram<Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed>;Node*Process<Lnode*org,Lnode*goal,Lstack*Open,Lstack*Closed,floatspeed>;voidqf<intinit[9],inttarget[9]>;intmain<>{ intinit[9],target[9];l: printf<"輸入初始狀態(tài):\n">;input<init>;printf<"輸入目標狀態(tài):\n">;input<target>;if<cansolve<init,target>> {printf<"使用廣度優(yōu)先進行搜索:\n">; bfs<init,target>; printf<"使用啟發(fā)式進行搜索:\n">; qf<init,target>;}else{ printf<"無解">;}getchar<>;system<"cls">;gotol;}Node*Minf<Lstack*Open>{//選取OPEN表上f值最小的節(jié)點,返回該節(jié)點地址 Lstacktemp=<*Open>->next,min=<*Open>->next,minp=<*Open>; Node*minx;while<temp->next!=NULL> { if<<temp->next->npoint->f><<min->npoint->f>> { min=temp->next; minp=temp; } temp=temp->next; } minx=min->npoint; temp=minp->next; minp->next=minp->next->next; free<temp>; returnminx;}intEqual<Node*suc,Node*goal>{//判斷節(jié)點是否相等,相等,不相等 for<inti=0;i<9;i++> if<suc->num[i]!=goal->num[i]>return0;return1;}Node*Belong<Node*suc,Lstack*list>{//判斷節(jié)點是否屬于OPEN表或CLOSED表,是則返回節(jié)點地址,否則返回空地址 Lstacktemp=<*list>->next; if<temp==NULL>returnNULL; while<temp!=NULL> { if<Equal<suc,temp->npoint>>returntemp->npoint; temp=temp->next; } returnNULL;}voidPutinto<Node*suc,Lstack*list>{//把節(jié)點放入OPEN或CLOSED表中Stack*temp; temp=<Stack*>malloc<sizeof<Stack>>; temp->npoint=suc; temp->next=<*list>->next; <*list>->next=temp;}///////////////計算f值部分-開始//////////////////////////////doubleFvalue<Nodesuc,Nodegoal,floatspeed>{//計算f值 doubleDistance<Node,Node,int>; doubleh=0; for<inti=1;i<=8;i++> h=h+Distance<suc,goal,i>; returnh*speed+suc.g;//f=h+g;<speed值增加時搜索過程以找到目標為優(yōu)先因此可能不會返回最優(yōu)解>}doubleDistance<Nodesuc,Nodegoal,inti>{//計算方格的錯位距離 intk,h1,h2; for<k=0;k<9;k++> { if<suc.num[k]==i>h1=k; if<goal.num[k]==i>h2=k; } returndouble<fabs<h1/3-h2/3>+fabs<h1%3-h2%3>>;}///////////////計算f值部分-結(jié)束/////////////////////////////////////////////////////擴展后繼節(jié)點部分的函數(shù)-開始/////////////////intBelongProgram<Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed>{//判斷子節(jié)點是否屬于OPEN或CLOSED表并作出相應(yīng)的處理 Node*temp=NULL; intflag=0; if<<Belong<*suc,Open>!=NULL>||<Belong<*suc,Closed>!=NULL>> { if<Belong<*suc,Open>!=NULL>temp=Belong<*suc,Open>; elsetemp=Belong<*suc,Closed>; if<<<*suc>->g><<temp->g>> { temp->parent=<*suc>->parent; temp->g=<*suc>->g; temp->f=<*suc>->f; flag=1; } } else { Putinto<*suc,Open>; <*suc>->f=Fvalue<**suc,goal,speed>; } returnflag;}intCanspread<Nodesuc,intn>{//判斷空格可否向該方向移動,,,表示空格向上向下向左向右移 inti,flag=0; for<i=0;i<9;i++> if<suc.num[i]==0>break; switch<n> { case1: if<i/3!=0>flag=1;break; case2: if<i/3!=2>flag=1;break; case3: if<i%3!=0>flag=1;break; case4: if<i%3!=2>flag=1;break; default:break; } returnflag;}voidSpreadchild<Node*child,intn>{//擴展child節(jié)點的字節(jié)點n表示方向,,,表示空格向上向下向左向右移 inti,loc,temp; for<i=0;i<9;i++> child->num[i]=child->parent->num[i]; for<i=0;i<9;i++> if<child->num[i]==0>break; if<n==0> loc=i%3+<i/3-1>*3; elseif<n==1> loc=i%3+<i/3+1>*3; elseif<n==2> loc=i%3-1+<i/3>*3; else loc=i%3+1+<i/3>*3; temp=child->num[loc]; child->num[i]=temp; child->num[loc]=0;}intSpread<Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed>{//擴展后繼節(jié)點總函數(shù) inti; Node*child; for<i=0;i<4;i++> { if<Canspread<**suc,i+1>>//判斷某個方向上的子節(jié)點可否擴展 { child=<Node*>malloc<sizeof<Node>>;//擴展子節(jié)點 child->g=<*suc>->g+1;//算子節(jié)點的g值 child->parent=<*suc>;//子節(jié)點父指針指向父節(jié)點 Spreadchild<child,i>;//向該方向移動空格生成子節(jié)點 if<BelongProgram<&child,Open,Closed,goal,speed>>// 判斷子節(jié)點是否屬于OPEN或CLOSED表并作出相應(yīng)的處理 free<child>; //step++; } } return1;}///////////////////////擴展后繼節(jié)點部分的函數(shù)-結(jié)束//////////////////////////////////Node*Process<Lnode*org,Lnode*goal,Lstack*Open,Lstack*Closed,floatspeed>{//總執(zhí)行函數(shù) while<1> { if<<*Open>->next==NULL>returnNULL;//判斷OPEN表是否為空,為空則失敗退出 Node*minf=Minf<Open>;//從OPEN表中取出f值最小的節(jié)點 Putinto<minf,Closed>;//將節(jié)點放入CLOSED表中 if<Equal<minf,*goal>>returnminf;//如果當前節(jié)點是目標節(jié)點,則成功退出Spread<&minf,Open,Closed,**goal,speed>; //當前節(jié)點不是目標節(jié)點時擴展當前節(jié)點的后繼節(jié)點 }}/*intShownum<Node*result>{//遞歸顯示從初始狀態(tài)到達目標狀態(tài)的移動方法 if<result==NULL>return0; else { intn=Shownum<result->parent>; for<inti=0;i<3;i++> { printf<"\n">; for<intj=0;j<3;j++> { if<result->num[i*3+j]!=0> printf<"%d",result->num[i*3+j]>; elseprintf<"">; } } printf<"\n">; returnn+1; }}*/voidqf<intinit[9],inttarget[9]>{LstackOpen=<Stack*>malloc<sizeof<Stack>>; Open->next=NULL; LstackClosed=<Stack*>malloc<sizeof<Stack>>; Closed->next=NULL; Node*org=<Node*>malloc<sizeof<Node>>; Node*p; org->parent=NULL;//初始狀態(tài)節(jié)點 org->f=1; org->g=1; intcount=0;// org->step=1;Node*goal=<Node*>malloc<sizeof<Node>>;//目標狀態(tài)節(jié)點 Node*result; set_num<org,init>; set_num<goal,target>; floatspeed=1000;//speed搜索速度// charc; doublenow; now=<double>clock<>; //printf<"請輸入搜索速度<速度越高越無法保證結(jié)果是最優(yōu)解>:">; //scanf<"%f",&speed>; // while<<c=getchar<>>!=10>; // printf<"搜索中,請耐心等待<如果您覺得時間太久請重新執(zhí)行程序并輸入更快的速度,默認值為>......\n">; Putinto<org,&Open>; result=Process<&org,&goal,&Open,&Closed,speed>;//進行剩余的操作print<result> for<p=result;p!=NULL;p=p->parent>{print<p>; printf<"--^--\n">; //printf<"搜索g:%f",p->g>; count++;} printf<"搜索所用時間:%fms,得出路徑所需節(jié)點%d",<double>clock<>-now,count>; printf<"\n">; printf<"PressEnterkeytoexit!">; //while<<c=getchar<>>!=10>;}intexist<QNode*node,inttemp[]>;intbfs<intinit[],inttarget[]>{inttemp[9];intfind=0; doublenow=0; intstep=1,count=1;QNode*front,*rear,*new_node,*p;//printf<"輸入初始狀態(tài):\n">;//input<init>;//printf<"輸入目標狀態(tài):\n">;//input<target>;if<!cansolve<init,target>>{printf<"不能實現(xiàn)\n">;return0;} now=<double>clock<>;front=<QNode*>malloc<sizeof<QNode>>;set_num<front,init>;front->parent=NULL;front->next=NULL;rear=front;while<front!=NULL&&!find>{if<isequal<front,target>>{find=1;break;} /*get_num<front,temp>; if<move_up<temp>> { if<equal<temp,target>> { new_node=<QNode*>malloc<sizeof<QNode>>;set_num<new_node,temp>;new_node->parent=front;new_node->next=NULL;rear->next=new_node;rear=new_node; } }*/get_num<front,temp>;if<move_up<temp>&&!exist<front,temp>>{new_node=<QNode*>malloc<sizeof<QNode>>;set_num<new_node,temp>;new_node->parent=front;new_node->next=NULL;rear->next=new_node;rear=new_node; step++;}get_num<front,temp>;if<move_left<temp>&&!exist<front,temp>>{new_node=<QNode*>malloc<sizeof<QNode>>;set_num<new_node,temp>;new_node->parent=front;new_node->next=NULL;rear->next=new_node;rear=new_node; step++;}get_num<front,temp>;if<move_down<temp>&&!exist<front,temp>>{new_node=<QNode*>malloc<sizeof<QNode>>;set_num<new_node,temp>;new_node->parent=front;new_node->next=NULL;rear->next=new_node;rear=new_node; step++;}get_num<front,temp>;if<move_right<temp>&&!exist<front,temp>>{new_node=<QNode*>malloc<sizeof<QNode>>;set_num<new_node,temp>;new_node->parent=front;new_node->next=NULL;rear->next=new_node;rear=new_node; step++;}front=front->next;count++;}if<find>{ count=0;for<p=front;p!=NULL;p=p->parent>{print<p>; printf<"--^--\n">; count++;} printf<"共花費時間%.4fms,得出最優(yōu)解共需%d個節(jié)點,\n",<double>clock<>-now/*/CLOCKS_PER_SEC*/,count>;}}intcansolve<intnum1[],intnum2[]>{inti,j;intsum1=0,sum2=0;for<i=0;i<9;i++>for<j=0;j<i;j++>{if<num1[j]>num1[i]&&num1[i]!=0>++sum1;if<num2[j]>num2[i]&&num2[i]!=0>++sum2;}if<sum1%2==sum2%2>return1;elsereturn0;}intequal<intnum1[],intnum2[]>{ for<inti=0;i<9;i++> { if<num1[i]!=num2[i]> {return0;} } return1;}voidinput<intnum[]>{ inti=0,j=0,flag=0; charc; while<i<9> { while<<<c=getchar<>>!=10>> { if<c==''> { if<flag>=0>flag=0; } elseif<c>='0'&&c<='8'> { if<flag==0> { num[i]=<c-'0'>; flag=1; for<j=0;j<i;j++> if<num[j]==num[i]>flag=-2; i++; } // elseif<flag>=0>flag=-1; } elseif<flag>=0>flag=-1; } if<flag<0||i<9> { if<flag<0> { if<flag==-1>printf<"含有非法字符或數(shù)字!\n請重新輸入:\n">; elseif<flag==-2>printf<"輸入的數(shù)字有重復(fù)!\n請重新輸入:\n">; } elseif<i<9>