基于android數(shù)獨(dú)游戲畢業(yè)設(shè)計(jì)

1、畢業(yè)設(shè)計(jì)(論文)題題 目目: :基于 Android 數(shù)獨(dú)游戲設(shè)計(jì)I / 47基于 Android 數(shù)獨(dú)游戲設(shè)計(jì)摘摘 要要移動互聯(lián)網(wǎng)時(shí)代的到來極大的改變了我們的生活，而 Android 是一種以 Linux 為基礎(chǔ)的開放源碼操作系統(tǒng)迅速占領(lǐng)了智能機(jī)操作系統(tǒng)，所以在 android 環(huán)境下開發(fā)顯得尤為必要。Android 是開放性體系架構(gòu)，不僅具有非常好的開發(fā)、調(diào)試環(huán)境，而且還支持各種可擴(kuò)展的用戶體驗(yàn)，包括豐富的圖形組件、多媒體支持功能以與強(qiáng)大的瀏覽器。因此，對于軟件從業(yè)人員來說，Android 平臺具有無限的吸引力。本文就在分析討論 Android 手機(jī)軟件開發(fā)技術(shù)原理的基礎(chǔ)上，為用戶開發(fā)出基

2、于Android 平臺的數(shù)獨(dú)游戲的軟件。通過對 Android 系統(tǒng)架構(gòu)和應(yīng)用開發(fā)進(jìn)行初步研究，設(shè)計(jì)一款數(shù)獨(dú)游戲。在對系統(tǒng)進(jìn)行詳細(xì)需求分析的基礎(chǔ)上，確定了系統(tǒng)的功能和性能要求，對游戲的開機(jī)動畫，菜單界面、屏幕繪制、時(shí)間控制、布局算法等進(jìn)行了設(shè)計(jì)。本文詳細(xì)介紹了在 Android 平臺上以 Java 為語言編寫游戲的過程，最終實(shí)現(xiàn)了一個(gè)界面友好、操作簡單的手機(jī)益智游戲。關(guān)關(guān)鍵鍵詞詞：Android 數(shù)獨(dú) 智能機(jī)ThedesignThedesign ofof SudokuSudoku gamegame basedbased onon AndroidAndroidAbstractAbstractAr

3、rival of the mobile Internet era has greatly changed our lives, and Android is a Linux-based system quickly occupied the smartphone operation system, Android development is particularly necessary under the circumstances. Androids biggest feature is its open architecture, not only has a very good dev

4、elopment and debugging environment, but also supports a variety of scalable user experience, including rich graphical components, multimedia support, and powerful browser. Therefore, for software professionals, Android platform has unlimited appeal.In this thesis, the analysis and discussion of Andr

5、oid mobile phone software development technology provide users with better platform to the Sudoku based on Android meteorological software. Through the Android system structure and application development for preliminary research, we designed a Sudoku game. In the system based on the analysis of the

6、 detailed requirements, we design the game in the game menu interface, the screen rendering, time control and layout algorithm.This thesis describes the whole development process of Android based smart phone game using Google Android SDK. Finally, we have the software with friendly interface and sim

7、ple operation.KeyKey Words:Words:Android ; Sudoku ; SmartphoneIII / 47 目 錄摘要 IAbstractII第一章緒論 11.1 研究背景 11.1.1 手機(jī)游戲的發(fā)展以與特征 11.1.2 數(shù)獨(dú)游戲背景 21.2 Android 手機(jī)游戲的市場價(jià)值 21.3 本文主要工作與章節(jié)結(jié)構(gòu) 3第二章 Android 平臺概述 42.1 Android 系統(tǒng)簡介 42.2 Android 系統(tǒng)特性 42.3 Android 操作系統(tǒng)框架結(jié)構(gòu) 52.3.1 應(yīng)用程序 62.3.2 應(yīng)用程序框架 62.3.3 庫與運(yùn)行環(huán)境 72.3.4

8、核 72.4 Android 應(yīng)用程序構(gòu)成 82.4.1Activity82.4.2 Broadcast Receiver92.4.3 Service102.4.4 Content Provider102.5 Android 應(yīng)用程序的生命周期 11第三章數(shù)獨(dú)游戲的設(shè)計(jì) 133.1 游戲功能簡介 133.2 游戲策劃以與準(zhǔn)備工作 143.3 游戲的架構(gòu) 163.3.1 各類的介紹 163.3.2 游戲的框架簡介 18第四章基于 Android 平臺數(shù)獨(dú)游戲的實(shí)現(xiàn) 194.1 歡迎界面的設(shè)計(jì)和實(shí)現(xiàn) 194.1.1 主類 KLSDActivity 實(shí)現(xiàn) 194.1.2 歡迎界面 WelcomeVi

9、ew 類的實(shí)現(xiàn) 204.1.3 WelcomeViewDrawThread 類和 WelcomeViewGoThread 類的實(shí)現(xiàn) 214.1.4 HelpView 類和 AboutView 類的實(shí)現(xiàn) 224.2 游戲界面相關(guān)類的實(shí)現(xiàn) 234.2.1 游戲界面 GameView 的實(shí)現(xiàn) 244.2.2 時(shí)間線程 TimeThread 的實(shí)現(xiàn) 254.3 數(shù)獨(dú)算法類的實(shí)現(xiàn) 254.3.1 數(shù)獨(dú)算法基本邏輯 264.3.2 檢測填充結(jié)果 274.4 游戲的測試和運(yùn)行 294.4.1 游戲測試概述 294.4.2 測試環(huán)境 304.4.3 游戲運(yùn)行結(jié)果 31第五章總結(jié)和展望 355.1 總結(jié) 355

10、.2 展望 35參考文獻(xiàn) 36致 37第一章緒論1.11.1 研究背景研究背景1.1.1 手機(jī)游戲的發(fā)展以與特征手機(jī)游戲，是指用戶運(yùn)行在移動終端的應(yīng)用程序，具有網(wǎng)絡(luò)連接功能，能夠滿足用戶隨時(shí)隨地進(jìn)行游行的需求，它需要一定的硬件環(huán)境和一定的系統(tǒng)環(huán)境作為其運(yùn)行的基礎(chǔ)。手機(jī)游戲吸引用戶最大的特點(diǎn)就是其便利性，由于其是移動終端，所以用戶可以隨時(shí)隨地進(jìn)行游戲。正是因?yàn)槠浔憷?，手機(jī)游戲市場有了很大的發(fā)展。在美國，手機(jī)游戲作為美國手機(jī)用戶最喜歡的移動應(yīng)用之一，在iPhone和Android等智能終端推出后發(fā)展迅速。手機(jī)游戲常見的特征可以總結(jié)如下：1.龐大的潛在用戶群：全球在使用的移動已經(jīng)超過 10 億部，

