數(shù)獨(dú)實(shí)驗(yàn)報(bào)告范文

本文格式為Word版下載后可任意編輯和復(fù)制第第頁(yè)數(shù)獨(dú)實(shí)驗(yàn)報(bào)告范文Sudoku數(shù)獨(dú)試驗(yàn)報(bào)告

一、算法描述

求解Sudoku讓人最簡(jiǎn)單想到的方法是窮舉每個(gè)方格可能的值，假如符合條件，則得到解，不符合條件則進(jìn)行回溯。通過(guò)遞歸的方法，明顯可以得到數(shù)獨(dú)的解。

我想到的簡(jiǎn)潔的遞歸方法，是每一行從左到右，試驗(yàn)每一個(gè)方格可能的數(shù)字，進(jìn)行遞歸。這種方法看似特別麻煩，實(shí)際上對(duì)于一般的數(shù)獨(dú)題，速度是特別快的，思想比較簡(jiǎn)潔，寫(xiě)出來(lái)的代碼也特別簡(jiǎn)潔、易懂。

算法1：簡(jiǎn)潔遞歸方法

從第一個(gè)格開(kāi)頭，從1到9試驗(yàn)，是否滿意行、列、九宮格互不相同的條件。若滿意條件，則填入該數(shù)字，再試驗(yàn)下一個(gè)格。當(dāng)一個(gè)格子消失沒(méi)有數(shù)字能填的狀況時(shí)，說(shuō)明已經(jīng)填的數(shù)字有誤，回溯，再進(jìn)行遞歸。

算法2：優(yōu)化的遞歸算法

先遍歷全部格子，統(tǒng)計(jì)每種格子可能消失數(shù)字的個(gè)數(shù)。每次選擇可能消失數(shù)字個(gè)數(shù)最少的格子來(lái)進(jìn)行遞歸。

設(shè)置三維數(shù)組poss[i][j][k]來(lái)存儲(chǔ)可能消失數(shù)字的信息。poss[i][j][0]記錄i行j列的格子可能消失數(shù)字的個(gè)數(shù)，poss[i][j][k](1算法3：生成數(shù)獨(dú)棋盤(pán)的算法

我最開(kāi)頭的想法是窮舉法，隨機(jī)生成滿意行各不相同的9行，再推斷9宮格、每列是否符合要求，符合條件時(shí)，隨機(jī)生成停止。然而，這種算法的當(dāng)然時(shí)間簡(jiǎn)單度明顯是過(guò)高。第99一步的隨機(jī)生成的次數(shù)是9*9/P9=9608。隨機(jī)生成一組棋盤(pán)耗時(shí)就特別大。后來(lái)，我從求解的個(gè)數(shù)的程序獲得啟發(fā)。算法二對(duì)于1000多組解的數(shù)獨(dú)棋盤(pán)，解起來(lái)也很快。隨機(jī)生成填9個(gè)方格，再用算法一的方法解出來(lái)，取第一組正確的解作為棋盤(pán)即可生成填好的棋盤(pán)。再把肯定數(shù)量的格子的數(shù)字隨機(jī)刪除，計(jì)算解的個(gè)數(shù)。假如解唯一，就得到了棋盤(pán)。

二、數(shù)據(jù)結(jié)構(gòu)

這三種算法的數(shù)據(jù)結(jié)構(gòu)不是特別簡(jiǎn)單，只是一般的數(shù)組。

算法一：數(shù)組a[i][j]

算法二：數(shù)組a[i][j]和poss[i][j][k]

算法三：數(shù)組a[i][j]和poss[i][j][k]

三、時(shí)間效率分析

算法1：這種算法在tsinsen系統(tǒng)上只用了15ms得到全部答案。

雖然這種算法在tsinsen系統(tǒng)的測(cè)試中有很好的表現(xiàn)，但是我試了試在幾道骨灰級(jí)難度的題，發(fā)覺(jué)這種算法可能會(huì)用到10秒以上的時(shí)間，并且測(cè)試數(shù)據(jù)不同，時(shí)間差異特別大。

我認(rèn)為，這種算法的漏洞在于，假如開(kāi)頭的格子可能消失的數(shù)字特別多，遞歸樹(shù)開(kāi)頭的枝會(huì)特別多。并且，我們一般做數(shù)獨(dú)題，都會(huì)先挑可能消失數(shù)字個(gè)數(shù)最少的格子來(lái)填，充分利用了已知條件。然而，這種算法只按格子的行列挨次來(lái)試驗(yàn)，明顯特別傻。于是，我想出了其次種算法。

算法2：這種算法耗時(shí)長(zhǎng)。

特別令人絕望的是，雖然它能在短時(shí)間內(nèi)解出骨灰級(jí)題目，但是，和上一個(gè)算法相比，對(duì)于簡(jiǎn)潔的題目，它比較耗時(shí)。在tsinsen系統(tǒng)中測(cè)試的時(shí)間是91ms。它的缺陷在于，每次遞歸都必需更新（i，j）格子所在的行、列、九宮格全部的元素。每次要求20個(gè)數(shù)的poss[i][j]?；厮萃瑯右?。并且求poss[i][j]的函數(shù)時(shí)間簡(jiǎn)單度是O（n）。每一步所耗時(shí)間比上一種算法多許多。但是，總的試驗(yàn)的步數(shù)能顯著削減。所以，這種算法適用于數(shù)獨(dú)解題的動(dòng)畫(huà)演示和解極難題目。

四、程序結(jié)構(gòu)

五、運(yùn)行結(jié)果

六、總結(jié)和反思

后來(lái)老師提高了難度，要求程序能求出多解數(shù)獨(dú)題的解的個(gè)數(shù)。幾千個(gè)解的數(shù)據(jù)都能快速得出答案，但是幾萬(wàn)個(gè)解的數(shù)據(jù)，需要很長(zhǎng)時(shí)間，更別提幾百萬(wàn)的數(shù)據(jù)。這兩種遞歸的算法都有問(wèn)題，優(yōu)化的空間也有限，需要更強(qiáng)大、高效的算法。

這次Project