【文章內(nèi)容簡(jiǎn)介】 以下代碼完成這部分功能 。 graphmf[0][3]=s[0][0]。 //魔方上面狀態(tài)圖的構(gòu)建 graphmf[0][4]=s[0][1]。 graphmf[0][5]=s[0][2]。 graphmf[1][3]=s[0][3]。 graphmf[1][4]=s[0][4]。 graphmf[1][5]=s[0][5]。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 10 graphmf[2][3]=s[0][6]。 graphmf[2][4]=s[0][7]。 graphmf[2][5]=s[0][8]。 以上這部分代碼就是將每一個(gè)“大面”中的狀態(tài)拷貝到九個(gè)數(shù)組元素中去，也就是對(duì)應(yīng)的九個(gè)“小面”。 當(dāng)魔方狀態(tài)文件被成功的接收以后，并且，被保存到魔方狀態(tài)圖數(shù)組中后，接下來(lái)就是將這個(gè)狀態(tài)拷貝到兩個(gè)副本中去，由于第一個(gè)副本的拷貝并沒(méi)有在這個(gè)模塊中出現(xiàn)，所以，先不給出這部分的代碼。這個(gè)副本的拷貝是在 的 change()函數(shù)中完成，代碼如下： void change() { int i,j。 for(i=0。i12。i++) for(j=0。j9。j++) graphsta[i][j]=graphmf[i][j]。 } 下面是第二個(gè)副本對(duì)魔方上面狀態(tài)的拷貝： for(i=0。i12。i++) for(j=0。j9。j++) graphmf1[i][j]=graphmf[i][j]。 到這里這個(gè)模塊的主要問(wèn)題基本已經(jīng)解決了，當(dāng)然，由于完成的功能比較簡(jiǎn)單，只是簡(jiǎn)單 的給出了代碼，并簡(jiǎn)單的說(shuō)明。 下面在給出魔方狀態(tài)的構(gòu)造圖之前，先對(duì)圖中的標(biāo)記進(jìn)行簡(jiǎn)單的說(shuō)明， 表格中的行號(hào)和列號(hào)分別代表數(shù)組中的行標(biāo)和列標(biāo)。 U 代表魔方上面， 為 紅色； L 代表魔方左面， 為 綠色； F 代表魔方前面， 為 黃色； R 代表魔方右面， 為 藍(lán)色 ； D 代表魔方下面， 為 橙色； B 代表魔方后面， 為 白色。 以下就是魔方狀態(tài)的構(gòu)造圖 （ 表 31 魔方狀態(tài)構(gòu)造圖 ） ，在程序中一個(gè)很重要的部分。 程序執(zhí)行模塊 程序執(zhí)行模塊 ()。 這個(gè)模塊被設(shè)計(jì)成界面的打印和對(duì)用戶的輸入執(zhí)行相應(yīng)的操作，同時(shí)，它也是整個(gè)程序執(zhí)行的第一部 分，其它的函數(shù)調(diào)用都是在它的 search_begin()函數(shù)中來(lái)實(shí)現(xiàn)的 [10]。 在 search_begin()函數(shù)被主函數(shù)調(diào)用后，它首先調(diào)用自身的 choice()函數(shù)來(lái)打印出界面，同時(shí)等待接收用戶的輸入，當(dāng)用戶輸入為人工解決的時(shí)候，則給出魔方相應(yīng)旋轉(zhuǎn)的操作方法，例如：前面順時(shí)針操作對(duì)應(yīng)字符串 [f+]。其它的操作方法會(huì)東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 11 在用戶選擇界面中有相應(yīng)的提示。并且，會(huì)對(duì)錯(cuò)誤的輸入給出相應(yīng)的提示。每當(dāng)用戶選擇自己操作的時(shí)候，每輸入一次操作字符串，程序就會(huì)調(diào)用 的相應(yīng)的對(duì)魔方狀態(tài)圖操作的函數(shù)，例如： 輸入 [f+]，則調(diào)用 front_1()函數(shù)，這個(gè)函數(shù)主要是通過(guò)對(duì)魔方狀態(tài)圖中的各個(gè)面的顏色以及它在數(shù)組中的存儲(chǔ)位置的變換來(lái)達(dá)到動(dòng)態(tài)表示魔方旋轉(zhuǎn)后的正確的狀態(tài)的目的。然后，調(diào)用 display_mf()函數(shù)，來(lái)顯示旋轉(zhuǎn)后魔方的狀態(tài)圖 [11]。關(guān)于 front_1()函數(shù)會(huì)在。 在用戶輸入旋轉(zhuǎn)字符串，并且程序執(zhí)行相應(yīng)的操作后，程序調(diào)用 的 para()函數(shù)，來(lái)判斷魔方是否被用戶解出，如果解出則給出相應(yīng)的提示，并且返 回到 searchbegin()函數(shù)的調(diào)用處，也就是主函數(shù)中去。然后，執(zhí)行主函數(shù)中其它的操作。如果，魔方還沒(méi)有被用戶解決，則在給出相應(yīng)操作 的的顯示后，程序自動(dòng)等待用戶的下一次輸入。直到魔方被解決，或者 用戶在程序的執(zhí)行過(guò)程中選擇了幫助操作。 當(dāng)用戶選擇了幫助操作的時(shí)候，則程序自動(dòng)跳出接收用戶操作 的循環(huán)，轉(zhuǎn)向執(zhí)行魔方的自動(dòng)求解程序。在這里有一點(diǎn)需要說(shuō)明，由于 魔方的旋轉(zhuǎn)操作都是對(duì)graphsta[12][9]這個(gè)數(shù)組的操作，并且，在自動(dòng)求解的過(guò)程中也要用到這個(gè)數(shù)組，但是，由于用戶一開(kāi)始并沒(méi)有選擇自動(dòng)求解，所以，數(shù) 組中的狀態(tài)并不是魔方狀態(tài)圖的初始狀態(tài)，所以，需要將 graphsta這個(gè)數(shù)組在次轉(zhuǎn)換到魔方狀態(tài)圖的初始狀態(tài) [12]。然后，開(kāi)始電腦自動(dòng)求解。 這部分的功能也十分簡(jiǎn)單，實(shí)現(xiàn)的過(guò)程也不是很復(fù)雜，只是對(duì)輸入的判斷和對(duì)其它函數(shù)的調(diào)用，這里不給出它的源代碼。 表 31 魔方狀態(tài)構(gòu)造圖 0 1 2 3 4 5 6 7 9 0 角塊 5 邊塊 6 角塊 6 1 邊塊 5 U（紅） 邊塊 7 2 角塊 1 邊塊 2 角塊 2 3 角塊 5 邊塊 5 角塊 1 角塊 1 邊塊 2 角塊 2 角塊 2 邊塊 7 角 塊 6 4 邊塊 12 L（綠） 邊塊 1 邊塊 1 F（黃） 邊塊 3 邊塊 3 R（藍(lán)） 邊塊 8 5 角塊 8 邊塊 11 角塊 4 角塊 4 邊塊 4 角塊 3 角塊 3 邊塊 9 角塊 7 6 角塊 4 邊塊 4 角塊 3 7 邊塊 11 D（橙） 邊塊 9 8 角塊 8 邊塊 10 角塊 7 9 角塊 5 邊塊 6 角塊 6 10 邊塊 12 B（白） 邊塊 8 11 角塊 8 邊塊 10 角塊 7 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 12 旋轉(zhuǎn)操作模塊 旋轉(zhuǎn)操作模塊 ()。 這個(gè)模 塊的設(shè)計(jì)可以說(shuō)是程序中的一個(gè)比較重要的環(huán)節(jié)，因?yàn)椋挥袑?duì)魔方狀態(tài)圖操作的準(zhǔn)確才能保證求解的順利完成，下面對(duì)這不分加以詳細(xì)的說(shuō)明。 這個(gè)部分主要是為了響應(yīng)對(duì)魔方采取一定的旋轉(zhuǎn)操作后，魔方狀態(tài)圖中的顏色以及它們?cè)跀?shù)組中位置的變化?？梢哉f(shuō)，這是個(gè)比較復(fù)雜的過(guò)程，因?yàn)?，這個(gè)部分的實(shí)現(xiàn)沒(méi)有什么復(fù)雜的操作和特殊的結(jié)構(gòu)， 只是 數(shù)組內(nèi)部各個(gè)數(shù)據(jù)間的變換，需要的是細(xì)心和耐心。 這里數(shù)組間數(shù)據(jù)的變換關(guān)系都與前面給出的魔方狀態(tài)構(gòu)造圖有關(guān)，由于魔方有六個(gè)面，每個(gè)面都有兩種旋轉(zhuǎn)方式，順時(shí)針旋轉(zhuǎn)和逆時(shí)針旋轉(zhuǎn)。所以說(shuō)，對(duì)魔方應(yīng)有 12種操作 方式，所以，在這里為每種操作都定義了一個(gè)相應(yīng)的函數(shù)，這個(gè)函數(shù)的功能就是完成在這種操作下，魔方狀態(tài)圖中顏色應(yīng)有的變換，以準(zhǔn)確的表現(xiàn)出當(dāng)前魔方的狀態(tài)。這里所有的操作都是對(duì)數(shù)組 graphsta的操作。這十二個(gè)函數(shù)分別是： front_1()，前面順時(shí)針操作； front_2()，前面逆時(shí)針操作； back_1()，后面順時(shí)針操作； back_2()，后面逆時(shí)針操作； up_1()，上面順時(shí)針操作； up_2()，上面逆時(shí)針操作； down_1()，下面順時(shí)針操作； down_2()，下面逆時(shí)針操作； left_1()，左面順時(shí)針操 作； left_2()，左面逆時(shí)針操作； right_1()，右面順時(shí)針操作； right_2()，右面逆時(shí)針操作 [13]。 下面我以 front_1()操作來(lái)簡(jiǎn)單的說(shuō)明一下數(shù)組間的數(shù)據(jù)是如何交換的，因?yàn)椋@部分與我前面給出的狀態(tài)圖有十分密切的關(guān)系，所以，一定要理解前面的狀態(tài)圖的基礎(chǔ)上來(lái)解決這個(gè)問(wèn)題。下面我給出這個(gè)函數(shù)執(zhí)行過(guò)程中狀態(tài)圖中數(shù)據(jù)交換的過(guò)程，也就是這個(gè)函數(shù)實(shí)現(xiàn)的源代碼，在代碼中我都標(biāo)上了注釋，對(duì)于這個(gè)問(wèn)題的理解會(huì)很有幫助。其中在注釋中的數(shù)字都為我在魔方狀態(tài)圖中標(biāo)出的那些數(shù)字。例如：在對(duì)角塊的操作的過(guò)程中 12就為將角塊 1中的顏色（也就是數(shù)組的數(shù)據(jù)）送到角塊 2中去。對(duì)于邊塊的操作與角塊一樣，這里就不多說(shuō)。 void front_1() { char temporary0[3]。 //存儲(chǔ)角塊的臨時(shí)變量 char temporary1[2]。 //存儲(chǔ)邊塊的臨時(shí)變量 /*對(duì)角塊操作 */ temporary0[0]=graphsta[3][5]。 //存儲(chǔ) 2到臨時(shí)變量 temporary0[1]=graphsta[3][6]。 temporary0[2]=graphsta[2][5]。 //12 graphsta[3][5]=graphsta[3][3]。 東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 13 graphsta[3][6]=graphsta[2][3]。 graphsta[2][5]=graphsta[3][2]。 //41 graphsta[3][3]=graphsta[5][3]。 graphsta[2][3]=graphsta[5][2]。 graphsta[3][2]=graphsta[6][3]。 //34 graphsta[5][3]=graphsta[5][5]。 graphsta[5][2]=graphsta[6][5]。 graphsta[6][3]=graphsta[5][6]。 //23 graphsta[5][5]=temporary0[0]。 graphsta[6][5]=temporary0[1]。 graphsta[5][6]=temporary0[2]。 /*對(duì)邊塊操作 */ temporary1[0]=graphsta[3][4]。 //存儲(chǔ) 2到臨時(shí)變量 temporary1[1]=graphsta[2][4]。 //12 graphsta[3][4]=graphsta[4][3]。 graphsta[2][4]=graphsta[4][2]。 //41 graphsta[4][3]=graphsta[5][4]。 graphsta[4][2]=graphsta[6][4]。 //34 graphsta[5][4]=graphsta[4][5]。 graphsta[6][4]=graphsta[4][6]。 //23 graphsta[4][5]=temporary1[0]。 graphsta[4][6]=temporary1[1]。 } 相信看過(guò)以上的代碼后，會(huì)很容易理解這個(gè)模塊的功能和實(shí)現(xiàn)的方法。由于，其它函數(shù)的操作都與上面給出的例子大體相同，在這里就不過(guò)多的說(shuō)明。這些就需要對(duì)魔方的平面狀態(tài)有一定的了解，只有這樣才能準(zhǔn)確的想象出魔方每一次旋轉(zhuǎn)后數(shù)組中的數(shù)據(jù)交換的過(guò)程。 在交換的時(shí)候，為了保證數(shù)據(jù)不丟失，應(yīng)該將一個(gè)角塊或邊塊的數(shù)據(jù)首先存儲(chǔ)到一個(gè)變量中去，然后在對(duì)這個(gè)角塊或邊塊中的數(shù)據(jù)進(jìn)行替換。這一切上面的代碼都已經(jīng)寫(xiě)的很清楚。 在這里我們還有兩個(gè)函數(shù)并沒(méi)有提到過(guò) ，一個(gè)是 left_front()，實(shí)現(xiàn)的操作是，leftfrontrightbackleft的各個(gè)面間的數(shù)據(jù) 進(jìn)行 轉(zhuǎn)換， 而 另 外 一個(gè)實(shí)現(xiàn)的操作是，front_down()，實(shí)現(xiàn) frontdownbackupfront的各個(gè)面間的數(shù)據(jù)轉(zhuǎn)換 [14]。這些和我給出的例子的操作是一樣的，這里就不多說(shuō)。這兩個(gè)函數(shù)的 定義主要是為了和專家東北石油大學(xué)華瑞學(xué)院本科生畢業(yè)設(shè)計(jì)（論文） 14 系統(tǒng)的融合，因?yàn)樵凇鞍私欠ā敝杏羞@樣的操 作 。 搜索模塊 搜索模塊 ()。 這個(gè)模塊在整個(gè)魔方求解的過(guò)程中是十分重要的一個(gè)模塊，主要是實(shí)現(xiàn)在魔方復(fù)原的第一階段的搜索，對(duì)魔方狀態(tài)圖的搜索。這是程序設(shè)計(jì)中的一個(gè)難點(diǎn)，因?yàn)檫@里涉及到了搜索的方法和一些數(shù)據(jù)結(jié)構(gòu)的問(wèn)題。 首先，談?wù)勊阉鞯膯?wèn)題。 就像在概述中提到的那樣，在魔方求解的問(wèn)題中盲目的搜索是起不到任何作用的，必須采用專家系統(tǒng)。但在這里我先不討論專家系統(tǒng)的問(wèn)題，就想對(duì)搜索的方法和如何優(yōu)化搜索過(guò)程進(jìn)行說(shuō)明。 搜索方法采用的 是 A＊ 算法。這是一個(gè)比較通用的圖的搜索算法，下面給出它具體的定義和實(shí)現(xiàn)方法。 生成一個(gè)只包含開(kāi)始接點(diǎn) n的搜索圖 G，把 n放在一個(gè)叫 OPEN的列表上。 (1)生成一個(gè)列表 CLOSED，它的初始值為空。 (2)如果 OPEN為空，則失敗退出。 (3)選擇 OPEN上的第一個(gè)結(jié)點(diǎn)，把它從 OPEN中移入 CLOSED，稱該結(jié)點(diǎn)為 n1。 (4)如果 n1是目標(biāo)結(jié)點(diǎn)，順著 G中，從 n1到 n的指針找到一條路徑，獲得解決方案，成功退出（該指針定義了一個(gè)搜索樹(shù)，在第七步建立）。 (5)擴(kuò)展結(jié)點(diǎn) n1，生成其后繼結(jié)點(diǎn)集 M，在 G中， n1的祖先 不能在 M中。在 G中安置 M的成員，使它們成為 n1的后繼。 (6)從 M的每一個(gè)不在 G中的成員建立一個(gè)指向 n1的指針。把 M的這些成員加到OPEN中。對(duì) M的每一個(gè)已在 OPEN中或 CLOSED中的成員 m，如果到目前為止找到的到達(dá) m的最好路徑通過(guò) n1，就把它的指針指向 n1。對(duì)已在 CLOSED中的 M的每一個(gè)成員，重定向它在 G中的每一個(gè)后繼，以使它們順著到目前為止發(fā)現(xiàn)的最好的路徑指向它們的祖先。 (7)重排 OPEN表。 (8)返回第 3步 。 在本程序中的搜索并沒(méi)有嚴(yán)格的按照這個(gè)算法，但也是受到這個(gè)算法的啟發(fā)。 在搜索的問(wèn)題中 ，我想先談?wù)勱P(guān)于結(jié)點(diǎn)的擴(kuò)展問(wèn)題。由于魔方有六個(gè)面，每個(gè)面有兩種操作，這在前面提過(guò)，一共是 12種旋轉(zhuǎn)方式。所以，在每當(dāng)一個(gè)結(jié)點(diǎn)（這里的結(jié)點(diǎn)指的就是魔方狀態(tài)圖）要擴(kuò)展的時(shí)候，就要分別對(duì)同一結(jié)點(diǎn)采取 12種不同的操作，然后，判斷是否找到需要的狀態(tài)。下面給出它的擴(kuò)展圖，只是兩個(gè)結(jié)點(diǎn)的擴(kuò)展，其它的由省略號(hào)表示。 東北石油大學(xué)華瑞學(xué)院本