11、而且這個(gè)數(shù)字每天都在不斷增加。在除美國之外的各個(gè)發(fā)達(dá)國家，手機(jī)用戶都比計(jì)算機(jī)用戶多。手機(jī)游戲潛在的市場比其他任何平臺，比如 PlayStation 和 GameBoy 都要大。2.便攜性與移動性：在控制臺游戲時(shí)代，GameBoy 熱銷的一個(gè)原因就是便攜性人們可以隨時(shí)隨地沉浸在自己喜歡的游戲中，還可以隨時(shí)隨地?fù)屬徸约合矚g的裝備或?qū)櫸?。和游戲控制臺或者 PC 相比，手機(jī)雖然可能不是一個(gè)理想的游戲設(shè)備，但畢竟人們總是隨時(shí)隨身攜帶，這樣手機(jī)游戲很可能成為人們消遣時(shí)間的首選。手機(jī)便攜性、移動性的特征更能滿足用戶隨時(shí)隨地玩游戲的需求，用戶利用排隊(duì)、等車的時(shí)間進(jìn)行游戲，手機(jī)游戲碎片化的特性凸顯。調(diào)查顯示，2

12、9.8%的用戶在用手機(jī)玩游戲以后電腦端玩游戲的時(shí)間減少，手機(jī)游戲已經(jīng)開始搶奪電腦游戲時(shí)間。22.4%的用戶手機(jī)游戲時(shí)間越來越長，僅有 10%的用戶時(shí)間變短，手機(jī)游戲已逐漸成為一種普遍的娛樂方式。3.支持網(wǎng)絡(luò)：因?yàn)槭謾C(jī)是網(wǎng)絡(luò)設(shè)備，在一定限制因素下可以實(shí)現(xiàn)多人在線游戲。隨著移動網(wǎng)絡(luò)的發(fā)展，移動游戲也越來越多的被大家接受，對于之前長期通知市場的掌機(jī)來說造成了不少的沖擊。市場研究公司 IDC 和 App Annie 報(bào)告顯示 2013 年第一季度 iOS 和 Android 平臺游戲業(yè)務(wù)營收是掌機(jī)的 3 倍。1.1.2 數(shù)獨(dú)游戲背景數(shù)獨(dú)的前身為“九宮格” ，最早起源于中國。但當(dāng)時(shí)的算法比現(xiàn)在的更為復(fù)雜

13、，要求縱向、橫向、斜向上的三個(gè)數(shù)字之和等于 15，而不是數(shù)字不能重復(fù)。儒家典籍易經(jīng)中的“九宮圖”也是來源于此。到了 18 世紀(jì)末，瑞士數(shù)學(xué)家萊昂哈德歐文又發(fā)明了一種叫做“拉丁方塊”的游戲，之后不久，美國的一家數(shù)字邏輯游戲雜志開始刊登這類游戲，使此類游戲得到良好發(fā)展，之后又在日本得到了廣泛的傳播。2004 年，第一個(gè)“數(shù)獨(dú)”游戲被刊登上了英國泰晤士報(bào)的封面，此時(shí)開始數(shù)獨(dú)游戲才真正為世界所知曉。數(shù)獨(dú)游戲的規(guī)則很簡單，只需要在空格處填寫19的數(shù)字，并保證每個(gè)數(shù)字在每個(gè)九宮格只出現(xiàn)一次，而一般的游戲過程是系統(tǒng)隨機(jī)生成一個(gè)棋局，然后玩家需要在空白處填上相應(yīng)的數(shù)字使其滿足游戲規(guī)則。由于此類游戲操作簡單，不

14、需要特定的語言基礎(chǔ)，也不需要進(jìn)行數(shù)字運(yùn)算且可玩性高、鍛煉思維、開發(fā)大腦，所以很快風(fēng)靡全球。1.2Android1.2Android 手機(jī)游戲的市場價(jià)值手機(jī)游戲的市場價(jià)值A(chǔ)ndroid 是 Google 開發(fā)的基于 Linux 平臺的開源手機(jī)操作系統(tǒng)。它包括操作系統(tǒng)、用戶界面和應(yīng)用程序移動工作所需的全部軟件，而且不存在任何以往阻礙移動產(chǎn)業(yè)創(chuàng)新的專有權(quán)障礙2。Google 與開放手機(jī)聯(lián)盟合作開發(fā)了Android，這個(gè)聯(lián)盟由包括中國移動、摩托羅拉、高通、宏達(dá)電和 T-Mobile 在的 30 多家技術(shù)和無線應(yīng)用的領(lǐng)軍企業(yè)組成。Google 通過與運(yùn)營商、設(shè)備制造商、開發(fā)商和其他有關(guān)各方結(jié)成深層次的合

15、作伙伴關(guān)系，希望借助建立標(biāo)準(zhǔn)化、開放式的移動軟件平臺，在移動產(chǎn)業(yè)形成一個(gè)開放式的生態(tài)系統(tǒng)。Android平臺上的游戲相比應(yīng)用軟件，不需要進(jìn)行嚴(yán)格的市場細(xì)分，不需要針對目標(biāo)用戶量身定制。這是因?yàn)橛螒蛲婕业暮诵男杞y(tǒng)一的，那就是：娛樂與打發(fā)時(shí)間(乃至更高層面的競技需求和群體認(rèn)同需求)，這種需求附著于特定的社會發(fā)展階段，不受地域的限制，甚至于能夠穿透文化壁壘。因此，絕大多數(shù)3 / 47種類的游戲都具備傳染性與普適性，每一個(gè)售出的游戲都將會點(diǎn)燃周圍潛在玩家的激情，最終吞噬整個(gè)需求市場。由此可知，幾乎每一個(gè)Android手機(jī)用戶都是游戲的需求者，都是潛在的顧客，現(xiàn)今的1000多萬Android用戶不過是冰

16、山一角，隨著Android手機(jī)市場進(jìn)一步壯大，游戲的市場容量將具備更大的增長空間3。1.31.3 本文主要工作與章節(jié)結(jié)構(gòu)本文主要工作與章節(jié)結(jié)構(gòu)整篇論文共分為六個(gè)部分，其主要容安排如下：第一章 引言。介紹論文的研究背景、目的和意義。包括課題的背景資料簡介、國外研究現(xiàn)狀和發(fā)展趨勢、深入地介紹了課題研究的價(jià)值。第二章 Android 平臺概述。這部分主要是介紹了智能手機(jī)系統(tǒng)現(xiàn)狀、Android 的功能特征、Android 系統(tǒng)的特點(diǎn)以與 Android 的體系結(jié)構(gòu)。第三章 數(shù)獨(dú)游戲的設(shè)計(jì)。對游戲相關(guān)策劃，功能以與架構(gòu)進(jìn)行介紹。第四章 數(shù)獨(dú)游戲的實(shí)現(xiàn)。這部分主要介紹了游戲的界面、游戲中的邏輯處理以與該

