【文章內(nèi)容簡介】 結(jié)構(gòu)排列，再進(jìn)行搜索。一般解空間構(gòu)造成為為樹狀結(jié)構(gòu)，用深度優(yōu)先的策略搜索，一般有兩種方式：，找到解就停止。，則需做“樹的遍歷”找到所有解?；厮莘ǖ幕咀龇ㄊ撬阉鳎蚴且环N組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索。回溯法是一種搜索算法，其基本思路是：在一個(gè)問題中，根據(jù)題意給出的邊界條件劃定出所有可能解的范圍（稱為可能解），根據(jù)題意確定出約束條件。利用程序順次在所有可能解中搜索時(shí)按照深度搜索的方式進(jìn)行。即在第一層選定一個(gè)滿足約束條件的解，然后以該可能解為出發(fā)點(diǎn)，搜索第二層的一個(gè)可能解（試探）。如果搜索到第二層的一個(gè)可能解，則繼續(xù)搜索第三層得一個(gè)可能解。依次類推，直到所有層得可能解都被找到，則得到了該問題的一個(gè)完整解。如果第二層所有的肯可能解都不滿足約束條件，則返回第一層，放棄原有的可能解，使用第一層的下一個(gè)可能解（回溯）。一次類推，尋找第二層的一個(gè)可能解?；厮莘ㄏ鄬?duì)于其他窮舉的特點(diǎn)在于，不必把問題的每一層的所有可能解都遍歷一遍，只要當(dāng)前的可能解不滿足約束條件就拋棄該解，尋求下一個(gè)可能解，而不必求解其余的下層解。當(dāng)當(dāng)前層得所有可能解都不滿足約束條件，則回溯到上一層，拋棄上一層的當(dāng)前可能解。從以上分析中結(jié)合數(shù)獨(dú)問題的規(guī)則，得出數(shù)獨(dú)問題的約束條件為：每一格的數(shù)值范圍僅限 19每一格內(nèi)的數(shù)字在當(dāng)前行不允許重復(fù)每一格內(nèi)的數(shù)字在當(dāng)前列不允許重復(fù)每一格內(nèi)的數(shù)字在當(dāng)前小宮格內(nèi)不允許重復(fù)由此，回溯法通過約束條件的篩選，在所有解中除掉不可能的解，從而獲得問題的一個(gè)或者全部解。具體實(shí)現(xiàn)方法和代碼會(huì)在后面章節(jié)詳細(xì)說明。整個(gè)游戲共由 10 個(gè)類組成，如圖 311 所示是游戲的類結(jié)構(gòu)。游戲的SuDoKuMIDlet 類負(fù)責(zé)保持 display 對(duì)象，確保在各個(gè)屏幕之間切換。所切換的屏幕包括閃屏，菜單，游戲畫布，游戲設(shè)置表單和游戲說明表單。游戲線程和屏幕繪制由 SuDoKuCanvas 畫布類實(shí)現(xiàn)，屏幕繪制包括背景，宮格和數(shù)字，游戲循環(huán)每隔 50ms 繪制一次。游戲聲效由 SoundEffects 類實(shí)現(xiàn)。游戲控制類 SuDoKuModel 銜接了游戲畫布，游戲存儲(chǔ)和游戲邏輯各個(gè)功能單元。使用這種結(jié)構(gòu)能很好地保持各個(gè)類得抽象性和封裝性，例如，邏輯類負(fù)責(zé)保持宮格數(shù)據(jù)，判斷勝負(fù)；而畫布類只負(fù)責(zé)繪制和接收鍵盤事件；游戲控制類起到中樞神經(jīng)的功能。S u D o K u M I D l e t S p l a s h S c r e e nM e n u L i s tS u D o K u C a n v a sO p t i o n S c r e e nI n s t r u c t i o n s S c r e e nS u D o K u M o d e lS o u n d E f f e c t sS u D o K u L o g i cS u D o K u S t o r e主類游戲閃屏游戲菜單畫布游戲設(shè)置游戲說明游戲控制聲效游戲邏輯存儲(chǔ)圖 311 類結(jié)構(gòu)游戲啟動(dòng)時(shí)，首先顯示閃屏畫面，等待 3 秒或者玩家按下任意鍵之后，進(jìn)入游戲主菜單。菜單選項(xiàng)有“開始新游戲”“加載游戲”“游戲設(shè)置”“游戲說明”和“退出游戲”。玩家選擇“開始新游戲”和“加載游戲”則顯示游戲畫布；玩家選擇“游戲設(shè)置”，則進(jìn)入游戲設(shè)置表單；玩家按下“游戲說明”則顯示游戲說明畫面；玩家選擇“退出游戲”則退出整個(gè)游戲。整個(gè)游戲的界面切換流程如圖 312 所示，主要的用戶界面如圖 313 所示。游戲閃屏確定游戲菜單游戲設(shè)置游戲說明游戲畫布退出啟動(dòng) 圖 312 整個(gè)游戲的界面切換流程圖 圖 313 游戲主要的用戶界面5. 主要模塊設(shè)計(jì) SuDoKuMIDlet 類游戲的主類為 SuDoKuMIDlet 類，該類繼承了 MIDlet 類，用于在各個(gè)屏幕之間切換，并且實(shí)現(xiàn)各個(gè)功能的調(diào)用，是整個(gè)程序的中樞核心。游戲啟動(dòng)后顯示游戲閃屏，閃屏由 SplashScreen 類實(shí)現(xiàn)，代碼如下： public void startApp() { Displayable current = (this).getCurrent()。 if (current == null) { (this).setCurrent(new SplashScreen(this))。 //顯示閃屏界面 }}當(dāng)閃屏畫面結(jié)束之后，將創(chuàng)建并顯示菜單，菜單由 Menulist 類實(shí)現(xiàn)，此時(shí)后臺(tái)創(chuàng)建 SuDoKuCanvas 游戲畫布：private MenuList menuList。 //游戲菜單private SuDoKuCanvas myCanvas。 //游戲畫布public void splashScreenDone() { menuList = new MenuList(this)。 //創(chuàng)建游戲菜單 myCanvas = new SuDoKuCanvas(this)。 //創(chuàng)建游戲畫布 (this).setCurrent(menuList)。 //顯示游戲菜單}游戲菜單有“開始新游戲”，“加載游戲”，“參數(shù)設(shè)置”，“游戲說明”，“退出游戲”，當(dāng)玩家選中這些選項(xiàng)時(shí)，將會(huì)有相應(yīng)的調(diào)用方法。. 繼續(xù)游戲選項(xiàng)當(dāng)玩家進(jìn)入游戲后如果中途返回菜單，菜單會(huì)增加一項(xiàng)“繼續(xù)游戲”，選擇該項(xiàng)則返回游戲。中途返回菜單將停止計(jì)算時(shí)間，代碼如下： public void menuListContinue() { (this).setCurrent(myCanvas)。//顯示游戲畫布 ()。 //啟動(dòng)游戲線程}從游戲，游戲幫助和參數(shù)設(shè)置界面返回菜單的代碼如下，但是注意，從游戲中返回時(shí)調(diào)用了菜單對(duì)象的 setGameActive()方法，該方法用于在菜單中插入“繼續(xù)游戲”選項(xiàng)；當(dāng)設(shè)置好游戲參數(shù)返回時(shí)，通過主類將參數(shù)從對(duì)象傳遞給游戲畫布，可見主類起到了中介傳遞作用，這些方法代碼如下：public void gameBack() { (true)。//在菜單中插入繼續(xù)游戲選項(xiàng) (this).setCurrent(menuList)。//顯示菜單 } public void menuListContinue() { (this).setCurrent(menuList)。//顯示菜單 ()。 }public void optionsBack(byte level,byte back,byte input,byte music) {(level,back,input,music)。//將參數(shù)傳遞給游戲畫布(this).setCurrent(menuList)。//顯示菜單 }當(dāng)玩家填好方格內(nèi)所有數(shù)字后，將對(duì)結(jié)果進(jìn)行檢測，將檢測結(jié)果保存在布爾變量 isSolved 中，并且彈出提示框。如果玩家順利完成了謎題，提示框中將顯示玩家耗費(fèi)的時(shí)間和難度級(jí)別，并恭喜玩家順利通過；如果玩家填充了題目，卻存在錯(cuò)誤，提示框?qū)@示失敗圖片，并請(qǐng)玩家繼續(xù)努力。由于持續(xù)時(shí)間使用的是毫秒單位，還需將時(shí)間轉(zhuǎn)換為小時(shí)，分，秒單位。由notifyGameOver()方法處理游戲完成，該方法代碼如下：public void notifyGameOver(byte level,long gameDuration,boolean isSolved) { String strTime。 //時(shí)間字符串 String s。 //提示字符串 long temp。 //轉(zhuǎn)換時(shí)間格式臨時(shí)長整型變量 temp = gameDuration / 1000。//將毫秒轉(zhuǎn)換成秒 strTime = (gameDuration % 60) + 秒 。 //獲取秒 if (temp = 60){ temp = temp / 60。 strTime = (temp % 60) + 分 + strTime。 //獲取分 if (temp =60){ temp = temp/ 60。 strTime = temp + 小時(shí) + strTime。 //獲取小時(shí) } } if(isSolved)s=恭喜，在+strTime+ 內(nèi)您順利完成了本題！ 。 else s=未能完成本題，請(qǐng)繼續(xù)加油！。 if (alert == null) { alert = new Alert (游戲結(jié)束)。 //創(chuàng)建提示框 ()。 //等待用戶確認(rèn)后消失 ()。 } (s)。 //設(shè)置提示框的文字內(nèi)容 Image imgGameOver。 if(isSolved)imgGameOver = createImage(/)。 else imgGameOver = createImage(/)。 (imgGameOver)。 (false)。 (this).setCurrent (alert, menuList)。 }游戲閃屏由 SplashScreen 類實(shí)現(xiàn)，該類繼承了低級(jí)用戶界面 Cancas 類，并且開啟線程來等待用戶確認(rèn)，該類實(shí)現(xiàn)了 Runnable 接口。SplashScreen 類得構(gòu)造方法加載了閃屏圖片，并且啟動(dòng)等待線程，由如下代碼實(shí)現(xiàn)： SplashScreen( SuDoKuMIDlet midlet) { = midlet。 imgSplash = (/)。//加載閃屏圖片 new Thread(this).start()。 }當(dāng)顯示閃屏畫布時(shí)，將自動(dòng)調(diào)用 paint()方法，該方法將閃屏圖片繪制到屏幕中心，繪制完成后將圖片銷毀，以便垃圾回收。代碼如下：private Image imgSplash。public void paint(Graphics g) { int CanvasWidth = getWidth()。 //獲取屏幕寬度 int CanvasHeight = getHeight()。 //獲取屏幕高度 if (imgSplash != null) { (imgSplash,CanvasWidth/2, CanvasHeight/2, | )。//將圖片繪制到屏幕中心 imgSplash = null。 }}閃屏的線程等待 3 秒鐘后取消閃屏，代碼如下： public void run() { synchronized(this) { try { wait(3000L)。 //等待 3 秒 } catch (InterruptedException e) { //捕捉線程中斷異常 } dismiss()。 } }除了等待 3 秒外，玩家按下任意鍵也能取消閃屏，鍵盤處理調(diào)用畫布類的keyPressed()方法，代碼如下：public synchronized void keyPressed(int keyCode) { dismiss()。}Dismiss()方法用于取消閃屏，取消閃屏的同時(shí)設(shè)置標(biāo)志位，此時(shí)調(diào)用主類的 splahScreenDone()方法，該方法將顯示權(quán)交給游戲菜單。用如下方法實(shí)現(xiàn)：private volatile boolean isDismissed = false。 private v