畢業(yè)設(shè)計(jì)（論文）開題報(bào)告：數(shù)獨(dú)問(wèn)題的設(shè)計(jì)算法研究

PAGEPAGE8畢業(yè)設(shè)計(jì)（論文）開題報(bào)告題目數(shù)獨(dú)問(wèn)題的設(shè)計(jì)算法研究專業(yè)信息與計(jì)算科學(xué)姓名班級(jí)學(xué)號(hào)指導(dǎo)教師提交時(shí)間一、綜述本課題的研究動(dòng)態(tài)，說(shuō)明選題的依據(jù)和意義1、本課題研究動(dòng)態(tài)1.1數(shù)獨(dú)研究背景數(shù)獨(dú)是一種源自18世紀(jì)末的瑞士，后在美國(guó)發(fā)展、并在日本得以發(fā)揚(yáng)光大的數(shù)字謎題。世界數(shù)獨(dú)錦標(biāo)賽是世界上規(guī)模最大的數(shù)獨(dú)比賽，由世界智力謎題聯(lián)合會(huì)主辦。首屆世界數(shù)獨(dú)錦標(biāo)賽于2006年在意大利的盧卡舉辦，以后每年舉辦一屆。2013年第八屆世界數(shù)獨(dú)錦標(biāo)賽在中國(guó)的北京舉行。1.2數(shù)獨(dú)玩法數(shù)獨(dú)盤面是個(gè)九宮，每一宮又分為九個(gè)小格。在這八十一格中給出一定的已知數(shù)字和解題條件，利用邏輯和推理，在其他的空格上填入1-9的數(shù)字，使1-9每個(gè)數(shù)字在每一行、每一列和每一宮中都只出現(xiàn)一次。1.3數(shù)獨(dú)的發(fā)展歷程早在數(shù)千年前，中國(guó)人就發(fā)明了九宮圖：在9個(gè)方格中，橫行和豎行的數(shù)字總和是相同的?！皵?shù)獨(dú)”也不是什么新生事物，已經(jīng)存在了數(shù)百年。現(xiàn)今流行的數(shù)獨(dú)于1984年由日本游戲雜志《パズル通信ニコリ》發(fā)表并得了現(xiàn)時(shí)的名稱。數(shù)獨(dú)本是“獨(dú)立的數(shù)字”的省略，因?yàn)槊恳粋€(gè)方格都填上一個(gè)非零的個(gè)位數(shù)。18世紀(jì)，瑞士數(shù)學(xué)家萊昂哈德·歐勒發(fā)明了“拉丁方塊”，但并沒(méi)有受到人們的重視。直到20世紀(jì)70年代，美國(guó)雜志才以“數(shù)字拼圖”的名稱將它重新推出。日本隨后接受并推廣了這種游戲，并且將它改名為“數(shù)獨(dú)”，大致的意思是“獨(dú)個(gè)的數(shù)字”或“只出現(xiàn)一次的數(shù)字”。1.4數(shù)獨(dú)近現(xiàn)代發(fā)展成就自二十一世紀(jì)以來(lái)，數(shù)獨(dú)進(jìn)入了高速發(fā)展期，尤其是計(jì)算機(jī)的快速發(fā)展帶動(dòng)了數(shù)獨(dú)設(shè)計(jì)以及計(jì)算的多元化。還有學(xué)者發(fā)表了一些研究，如：宋韜在文獻(xiàn)[11]中根據(jù)常規(guī)數(shù)獨(dú)問(wèn)題的基本規(guī)則，推導(dǎo)了五項(xiàng)數(shù)獨(dú)求解基礎(chǔ)方法,然后結(jié)合計(jì)算機(jī)程序的實(shí)現(xiàn)，將其設(shè)計(jì)為可各自獨(dú)立執(zhí)行的算法。在此基礎(chǔ)上，以人工求解數(shù)獨(dú)問(wèn)題的思維過(guò)程為依據(jù)，提出了基于策略模式的數(shù)獨(dú)優(yōu)化求解算法。該算法實(shí)現(xiàn)了在數(shù)獨(dú)問(wèn)題的初步推斷和后續(xù)回溯法求解過(guò)程中根據(jù)各單元格出現(xiàn)的不同數(shù)值情況自主判定并選擇執(zhí)行不同的策略，從而通過(guò)較少的運(yùn)算量將未知情況數(shù)量降至最小，提高了計(jì)算機(jī)求解數(shù)獨(dú)的運(yùn)算效率。其中楊曉華教授在文獻(xiàn)[10]中用C語(yǔ)言模擬數(shù)獨(dú)的人工解題思路，用計(jì)算機(jī)模擬人腦解題的方法，提出了數(shù)獨(dú)問(wèn)題人工解法程序?qū)崿F(xiàn)的可能途徑，介紹了唯一法、排除法及回溯法三種解題方法。有利于學(xué)習(xí)C語(yǔ)言及相應(yīng)的編程技巧，嘗試著把人的思維方式轉(zhuǎn)化成相應(yīng)的計(jì)算機(jī)程序，便于人工智能方面的研究。柯春梅教授在文獻(xiàn)[6]中本文首先從標(biāo)準(zhǔn)數(shù)獨(dú)的條件與規(guī)則出發(fā)，引入三元0-1變量,建立標(biāo)準(zhǔn)數(shù)獨(dú)的0-1整數(shù)規(guī)劃模型,根據(jù)模型設(shè)計(jì)LINGO求解程序，用一個(gè)數(shù)獨(dú)難題進(jìn)行驗(yàn)證，說(shuō)明程序計(jì)算的準(zhǔn)確性；然后將標(biāo)準(zhǔn)數(shù)獨(dú)的LINGO求解程序推廣到窗口數(shù)獨(dú)、額外區(qū)域數(shù)獨(dú)、奇偶數(shù)獨(dú)等三種變形數(shù)獨(dú)的求解；最后利用數(shù)獨(dú)聯(lián)盟五段段位考試訓(xùn)練題進(jìn)行驗(yàn)證，運(yùn)算時(shí)間不超過(guò)2秒，準(zhǔn)確率達(dá)到100%，說(shuō)明這些LINGO程序求解數(shù)獨(dú)問(wèn)題,速度快且結(jié)果準(zhǔn)確可靠。2、選題的依據(jù)和意義2.1數(shù)獨(dú)對(duì)近現(xiàn)代的影響在中國(guó)北京有80多所中小學(xué)把數(shù)獨(dú)作為校本課程引進(jìn)課堂；東莞市也有10多家學(xué)校在學(xué)校開設(shè)了數(shù)獨(dú)第二課堂，40多家學(xué)校開過(guò)數(shù)獨(dú)公開課。數(shù)獨(dú)的魅力可不僅僅局限于中國(guó)：牛津大學(xué)為它舉辦程序設(shè)計(jì)大賽，瑞士銀行將它列入招聘員工試題；國(guó)際大學(xué)生建模大賽將它列為賽事選題。英國(guó)、日本等政府把“數(shù)獨(dú)”引進(jìn)學(xué)校課堂，影響數(shù)獨(dú)難度的因素很多，就題目本身而言，包括最高難度的技巧、各種技巧所用次數(shù)、是否有隱藏及隱藏的深度及廣度的技巧組合、當(dāng)前盤面可邏輯推導(dǎo)出的出數(shù)個(gè)數(shù)等等。數(shù)獨(dú)沖出日本成為英國(guó)當(dāng)下的流行游戲，得歸功于曾任香港高等法院法官的高樂(lè)德（WayneGould）。2004年，他在日本旅行的時(shí)候，發(fā)現(xiàn)雜志上介紹的這款游戲，便帶回倫敦向《泰晤士報(bào)》推介并獲得接納。英國(guó)《每日郵報(bào)》也于三日后開始連載，使數(shù)獨(dú)在英國(guó)正式掀起熱潮。數(shù)獨(dú)不僅是報(bào)章增加銷量的法寶，腦筋動(dòng)得快的《泰晤士報(bào)》還做起手機(jī)族的生意，花4.5英鎊就能下載10則數(shù)獨(dú)游戲到手機(jī)上玩。漸漸，其他國(guó)家和地區(qū)受其影響也開始風(fēng)靡數(shù)獨(dú)。2.2數(shù)獨(dú)與生俱來(lái)的獨(dú)特魅力與同類似的填字游戲不同，數(shù)獨(dú)受歡迎的原因之一是它既不需要豐富的百科知識(shí)，也不要掌握大量的詞匯，這使其能迅速為孩子和初學(xué)者所接受。根據(jù)游戲開始時(shí)的方格中已有的數(shù)字和位置，數(shù)獨(dú)難易程度不同，有些復(fù)雜的甚至令數(shù)學(xué)家也不能完成。據(jù)著名的動(dòng)游戲開發(fā)商AstrawareLtd.預(yù)計(jì)，移動(dòng)數(shù)獨(dú)游戲的版本多達(dá)幾十種，Palm和WindowsMobile設(shè)備版本的數(shù)獨(dú)游戲就各有20種左右。Sudokumo推出的移動(dòng)數(shù)獨(dú)游戲，能夠下載到大多數(shù)手機(jī)中。這家位于英國(guó)的游戲軟件公司表示，已經(jīng)在全球賣出了7500套數(shù)獨(dú)游戲，而且來(lái)自用戶的興趣還在增加。數(shù)獨(dú)游戲由數(shù)學(xué)家歐拉發(fā)明,目前在國(guó)內(nèi)外非常流行。通過(guò)對(duì)數(shù)獨(dú)求解及分析，歸納總結(jié)出一套有效的求解算法——整數(shù)規(guī)劃法,以計(jì)算機(jī)直接模擬人腦的思維方式,逐個(gè)排除不可能出現(xiàn)在宮格中的數(shù)字。因?yàn)閿?shù)獨(dú)不僅有趣好玩，還可以增進(jìn)玩者的推理與邏輯能力，這種游戲全面考驗(yàn)做題者觀察能力和推理能力，雖然玩法簡(jiǎn)單，但數(shù)字排列方式卻千變?nèi)f化，所以不少教育者認(rèn)為數(shù)獨(dú)是訓(xùn)練頭腦的絕佳方式。二、本課題研究的基本內(nèi)容，擬解決的主要問(wèn)題和難點(diǎn)問(wèn)題1、基本內(nèi)容本課題研究如何設(shè)計(jì)數(shù)獨(dú)問(wèn)題，探討數(shù)獨(dú)設(shè)計(jì)問(wèn)題的算法并編程實(shí)現(xiàn)。在此過(guò)程中需要了解數(shù)獨(dú)問(wèn)題的由來(lái)，數(shù)獨(dú)問(wèn)題的介紹及各種數(shù)獨(dú)問(wèn)題設(shè)計(jì)的方法，并利用Matlab作為編程軟件，編寫出程序并正確運(yùn)行。本課題研究的數(shù)獨(dú)問(wèn)題所采用的方式便是利用Matlab實(shí)現(xiàn)數(shù)獨(dú)游戲的設(shè)計(jì)，該程序能夠設(shè)置不同難度等級(jí)，實(shí)現(xiàn)數(shù)獨(dú)游戲設(shè)計(jì)的多樣化。設(shè)計(jì)后通過(guò)測(cè)試來(lái)檢驗(yàn)界面操作、數(shù)獨(dú)唯一解和數(shù)獨(dú)功能的完整性。為確保設(shè)計(jì)能夠執(zhí)行相應(yīng)的功能并且存在唯一解，可采取以下設(shè)計(jì)方法：1.唯一解法2.允許數(shù)標(biāo)注法3.已知數(shù)標(biāo)線法4.回溯法其中在編寫數(shù)獨(dú)設(shè)計(jì)程序時(shí)可以考慮人工智能的設(shè)計(jì)方法。所謂人工智能設(shè)計(jì)應(yīng)當(dāng)是設(shè)計(jì)者對(duì)該游戲的特性有較為深入的了解依據(jù)其內(nèi)在聯(lián)系設(shè)計(jì)出的和人類思維相似的解決算法。目的是為了能夠提供更快的更準(zhǔn)確的設(shè)計(jì)方法。2、擬解決的主要問(wèn)題（1）數(shù)獨(dú)問(wèn)題的由來(lái)、數(shù)獨(dú)問(wèn)題的介紹；（2）數(shù)獨(dú)問(wèn)題研究的意義；（2）數(shù)獨(dú)問(wèn)題的終盤的設(shè)計(jì)方法；（3）數(shù)獨(dú)問(wèn)題的一般設(shè)計(jì)方法討論；（4）數(shù)獨(dú)問(wèn)題的（分初級(jí)、中級(jí)、高級(jí)、特級(jí)等級(jí)別）設(shè)計(jì)及其編程實(shí)現(xiàn)；（6）數(shù)獨(dú)問(wèn)題的研究成果及未來(lái)展望。3、難點(diǎn)問(wèn)題（1）特型數(shù)獨(dú)問(wèn)題的設(shè)計(jì)及其編程實(shí)現(xiàn)；（2）額外區(qū)域數(shù)獨(dú)問(wèn)題的設(shè)計(jì)及其編程實(shí)現(xiàn)。三、研究步驟、方法及措施1、了解基本課題，閱讀與課題相關(guān)的各類文獻(xiàn)，會(huì)基本數(shù)獨(dú)解法；1.1被篩選數(shù)標(biāo)線法算法目的數(shù)就是要在某空格填的數(shù).所謂“目的數(shù)標(biāo)線法”,就是從某一個(gè)預(yù)想的目的數(shù)出發(fā)引出標(biāo)線，把這些標(biāo)線集中到某宮、某行、某列，然后在其中排除不允許該目的數(shù)存在的格子，而將目的數(shù)落實(shí)到正確的格子中。1.2回溯法回溯法是一種搜索算法，其基本思路是：在一個(gè)問(wèn)題中，根據(jù)題意給出的邊界條件劃定出所有可能解的范圍（稱為可能解），根據(jù)題意確定出約束條件.利用程序順次在所有可能解中，根據(jù)題意確定出約束條件.利用程序順次在所有可能解中，搜索時(shí)按照深度搜索的方式進(jìn)行.即在第一層選定一個(gè)滿足約束條件的解，然后以該可能解為出發(fā)點(diǎn)，搜索第二層的一個(gè)可能解（試探）.如果搜索到第二層的一個(gè)可能解，則繼續(xù)搜索第三層的一個(gè)可能解.依次類推，直到所有層的可能解被找到，則得到了該問(wèn)題的一個(gè)完整解.如果第二層所有的可能解都不滿足約束條件，則返回第一層，放棄原有的可能解，使用第一層的下一個(gè)可能解（回溯）.以此類推，尋找第二層的一個(gè)可能解。1.3唯一解法當(dāng)某行已填數(shù)字的宮格達(dá)到8個(gè)，那么該行剩余宮格能填的數(shù)字就只剩下那么還沒(méi)出現(xiàn)過(guò)的數(shù)字了，成為行唯一解。同理，當(dāng)某列或某宮已填數(shù)字達(dá)到八個(gè)，那么剩余數(shù)字只剩下未出現(xiàn)的那個(gè)。2、了解數(shù)獨(dú)問(wèn)題的各類設(shè)計(jì)方法，學(xué)習(xí)Matlab軟件編程及其他有關(guān)的知識(shí)點(diǎn)；2.1總體思路先得到一個(gè)完整數(shù)獨(dú)。然后根據(jù)難度需要，有選擇性的的挖出一些空格來(lái)，判斷是否符合條件以及游戲規(guī)則，最后選擇輸出。2.2過(guò)程分析第一行：取1`9個(gè)數(shù)字，打亂后放入第一行的每個(gè)格子里。第二行：由于第一行的限制，這時(shí)每個(gè)格子的數(shù)字可選擇一個(gè)專門的函數(shù)來(lái)確認(rèn)。從第一列開始直至第九列結(jié)束。數(shù)字生成好后，游戲時(shí)隨機(jī)的把部分?jǐn)?shù)字遮蓋住以此生成空格，判斷填入正確與否。3、研究各章數(shù)獨(dú)問(wèn)題的設(shè)計(jì)方法，并對(duì)每種算法的效率作比較；下面一道2013年中國(guó)錦標(biāo)賽數(shù)獨(dú)題目000,009,002;129,000,000;000,207,003;015,030,090;090,040,020;040,070,380;700,503,000;000,000,548;500,100,000在使用MATLAB軟件可以得出，回溯法算法求出此問(wèn)題需要進(jìn)行0.182482秒，整數(shù)規(guī)劃法求出此問(wèn)題需要進(jìn)行2.994893秒，而被篩選數(shù)標(biāo)線法算法求出此問(wèn)題需要進(jìn)行0.291465秒。由此可見回溯法解題效率最高，整數(shù)規(guī)劃法要比回溯法低一些，并且這個(gè)差距會(huì)隨著題目難度的增加而增加。在正文中會(huì)具體介紹到。4、設(shè)計(jì)實(shí)驗(yàn)方案，做出實(shí)驗(yàn)；5、分析實(shí)驗(yàn)結(jié)果，得出結(jié)論。四、工作進(jìn)度序號(hào)設(shè)計(jì)（論文）各階段名稱日期1查閱數(shù)獨(dú)問(wèn)題的資料（網(wǎng)上資料或圖書館資源），熟悉數(shù)獨(dú)問(wèn)題和數(shù)獨(dú)游戲的玩法。1～2周2理解數(shù)獨(dú)問(wèn)題的基本設(shè)計(jì)方法，熟悉Matlab編程軟件。2～3周3畢業(yè)實(shí)習(xí)，撰寫文獻(xiàn)綜述，開題報(bào)告。3～5周4數(shù)獨(dú)問(wèn)題的終盤的設(shè)計(jì)方法及其編程實(shí)現(xiàn)。5～7周5數(shù)獨(dú)問(wèn)題的(分初級(jí)、中級(jí)、高級(jí)、特級(jí)等級(jí)別)設(shè)計(jì)及其編程實(shí)現(xiàn)。18～12周6特型數(shù)獨(dú)問(wèn)題的設(shè)計(jì)及其編程實(shí)現(xiàn)，額外區(qū)域數(shù)獨(dú)問(wèn)題的設(shè)計(jì)及其編程實(shí)現(xiàn)。12～14周7進(jìn)行論文寫作，完成相應(yīng)計(jì)算機(jī)程序的設(shè)計(jì)。14～15周8完善軟件、完成畢業(yè)論文。16周總結(jié)及未來(lái)展望影響數(shù)獨(dú)難度的因素很多，就題目本身而言，包括最高難度的技巧、各種技巧所用次數(shù)、是否有隱藏及隱藏的深度及廣度的技巧組合、當(dāng)前盤面可邏輯推導(dǎo)出的出數(shù)個(gè)數(shù)等等。對(duì)于玩家而言，了解的技巧數(shù)量、熟練程度、觀察力自然也影響對(duì)一道題的難度判斷。同時(shí)由于數(shù)獨(dú)的獨(dú)特魅力所在，由數(shù)獨(dú)引出的其他游戲也吸引了大量玩家，也有眾多的擁護(hù)者，而且與數(shù)獨(dú)有千絲萬(wàn)縷的關(guān)系，比如：數(shù)和（Kakuro）數(shù)圖（Nonograms/Griddlers）數(shù)回（SlitherLink）數(shù)墻（Nurikabe）數(shù)連（NumberLink）數(shù)獨(dú)愛好者同樣不能錯(cuò)過(guò)這些優(yōu)秀的邏輯推理游戲。數(shù)獨(dú)是一種人生，它不允許你填錯(cuò)一個(gè)數(shù)字，否則全盤皆輸！望著全盤的數(shù)字，你不知道哪錯(cuò)了，卻不允許你去涂改，只能重新開始！這就跟我們的學(xué)習(xí)一樣，它要求我們要想好再去做，一步一個(gè)腳印，確定是那個(gè)數(shù)字我們才能下手！每個(gè)數(shù)字都各司其職，都會(huì)有他們并不固定的崗位，有可能我在角落，也有可能我在中間，哪里需要我，我就會(huì)出現(xiàn)在哪！這就要求我們要注意到上下左右以及這小宮格各方面的協(xié)調(diào)！是的我們要有大局觀！喜歡數(shù)獨(dú)的理由無(wú)數(shù)種，因?yàn)檎嫦嘀挥幸粋€(gè)！最后再說(shuō)幾句：生活和做數(shù)獨(dú)一樣，不要輕易放棄。當(dāng)你推斷到自以為山窮水盡時(shí),再用1-9的順序掃一遍,說(shuō)不定就會(huì)有峰回路轉(zhuǎn)的發(fā)現(xiàn)。數(shù)獨(dú)的真正魅力就在于看似簡(jiǎn)單卻蘊(yùn)含了很多不平凡的奧妙。恰恰人生也正像這樣一場(chǎng)游戲，在簡(jiǎn)單的規(guī)則中不斷挑戰(zhàn)自我，專注地生活。最后我衷心的希望每個(gè)人都能從數(shù)獨(dú)的游戲中感悟人生的道理，能在知識(shí)的海洋里遨游感受數(shù)學(xué)，感受數(shù)獨(dú)的樂(lè)趣。六、主要參考文獻(xiàn)[1]商文喜,蔚承建,王開,劉凱.數(shù)獨(dú)問(wèn)題的一個(gè)分布式物理博弈求解[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(12):113-115.

[2]黃祖賢.數(shù)獨(dú)游戲的問(wèn)題生成及求解算法優(yōu)化[J].安徽工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,32(02):187-191.

[3]雷蕾,沈富可.關(guān)于數(shù)獨(dú)問(wèn)題的算法的設(shè)計(jì)與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)(學(xué)術(shù)交流),2007,14(02):481-482+523.

[4]王瓊,鄒晟.數(shù)獨(dú)問(wèn)題的求解、評(píng)價(jià)與生成算法的研究[J].南京師范大學(xué)學(xué)報(bào)(工程技術(shù)版),2010,10(01