17、游戲今后的改進(jìn)和優(yōu)化。第五章 總結(jié)和展望。對整篇論文加以總結(jié)與回顧以與對未來的展望。第二章 Android 平臺概述本章將介紹Android 這個(gè)基于Linux開發(fā)平臺，首先我們會介紹 Android 操作系統(tǒng)，然后講述其特性，接著講述其系統(tǒng)框架，其次我們會重點(diǎn)介紹其應(yīng)用程序的構(gòu)成模塊，最后會介紹其生命周期。2.12.1 AndroidAndroid 系統(tǒng)簡介系統(tǒng)簡介Android 是谷歌公司發(fā)布的手機(jī)操作系統(tǒng)，它是基于Linux 平臺的開源手機(jī)操作系統(tǒng)，谷歌公司將要把其打造為基于移動終端的真正開放的移動軟件平臺，不僅擁有移動所需要的工作軟件，而且在專利權(quán)方面能夠不侵犯他人權(quán)利去推動移動互聯(lián)網(wǎng)

18、的創(chuàng)新。谷歌公司為了開發(fā)Android，與開放手機(jī)聯(lián)盟進(jìn)行了合作，手機(jī)開放聯(lián)盟由全球30 多家移動開發(fā)和手機(jī)應(yīng)用的領(lǐng)先企業(yè)組成。谷歌公司不僅僅和運(yùn)營商達(dá)成了合作關(guān)系、而且與設(shè)備制造商以與開發(fā)商保持長期合作，目的就在于利用其優(yōu)勢建立移動軟件平臺，其特點(diǎn)是標(biāo)準(zhǔn)化、開放式的。Android是谷歌公司未來企業(yè)戰(zhàn)略的一部分，其目的是為了在任何時(shí)候任何地點(diǎn)能夠提供信息 4。2.22.2 AndroidAndroid 系統(tǒng)特性系統(tǒng)特性Android系統(tǒng)特性如下所示：1.應(yīng)用框架：Android系統(tǒng)組件，用于開發(fā)流程，兩個(gè)特性：可重用性和可替代性。2.Dalvik 虛擬機(jī)：在Android系統(tǒng)中， Dalvi

19、k虛擬機(jī)是一種Java 虛擬機(jī)，是Google公司自主開發(fā)，其代號為Dalvik，占用資源比較小，運(yùn)行效率比較高。3.集成瀏覽器：引擎WebKit，其特性是開源。4.優(yōu)化圖形：強(qiáng)大的自定義二維圖形庫?；贠penGL ES 1.0 標(biāo)準(zhǔn)的3D 圖形功能，在移動3D 開發(fā)中有著至關(guān)重要的地位。5.SQLite 數(shù)據(jù)庫：SQLite 提供結(jié)構(gòu)化的數(shù)據(jù)存儲。它是一款輕型免費(fèi)的5 / 47且開源的數(shù)據(jù)庫，設(shè)計(jì)目標(biāo)是嵌入式的。它具備占用資源低、需要的存空間少、處理速度較快，并且還支持事務(wù)處理功能等優(yōu)點(diǎn)。6.多媒體支持：支持各種通用的音視頻和靜態(tài)圖像格式(MPEG4、MP3、JPG、PNG、GIF、AAC

20、、H.264、AMR)。7.GSM 技術(shù)：(依賴硬件)Global System for Mobile Communications,全球移動通訊系統(tǒng),俗稱全球通,是第二代移動通信技術(shù)，其開發(fā)目的是讓全球各地可以共同使用一個(gè)移動網(wǎng)絡(luò)標(biāo)準(zhǔn)，讓用戶使用一部手機(jī)就能行遍全球。8.藍(lán)牙，EDGE，3G,and Wi-Fi：(依賴硬件)藍(lán)牙和Wi-Fi 都是一種短距離的無線連接技術(shù)，在短距離可以實(shí)現(xiàn)話音和數(shù)據(jù)的無線傳輸。EDGE(Enhanced Data Rate forGSM Evolution)，是增強(qiáng)型數(shù)據(jù)速率GSM 演進(jìn)技術(shù)。9.Camera，GPS，Compass，and Accelerom

21、eter：(依賴硬件)GPS(Global PositioningSystem)，即全球定位系統(tǒng)。它是一個(gè)由覆蓋全球的24 顆衛(wèi)星組成的衛(wèi)星系統(tǒng)。Compass是一個(gè)開放源代碼的Java 搜索引擎框架。10.強(qiáng)大的開發(fā)環(huán)境：包括一個(gè)設(shè)備模擬器，調(diào)試工具，存和性能檢測，以與Eclipse11.IDE 的開發(fā)插件。Eclipse集成開發(fā)環(huán)境。2.32.3 AndroidAndroid 操作系統(tǒng)框架結(jié)構(gòu)操作系統(tǒng)框架結(jié)構(gòu)Android 作為一個(gè)開源的移動設(shè)備的平臺，其軟件層次結(jié)構(gòu)自上而下分為四個(gè)層次，分別是：應(yīng)用程序(Application)、應(yīng)用程序框架(Application Framework)

22、、各種庫(Libraries)和Android 運(yùn)行環(huán)境(RunTime)、Linux 核(Linux Kernel)。圖 2.1 Google 手機(jī)操作系統(tǒng)平臺-Android 的架構(gòu)模型2.3.1 應(yīng)用程序突破傳統(tǒng)思維，提供更好的用戶體驗(yàn)。Android 將會移植一系列的核心應(yīng)用，包括E-mail 客戶端，SMS 程序，日歷，GPS 地圖，瀏覽器，聯(lián)系人等等。所有的應(yīng)用程序都是由Java語言完成的。應(yīng)用程序是無界限的，可以在平等條件下創(chuàng)建，還可以輕松地嵌入Web，可以并行運(yùn)行5。2.3.2 應(yīng)用程序框架Android 應(yīng)用程序由一個(gè)或多個(gè)組件組成，Android 的應(yīng)用程序框架為應(yīng)用程序?qū)?/p>

23、的開發(fā)者提供APIs，它實(shí)際上是一個(gè)應(yīng)用程序的框架。由于上層的應(yīng)用程序是以Java 構(gòu)建的，因此本層次提供的首先包含了UI 程序中所需要的各種控件：例如：Views(視圖組件)包括lists(列表)，grids(柵格)，text boxes(文本框)，buttons(按鈕)等。甚至一個(gè)嵌入式的Web 瀏覽器。一個(gè) Android 的應(yīng)用程序可以利用應(yīng)用程序框架中的以下幾個(gè)部分：Activity(活動)，Broadcast Receiver(廣播接收者)，Service(服務(wù))，Content Provider(容提供者)7 / 472.3.3 庫與運(yùn)行環(huán)境Android 包含一套C/C+庫，能

24、被系統(tǒng)中不同的組件使用。這些功能通過Android應(yīng)用框架展現(xiàn)給開發(fā)人員。下面列出一些核心庫：(1)System C library：從BSD 繼承來的標(biāo)準(zhǔn)C 系統(tǒng)函數(shù)庫，也是系統(tǒng)中最為底層的庫，是專門為基于嵌入式Linux 的設(shè)備制定的。(2)Media Framework：該庫支持多種常用的音頻、視頻格式的回放和錄制，同時(shí)支持靜態(tài)圖片文件，包括MPEG4、H.264、MP3、AAC、AMR、JPG 和PNG 等。(3)Surface Manager：用于管理不同應(yīng)用對圖形顯示子系統(tǒng)和2D 和3D 圖形層的訪問。(4)WebKit：一個(gè)時(shí)尚的web 瀏覽器引擎，為Android 瀏覽器和嵌的

25、web view 提供實(shí)現(xiàn)。(5)SGL：隱藏的2D 圖形引擎。(6)3D libraries：基于OpenGL ES 1.0 APIs 實(shí)現(xiàn)的庫，該庫可以使用硬件3D 加速，或者高度優(yōu)化的3D 軟加速。(7)FreeType：位圖和向量模式的字體繪制。(8)SQLite：一個(gè)強(qiáng)大的，輕量的關(guān)系型數(shù)據(jù)庫引擎，用于所有的應(yīng)用。Android 運(yùn)行時(shí)Android 包含一組核心庫，提供了Java 語言核心庫的大部分功能。Android運(yùn)行環(huán)境主要指的是虛擬機(jī)技術(shù)Dalvik。Dalvik虛擬機(jī)依賴Linux kernel來實(shí)現(xiàn)一些潛在功能，例如線程和底層存管理。Dalvik虛擬機(jī)和一般Java虛擬

26、機(jī)(JavaVM)不同，它執(zhí)行的不是Java標(biāo)準(zhǔn)的字節(jié)碼而是Dalvik可執(zhí)行格式(.dex)中執(zhí)行文件，該格式的文件經(jīng)過優(yōu)化占用很小的存。在執(zhí)行的過程中，每一個(gè)應(yīng)用程序即一個(gè)進(jìn)程(Linux 的一個(gè)Process) 。二者最大的區(qū)別在于Java VM 是以基于棧的虛擬機(jī)(Stack-based)，而Dalvik是基于寄存器的虛擬機(jī)(Register-based)6。顯然，后者最大的好處在于可以根據(jù)硬件實(shí)現(xiàn)更大的優(yōu)化，這更適合移動設(shè)備的特點(diǎn)。每個(gè)Android應(yīng)用程序都在Dalvik VM的一個(gè)實(shí)例中運(yùn)行，這個(gè)實(shí)例駐留在一個(gè)由Linux核管理的進(jìn)程中。2.3.4 核Android使用Linux

27、2.6 核來提供系統(tǒng)的核心服務(wù)，例如：安全機(jī)制，存管理，進(jìn)程管理，網(wǎng)絡(luò)堆棧。Android更多的是需要一些與移動設(shè)備相關(guān)的驅(qū)動程序。其主要的驅(qū)動有：顯示驅(qū)動(Display Driver)、Flash存驅(qū)動(Flash Memory Driver)、照相機(jī)驅(qū)動(Camera Driver)、音頻驅(qū)動(Audio Driver)、Wi-Fi驅(qū)動(Camera Driver)、鍵盤驅(qū)動(KeyBoard Driver)、藍(lán)牙驅(qū)動(Bluetooth Driver)、Binder IPC驅(qū)動(Android一個(gè)特殊的驅(qū)動程序，具有單獨(dú)的設(shè)備節(jié)點(diǎn)，提供進(jìn)程間通訊的功能)7。2.42.4 Android

28、Android 應(yīng)用程序構(gòu)成應(yīng)用程序構(gòu)成Android應(yīng)用程序與其他很多計(jì)算機(jī)平臺的應(yīng)用程序不同，他們沒有唯一的啟動入口，一個(gè)Android應(yīng)用程序是由多個(gè)不同組件組合而成，組件間通過Intent實(shí)現(xiàn)通信。Android系統(tǒng)的基本組件包括Activity、Service、Broadcast Receiver和Content Provider等，要實(shí)現(xiàn)組件間通信，還需要Intent消息組件。并不是每個(gè)Android應(yīng)用程序都必須具備這四個(gè)組件，很多時(shí)候只需要這四種中的某幾種就可以了。除此之外，應(yīng)用程序的所有組件還都必須在AndroidManifest.xml中聲明8。這是一個(gè)XML配置文件，這個(gè)

29、配置文件用于定義應(yīng)用程序的組件、組件的功能與必要條件等。這個(gè)配置文件是任何一個(gè)Android應(yīng)用程序所必需的。2.4.1ActivityActivity 可以說是開發(fā)人員最常用的組件，同時(shí)也屬于Android 最基本的組成部分之一。Android 程序中，一般一個(gè)Activity 代表手機(jī)屏幕上的一屏。舉例來說，如果將手機(jī)比作一個(gè)瀏覽器，那么一個(gè)Activity 就相當(dāng)于一個(gè)網(wǎng)頁。在Activity 中，可以添加多個(gè)視圖，然后為這些視圖添加一些事件處理。這些視圖可以是按鈕、文本框、列表等?？梢钥吹?，Activity 的概念和網(wǎng)頁的概念相當(dāng)類似。一般一個(gè)Android 應(yīng)用是由多個(gè)Activit

30、y 組成，同時(shí)這些Activity 相互之間可以進(jìn)行跳轉(zhuǎn)，例如，按下某個(gè)Activity 中的Button 按鈕后，可能會跳轉(zhuǎn)到一個(gè)其他的Activity。不過和網(wǎng)頁跳轉(zhuǎn)稍有不同，Activity之間的跳轉(zhuǎn)可以有返回值，例如，在Activity A 跳轉(zhuǎn)到Activity B 后，那么當(dāng)9 / 47Activity B運(yùn)行結(jié)束時(shí)，可能會返回給Activity A 一個(gè)值。在多個(gè)Activity 交流的過程中，這種返回機(jī)制是相當(dāng)實(shí)用的。當(dāng)用戶進(jìn)入一個(gè)新的屏幕時(shí)，之前的屏幕會轉(zhuǎn)入暫停狀態(tài)，并且保存在歷史堆棧中。正是由于歷史堆棧的存在，用戶可以通過返回操作，返回到之前打開過的所有屏幕。Android

31、默認(rèn)的是將應(yīng)用程序從開始到當(dāng)前的每一個(gè)屏幕都保存到堆棧中，不過與此同時(shí)，Android還提供了很方便的機(jī)制，讓開發(fā)人員自定義某個(gè)屏幕是否需要保存到歷史堆棧。Activity 的跳轉(zhuǎn)實(shí)現(xiàn)，必須借助于Intent 類。因此Intent 在Android 應(yīng)用中占據(jù)的地位是極其重要的。簡單來說，一個(gè)Intent 就是對一個(gè)將要執(zhí)行的操作請求的抽象描述。Intent 的描述，主要包含有兩個(gè)數(shù)據(jù)結(jié)構(gòu)：動作(action)和動作對應(yīng)的數(shù)據(jù)(data)。動作有很多種，系統(tǒng)中最常見的動作類型有：MAIN(表明該Activity 是應(yīng)用程序的入口)、VIEW、PICK、EDIT 等等；而動作對應(yīng)的數(shù)據(jù)一般以UR

32、I 的形式表示，例如：要查看某一個(gè)網(wǎng)頁，則需要?jiǎng)?chuàng)建Intent，它的動作類型為VIEW，對應(yīng)的數(shù)據(jù)應(yīng)該是該網(wǎng)頁的網(wǎng)址。值得一提的是，有一個(gè)類叫IntentFilter，它是Intent的相關(guān)類。如果說Intent是一個(gè)有效的操作請求，那么一個(gè)IntentFiler則用于描述一個(gè)Activity(或者Intent Receiver等)能夠接收哪些Intent的請求。比如系統(tǒng)瀏覽器的Activity用于查看某一個(gè)網(wǎng)頁，那么它用于接收Intent的IntentFilter，要定義類型為VIEW的動作并且能夠過濾表示一個(gè)網(wǎng)頁網(wǎng)址的URI。通常IntentFilter要被注冊在AndroidManife

33、st.xml文件中。Activity 之間的跳轉(zhuǎn)正是通過解析各種Intent 來實(shí)現(xiàn)的。例如一個(gè)Activity 調(diào)用startActivity(intent)方法，希望跳轉(zhuǎn)到其他的Activity 時(shí)，會觸發(fā)系統(tǒng)的Intent 解析過程，在所有安裝的應(yīng)用程序中已注冊的IntentFilter 中查找，并最終挑選出能夠匹配Intent 的Activity。然后這個(gè)新的Activity 因?yàn)榻邮盏絀ntent 的請求而開始運(yùn)行，完成Activity 的跳轉(zhuǎn)。這種跳轉(zhuǎn)機(jī)制提供了兩個(gè)關(guān)鍵好處：(1)操作請求被Intent 封裝起來，方便Activity 重復(fù)利用。(2)相互跳轉(zhuǎn)的多個(gè)Activity

34、 之間實(shí)現(xiàn)了松耦合。只要IntentFilier 保持不變，一個(gè)ctivity 可以隨意修改，而不用擔(dān)心其他Activity 找不到它。2.4.2 Broadcast Receiver應(yīng)用程序可以通過Broadcast Receiver 監(jiān)聽一個(gè)外部的事件，并做出響應(yīng)。例如，當(dāng)應(yīng)用程序需要對呼入這個(gè)外部事件做出反應(yīng)時(shí)，可以利用Broadcast Receiver 進(jìn)行處理。再如，當(dāng)一個(gè)后臺下載任務(wù)成功的事件發(fā)生時(shí)，需要提示用戶下載完成，仍然可以利用Broadcast Receiver 來進(jìn)行處理。Broadcast Receiver不能生成UI，也就是說對于用戶來說是透明的，用戶是看不到的。B

35、roadcast Receiver只能通過NotificationManager來通知用戶這些事件發(fā)生了。BroadcastReceiver既可以在AndroidManifest.xml中注冊，也可以在運(yùn)行時(shí)的代碼中使用Context.registerReceiver()進(jìn)行注冊。注冊完成之后，當(dāng)事件來臨的時(shí)候，即使程序沒有啟動，系統(tǒng)依然可以根據(jù)定義，自動啟動程序。各種應(yīng)用也可以通過使用Context.sendBroadcast()將它們自己的Intent Broadcast廣播給其他應(yīng)用程序。2.4.3 ServiceService是一種程序，它可以運(yùn)行很長時(shí)間，但是它卻沒有用戶界面，不可交

36、互，而且不能自己運(yùn)行。它需要通過某一個(gè)Activity或者其他的Context對象來調(diào)用12。最常見的例子，比如說用戶正在運(yùn)行一個(gè)音樂播放器的程序，此時(shí)如果想瀏覽網(wǎng)頁，那么，在用戶導(dǎo)航到Android的瀏覽器以后，雖然進(jìn)入了瀏覽器屏幕，但是歌曲的播放并沒有停止，而是在后臺繼續(xù)播放著。其實(shí)播放的動作正是由播放音樂的Service執(zhí)行著。當(dāng)然，如果需要的話，Service也是可以停止。通過startService(Intent service)可以啟動一個(gè)Service，通過Context.bindService()可以綁定一個(gè)Service。2.4.4 Content Provider對于數(shù)據(jù)存

37、儲，Android與其他的操作系統(tǒng)有一點(diǎn)不太一樣，即數(shù)據(jù)在Android程序中都是私有的，這些數(shù)據(jù)包括文件類型和數(shù)據(jù)庫類型以與其他類型的數(shù)據(jù)。這樣系統(tǒng)和應(yīng)用程序的數(shù)據(jù)就各自獨(dú)立起來，以避免受到某些不正常程序或是病毒的影響。不過這并不代表各應(yīng)用程序之間就因此而無法進(jìn)行數(shù)據(jù)11 / 47交換了。當(dāng)某個(gè)應(yīng)用程序希望與其它的應(yīng)用共享其數(shù)據(jù)時(shí)，Android提供的Content Provider就可以發(fā)揮作用了。在實(shí)現(xiàn)ContentProvider的抽象接口以后，程序便可以將自己的數(shù)據(jù)暴露出去，其他程序只要有權(quán)限，就可以通過這一套標(biāo)準(zhǔn)而統(tǒng)一的接口，讀取或是刪除該程序的數(shù)據(jù)13。2.52.5 Androi

38、dAndroid 應(yīng)用程序的生命周期應(yīng)用程序的生命周期Android 應(yīng)用程序一個(gè)完整的生命周期是從應(yīng)用程序的創(chuàng)建到結(jié)束的全過程，與其他系統(tǒng)不同，Android 應(yīng)用程序的生命周期是不受進(jìn)程本身控制的，而是由Android 系統(tǒng)來決定的，Android 系統(tǒng)會根據(jù)應(yīng)用程序?qū)τ脩舻闹匾耘c當(dāng)前系統(tǒng)的負(fù)載來決定生命周期的長短。Android 系統(tǒng)的各個(gè)進(jìn)程重要程度如圖2.2所示。前臺進(jìn)程可見進(jìn)程服務(wù)進(jìn)程后臺進(jìn)程空進(jìn)程關(guān)鍵優(yōu)先級高優(yōu)先級低優(yōu)先級圖 2.2 Android 應(yīng)用程序進(jìn)程優(yōu)先級(1)前臺進(jìn)程，是Android 系統(tǒng)中最重要的進(jìn)程，是與用戶正在進(jìn)行交互的進(jìn)程。有以下四種情況：Activit

39、y 正在與用戶進(jìn)行交互；進(jìn)程被Activity 調(diào)用，而且這個(gè)進(jìn)程正在與用戶進(jìn)行交互；進(jìn)程服務(wù)正在執(zhí)行聲明中的回調(diào)函數(shù)，如onCreate()、onStart()、onDestroy()；進(jìn)程的Broadcast Receiver 在執(zhí)行onReceive()函數(shù)。Android 系統(tǒng)在多個(gè)前臺進(jìn)程同時(shí)運(yùn)行時(shí)，可能會出現(xiàn)資源不足的情況，此時(shí)會清除部分前臺進(jìn)程，以保證主要的用戶界面能夠與時(shí)響應(yīng)。(2)可見進(jìn)程，是指部分應(yīng)用程序界面能夠被用戶看見，卻不在前臺與用戶進(jìn)行交互，不影響界面事件的進(jìn)程。如果應(yīng)用程序進(jìn)程包含一個(gè)服務(wù)，且這個(gè)服務(wù)正被用戶可見的Activity 調(diào)用，則此進(jìn)程同樣被視為可見進(jìn)程

40、。Android 進(jìn)程一般存在少量的可見進(jìn)程，只有在特殊情況下，Android 系統(tǒng)才會為保證前臺進(jìn)程的資源而清除可見進(jìn)程。(3)服務(wù)進(jìn)程，服務(wù)進(jìn)程是指包含已啟動服務(wù)的進(jìn)程。該進(jìn)程沒有用戶界面并在后臺長期運(yùn)行。除非Android 系統(tǒng)不能保證前臺進(jìn)程和可見進(jìn)程所必要的資源，否則不會強(qiáng)行清除服務(wù)進(jìn)程。(4)后臺進(jìn)程，后臺進(jìn)程是指不包括任何已經(jīng)啟動的服務(wù)，而且沒有任何用戶可見的Activity 的進(jìn)程。Android 系統(tǒng)中一般存在數(shù)量較多的后臺進(jìn)程，在系統(tǒng)資源緊時(shí)系統(tǒng)將會優(yōu)先清除用戶較長時(shí)間沒有見到的后臺進(jìn)程。(5)空進(jìn)程，空進(jìn)程是不包含任何活躍組件的進(jìn)程，空進(jìn)程在系統(tǒng)緊時(shí)會被首先清除。但為了提

41、高Android 應(yīng)用程序的啟動速度，Android 系統(tǒng)會將空進(jìn)程保存在系統(tǒng)存用，在用戶重新啟動該程序時(shí)，空進(jìn)程會被重新使用。當(dāng)兩個(gè)應(yīng)用程序具有一樣的優(yōu)先級時(shí)，處于較低優(yōu)先級且運(yùn)行時(shí)間最長的進(jìn)程將會首先被終止。進(jìn)程的優(yōu)先級也受到進(jìn)程間依賴性的影響，如果一個(gè)應(yīng)用程序依賴于第二個(gè)應(yīng)用程序所提供的服務(wù)或者容提供器，那么第二個(gè)應(yīng)用程序至少會擁有與它所支持的這個(gè)應(yīng)用程序一樣的優(yōu)先級。進(jìn)程的優(yōu)先級取決于所有組件中優(yōu)先級最高的部分，進(jìn)程的優(yōu)先級會根據(jù)其他進(jìn)程的依賴關(guān)系而變化。第三章 數(shù)獨(dú)游戲的設(shè)計(jì)3.13.1 游戲功能簡介游戲功能簡介數(shù)獨(dú)游戲的規(guī)則很簡單，只需在空格處填入19 的數(shù)字，并保證每個(gè)數(shù)字在每個(gè)

42、九宮格只能出現(xiàn)一次，且每個(gè)數(shù)字在每一行、每一列也只能出現(xiàn)一次，而一般的游戲過程是系統(tǒng)隨機(jī)生成一個(gè)棋局，然后玩家需要在空白處填上相應(yīng)的數(shù)字使其滿足游戲規(guī)則。游戲框架如下圖所示：點(diǎn)擊圖標(biāo)開機(jī)動畫計(jì)時(shí)區(qū)域提示暫停游戲區(qū)域退出游戲功能區(qū)域開始游戲菜單界面幫助游戲關(guān)于游戲退出換題圖3.1 游戲框架圖該游戲的運(yùn)行步驟如下。1.啟動游戲后首先進(jìn)入的便是歡迎界面的動畫，在歡迎界面中，“點(diǎn)擊屏幕繼續(xù)”閃動，達(dá)到提示的效果。2.在游戲界面點(diǎn)擊屏幕，便進(jìn)入菜單界面。3.在菜單界面單擊“關(guān)于游戲”菜單可進(jìn)入“關(guān)于”界面，在“關(guān)于”界面中介紹了該游戲的目標(biāo)平臺與開發(fā)日期。4.在菜單界面單擊“幫助游戲”菜單可進(jìn)入“幫助”

43、界面，在“幫助”界面介紹了游戲的基本規(guī)則。5.在菜單界面單擊“開始游戲”菜單可進(jìn)入游戲界面。6.當(dāng)在游戲過程中單擊“暫?！卑粹o時(shí)，便進(jìn)入暫停狀態(tài)。7在游戲過程中隨時(shí)可以通過“換題”按鈕來更換題目。8.當(dāng)玩家單擊“放棄”按鈕時(shí)，會提示玩家是否真的需要退出游戲，然后根據(jù)玩家的選擇進(jìn)行操作。9.當(dāng)玩家單擊“提示”按鈕時(shí)，界面上會出現(xiàn)一個(gè)紅心表示當(dāng)前可以提示玩家輸入數(shù)字，此時(shí)再單擊空白處，便會自動填上正確答案。10.當(dāng)玩家將界面中所有的空白全部填滿數(shù)字時(shí)，系統(tǒng)會自動判斷所填寫的數(shù)字正確與否，當(dāng)有錯(cuò)誤時(shí)，會出現(xiàn)游戲失敗界面；當(dāng)全部填寫正確時(shí)，會出現(xiàn)游戲勝利界面。11.在勝利或者失敗狀態(tài)時(shí)，玩家可以通過點(diǎn)

44、擊屏幕任意位置返回歡迎界面。12.在菜單界面單擊“退出游戲”便可退出該游戲。3.23.2 游戲策劃以與準(zhǔn)備工作游戲策劃以與準(zhǔn)備工作3.2.1歡迎界面的策劃歡迎界面的主要實(shí)現(xiàn)的是開機(jī)動畫以與菜單選項(xiàng)的功能。在開機(jī)動畫上準(zhǔn)備實(shí)現(xiàn)動態(tài)效果，利用圖片刷幀進(jìn)行實(shí)現(xiàn)。在菜單界面實(shí)現(xiàn)游戲的功能選擇，菜單界面就是一圖片，鼠標(biāo)點(diǎn)擊相應(yīng)的區(qū)域?qū)崿F(xiàn)相應(yīng)的功能。在這里運(yùn)用到坐標(biāo)系，如下圖所示15 / 47圖3.2 菜單界面手機(jī)屏幕分辨率是480320，所以橫縱坐標(biāo)如圖所示。當(dāng)點(diǎn)擊的區(qū)域坐落于60 x260,135y180區(qū)域，則進(jìn)行開始游戲功能。當(dāng)點(diǎn)擊的區(qū)域坐落于60 x260,180y230區(qū)域，則進(jìn)行關(guān)于游戲功能

45、。當(dāng)點(diǎn)擊的區(qū)域坐落于60 x260,230y280區(qū)域，則進(jìn)行幫助游戲功能。當(dāng)點(diǎn)擊的區(qū)域坐落于60 x260,280ywelcomeView.bitmapsID.length-1) welcomeView.drawIndex = welcomeView.bitmapsID.length-10; if(welcomeView.drawIndex%5 = 0) welcomeView.drawString = !welcomeView.drawString; try Thread.sleep(sleepSpan);/睡眠 catch(Exception e) e.printStackTrace()

46、;/打印異常信息 分析該類的run（）方法，控制drawIndex的值，每次循環(huán)將歡迎界面的drawIndex 加1，然后判斷是否到達(dá)數(shù)組的最后，當(dāng)?shù)竭_(dá)最后時(shí)，將其減10，然后繼續(xù)進(jìn)行循環(huán)。同時(shí)，判斷drawIndex是否為5，這樣每循環(huán)5次改變drawString的值，從而實(shí)現(xiàn)文字的閃動效果。4.1.4 HelpView 類和 AboutView 類的實(shí)現(xiàn)游戲中關(guān)于游戲幫助和游戲說明，我們分別通過HelpView類和AboutView類的實(shí)現(xiàn)。HelpView類和AboutView類都是通過onDraw()方法來繪制界面。由于這兩個(gè)類在很大程度上是相似的，所以下面只分析HelpView類，代

47、碼如下所示：public HelpView(KLSDActivity activity) super(activity);this.activity = activity;/得到activity的引用surfaceHolder = this.getHolder();/獲得surfaceHoldergetHolder().addCallback(this);/添加Callback接口的實(shí)現(xiàn)helpBitmap = BitmapFactory.decodeResource(getResources(), 23 / 47R.drawable.help);publicvoid onDraw(Canva

48、s canvas) /繪制方法canvas.drawColor(Color.WHITE);/背景色canvas.drawBitmap(helpBitmap, 0, 0, null);/繪制圖片publicboolean onTouchEvent(MotionEvent event) /鍵盤監(jiān)聽方法if(event.getAction() = MotionEvent.ACTION_DOWN)/屏幕被按下double x = event.getX();double y = event.getY();/得到坐標(biāo)if(x270 & x440 & y480)/點(diǎn)擊確定按鈕activity

49、.myHandler.sendEmptyMessage(2);returnsuper.onTouchEvent(event);public HelpView(KLSDActivity activity) 為“幫助”界面的構(gòu)造器，在構(gòu)造器中先得到activity 以與surfaceHolder的引用，然后添加Callback 接口的實(shí)現(xiàn)并對圖片資源進(jìn)行初始化。onDraw（）為重寫的繪制方法，在該方法中，首先繪制白色背景，然后將幫助界面的背景圖片繪制到指定位置。onTouchEvent（）為重寫的鍵盤監(jiān)聽方法，當(dāng)玩家點(diǎn)擊屏幕時(shí)，會調(diào)用該方法來處理玩家的屏幕事件，在“幫助”界面中該方法實(shí)現(xiàn)比較簡單

50、，只是判斷玩家點(diǎn)擊的是否為返回按鈕即可。當(dāng)玩家點(diǎn)擊返回按鈕時(shí)，需要向activity 發(fā)送Handler 消息通知控制器切換屏幕。4.24.2 游戲界面相關(guān)類的實(shí)現(xiàn)游戲界面相關(guān)類的實(shí)現(xiàn)游戲界面實(shí)現(xiàn)游戲展示，計(jì)時(shí)界面展示，以與功能按鍵。流程圖如下圖所示：開始生成數(shù)獨(dú)填數(shù)區(qū)域換題提示提示暫停計(jì)時(shí)暫停填數(shù)檢測退出結(jié)束是否是否是否是否圖 4.2 游戲界面流程圖4.2.1 游戲界面 GameView 的實(shí)現(xiàn)首先理解下GameView的運(yùn)行思路，GameView在初始化時(shí)候讀取相關(guān)圖片信息，包括背景圖片，數(shù)獨(dú)背景框圖片等等，在初始化同時(shí)，啟動GameViewDrawThread線程進(jìn)行刷幀，TimeThr

51、ead 線程來更新界面中的時(shí)間。當(dāng)玩家點(diǎn)擊背景框空白位置，需要繪制數(shù)字鍵盤時(shí)，會啟動DrawKeyThread 線程繪制數(shù)字鍵盤。當(dāng)玩家點(diǎn)擊按鈕時(shí)候，相關(guān)方法會被調(diào)用。以上的過程都需要KLSDActivity的參與管理。GameView 同樣繼承自SurfaceView 類，其關(guān)鍵也是實(shí)現(xiàn)onDraw()方法。onDraw()方法分別繪制游戲界面背景圖片，數(shù)字背景框，選題提示等等按鈕，時(shí)間顯示區(qū)域等。DrawKey()方法實(shí)現(xiàn)了數(shù)字鍵盤的繪制，保證在點(diǎn)擊空白框時(shí)候有圓盤數(shù)字選框出現(xiàn)。通過surfaceCreated（）和surfaceDestroyed（）兩個(gè)方法負(fù)責(zé)相關(guān)線程的啟動和調(diào)用工作。

52、25 / 474.2.2 時(shí)間線程 TimeThread 的實(shí)現(xiàn)TimeThread線程主要用來更新界面中的時(shí)間，作為數(shù)獨(dú)游戲玩家計(jì)時(shí)功能，代碼如下：publicclass TimeThread extends ThreadGameView gameView;/聲明GameView的引用boolean flag=true;/循環(huán)標(biāo)志位public TimeThread(GameView gameView)/構(gòu)造器this.gameView=gameView;/得到GameView的引用publicvoid run()/重寫的run方法while(flag)gameView.time+;/時(shí)間自

53、加tryThread.sleep(1000);/睡眠一秒種catch(Exception e)/捕獲異常e.printStackTrace();/打印異常信息TimeThread 類的實(shí)現(xiàn)比較簡單，只需每隔一秒鐘通過gameView.time自加更改一下GameView 中表示時(shí)間的屬性即可。public TimeThread(GameView gameView) 為時(shí)間線程的構(gòu)造器，在構(gòu)造器中先得到GameView的引用。然后重寫run()方法，通過時(shí)間的自加，實(shí)現(xiàn)一秒鐘功能。4.34.3 數(shù)獨(dú)算法類的實(shí)現(xiàn)數(shù)獨(dú)算法類的實(shí)現(xiàn)數(shù)獨(dú)算法類主要實(shí)現(xiàn)數(shù)獨(dú)的生成以與填入數(shù)字的檢測功能，流程圖如下：開始生

54、成數(shù)獨(dú)填入數(shù)字符合規(guī)則游戲成功結(jié)束是否圖 4.3 WelcomeView 類功能流程圖4.3.1 數(shù)獨(dú)算法基本邏輯本節(jié)將對數(shù)獨(dú)算法類ShuDuSuanFa.java進(jìn)行解釋，該類基本上是數(shù)學(xué)計(jì)算，通過一定的算法產(chǎn)生所需要的數(shù)獨(dú)數(shù)組，通過特定的接口供其他類使用。該類的目的是創(chuàng)建一個(gè)二維數(shù)組來表示數(shù)獨(dú)矩陣。使矩陣的每行、每列、每塊都沒有重復(fù)的數(shù)字。算法的簡單思路是先隨機(jī)取出一個(gè)09 的數(shù)字，然后檢查其所在的行、列、塊是否都符合要求。當(dāng)符合要求時(shí)繼續(xù)填充下一個(gè)，而當(dāng)不符合要求時(shí)，再次隨機(jī)取出一個(gè)沒有取出過的數(shù)字，再判斷。當(dāng)9 個(gè)數(shù)字都取出過后還沒有找到符合要求的數(shù)字時(shí)，進(jìn)行回退處理，即將最后一個(gè)取出

55、的符合要求的數(shù)字進(jìn)行重新取值，直到所有數(shù)字全部填充完畢。在求解數(shù)獨(dú)時(shí)候，運(yùn)用到回溯法，將所有的解（問題的解空間）按照一定結(jié)構(gòu)排列，再進(jìn)行搜索。一般解空間構(gòu)造成為為樹狀結(jié)構(gòu)，用深度優(yōu)先的策略搜索，一般有兩種方式：1.只需要一個(gè)解的話，找到解即停止。2.需要求出所有解，則需做“樹的遍歷”找到所有解?；厮莘ǖ幕咀龇ㄊ撬阉?，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數(shù)相當(dāng)大的問題。27 / 47回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則跳過對該結(jié)點(diǎn)為根的子

56、樹的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先策略搜索?；厮莘ㄊ且环N搜索算法，其基本思路是：在一個(gè)問題中，根據(jù)題意給出的邊界條件劃定出所有可能解的圍（稱為可能解） ，根據(jù)題意確定出約束條件。利用程序順次在所有可能解中搜索時(shí)按照深度搜索的方式進(jìn)行。即在第一層選定一個(gè)滿足約束條件的解，然后以該可能解為出發(fā)點(diǎn)，搜索第二層的一個(gè)可能解（試探） 。如果搜索到第二層的一個(gè)可能解，則繼續(xù)搜索第三層得一個(gè)可能解。依次類推，直到所有層得可能解都被找到，則得到了該問題的一個(gè)完整解。如果第二層所有的肯可能解都不滿足約束條件，則返回第一層，放棄原有的可能解，使用第一層的下一個(gè)可能解（回溯） 。一次類

57、推，尋找第二層的一個(gè)可能解?；厮莘ㄏ鄬τ谄渌F舉的特點(diǎn)在于，不必把問題的每一層的所有可能解都遍歷一遍，只要當(dāng)前的可能解不滿足約束條件就拋棄該解，尋求下一個(gè)可能解，而不必求解其余的下層解。當(dāng)當(dāng)前層得所有可能解都不滿足約束條件，則回溯到上一層，拋棄上一層的當(dāng)前可能解。從以上分析中結(jié)合數(shù)獨(dú)問題的規(guī)則，得出數(shù)獨(dú)問題的約束條件為：每一格的數(shù)值圍僅限 1-9每一格的數(shù)字在當(dāng)前行不允許重復(fù)每一格的數(shù)字在當(dāng)前列不允許重復(fù)每一格的數(shù)字在當(dāng)前小宮格不允許重復(fù)由此，回溯法通過約束條件的篩選，在所有解中除掉不可能的解，從而獲得問題的一個(gè)或者全部解。4.3.2 檢測填充結(jié)果根據(jù)數(shù)獨(dú)游戲的規(guī)則，玩家填充 81 個(gè)宮格之后

58、，要滿足所有行，所有列和所有小九宮格不能出現(xiàn)重復(fù)的數(shù)字，并以此為條件進(jìn)行檢測。列檢測首先對各列進(jìn)行檢測，提供了檢測列 9 個(gè)數(shù)字是否有重復(fù)數(shù)據(jù)的方法checkLine ()，該方法以此遍歷列中的 9 個(gè)數(shù)字，當(dāng)遍歷到某個(gè)數(shù)字時(shí)，檢測該數(shù)字后面的數(shù)字是否出現(xiàn)重復(fù)。比如，當(dāng)檢測到第 3 個(gè)數(shù)字是 7 時(shí)，則檢測第 4-9 個(gè)數(shù)字是否出現(xiàn) 7，如果出現(xiàn)重復(fù)則停止檢測，只有既可以避免重復(fù)檢測，又可以避免遺漏。publicboolean checkLine(int col)/ 檢查列是否符合要求 for(int j = 0;j 8;j+) if(njcol = 0)continue; for(int k

59、 =j + 1;k 9;k+)if(njcol = nkcol)returnfalse; returntrue;行檢測類似于對列數(shù)據(jù)的檢測，還需要對每行進(jìn)行檢測，因此程序提供了對行數(shù)據(jù)的檢測方法 checkRow ()，該方法代碼如下：publicboolean checkRow(int row)/檢查行是否符合要求for(int j = 0;j 8;j+)if(nrowj = 0)continue; for(int k =j + 1;k 9;k+)if(nrowj = nrowk)returnfalse; returntrue;小九宮格檢測29 / 47除了對行和列的重復(fù)數(shù)據(jù)檢測之外，還需要

60、對小九宮格的所有數(shù)字進(jìn)行檢測，避免出現(xiàn)重復(fù)現(xiàn)象。檢測原理與行，列檢測一樣，但需要計(jì)算九宮格數(shù)字的位置。Row 和 Col 指定了檢測九宮格的位置，數(shù)獨(dú)單元格中一共有 33 個(gè)九宮格，Row 和 Col 的圍為 0 到 2。用以下程序完成九宮格重復(fù)數(shù)字的檢測。publicboolean checkNine(int row,int col)/檢查3X3區(qū)域是否符合要求int j = row/3*3;/獲得左上角的坐標(biāo)int k = col/3*3;for(int i = 0;i 8;i+)/循環(huán)比較if(nj + i/3k + i % 3 = 0)continue;for(int m = i+ 1;m 9;m+)