數(shù)獨(dú)游戲?qū)嶒?yàn)報(bào)告文檔

文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.文檔來源為:從網(wǎng)絡(luò)收集整理.word版本可編輯.歡迎下載支持.數(shù)獨(dú)游戲?qū)嶒?yàn)報(bào)告篇一：Sudoku數(shù)獨(dú)實(shí)驗(yàn)報(bào)告

Project2：Sudoku實(shí)驗(yàn)報(bào)告

一、算法描述

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

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

算法1：簡單遞歸方法

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

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

先遍歷所有格子，統(tǒng)計(jì)每種格子可能出現(xiàn)數(shù)字的個(gè)數(shù)。每次挑選可能出現(xiàn)數(shù)字個(gè)數(shù)最少的格子來進(jìn)行遞歸。

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

我最開始的想法是窮舉法，隨機(jī)生成滿足行各不相同的9行，再判斷9宮格、每列是否符合要求，符合條件時(shí)，隨機(jī)生成停止。然而，這種算法的當(dāng)然時(shí)間復(fù)雜度顯然是過高。第

99

一步的隨機(jī)生成的次數(shù)是9*9/P9=9608。隨機(jī)生成一組棋盤耗時(shí)就非常大。

后來，我從求解的個(gè)數(shù)的程序獲得啟發(fā)。算法二對(duì)于1000多組解的數(shù)獨(dú)棋盤，解起來也很快。隨機(jī)生成填9個(gè)方格，再用算法一的方法解出來，取第一組正確的解作為棋盤即可生成填好的棋盤。再把一定數(shù)量的格子的數(shù)字隨機(jī)刪除，計(jì)算解的個(gè)數(shù)。如果解唯一，就得到了棋盤。

二、

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

這兩種算法的數(shù)據(jù)結(jié)構(gòu)不是非常復(fù)雜，只是普通的數(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ā)現(xiàn)這種算法可能會(huì)用到10秒以上的時(shí)間，并且測(cè)試數(shù)據(jù)不同，時(shí)間差異非常大。

我認(rèn)為，這種算法的漏洞在于，如果開始的格子可能出現(xiàn)的數(shù)字非常多，遞歸樹開始的枝會(huì)非常多。并且，我們一般做數(shù)獨(dú)題，都會(huì)先挑可能出現(xiàn)數(shù)字個(gè)數(shù)最少的格子來填，充分利用了已知條件。然而，這種算法只按格子的行列順序來試驗(yàn)，顯然非常傻。于是，我想出了第二種算法。

算法2：

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

四、

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

算法一：

算法二：

五、

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

五、總結(jié)和反思

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

這次Project讓我不斷思考，改進(jìn)了最初的算法。編程是確實(shí)是一個(gè)克服困難、不斷改進(jìn)與超越的過程?？傆行碌臄?shù)據(jù)擺在面前，把原來的算法打擊得很慘，激勵(lì)著我們研究更加先進(jìn)的算法。

篇二：android課程設(shè)計(jì)報(bào)告(數(shù)獨(dú)游戲)

?

河南科技學(xué)院

《物聯(lián)網(wǎng)移動(dòng)應(yīng)用開發(fā)》課程設(shè)計(jì)報(bào)告

設(shè)計(jì)題目：基于android的數(shù)獨(dú)游戲設(shè)計(jì)班級(jí)：學(xué)號(hào)：XX156555姓名：胡建剛指導(dǎo)教師：許睿成績：

信息工程學(xué)院

課程設(shè)計(jì)報(bào)告說明

一、寫報(bào)告前，請(qǐng)認(rèn)真閱讀《課程設(shè)計(jì)報(bào)告說明》。

二、打印裝訂要求

1、一律用A4紙，雙面打印，并左側(cè)裝訂。報(bào)告正文部分均采用宋體小四。《課程設(shè)計(jì)報(bào)告說明》頁也打印。

2、課程設(shè)計(jì)概述部分占一頁；課程設(shè)計(jì)內(nèi)容長度根據(jù)實(shí)際需要填寫；結(jié)論和指導(dǎo)教師評(píng)語及成績單獨(dú)占一頁。保證打印格式工整。

3、指導(dǎo)教師評(píng)語及成績部分由指導(dǎo)教師填寫。

三、報(bào)告內(nèi)容要求

1、課程設(shè)計(jì)目的結(jié)合實(shí)際自己寫，不要雷同。

2、課程設(shè)計(jì)原理簡要說明所完成課程設(shè)計(jì)項(xiàng)目所涉及的理論知識(shí)。

3、課程設(shè)計(jì)內(nèi)容這是課程設(shè)計(jì)報(bào)告極其重要的內(nèi)容。概括整個(gè)課程設(shè)計(jì)過程。（最好在上述內(nèi)容基礎(chǔ)上畫出相應(yīng)的流圖、設(shè)計(jì)思路和設(shè)計(jì)方法，再配以相應(yīng)的文字進(jìn)行說明。）

篇三：人工智能課程設(shè)計(jì)報(bào)告(數(shù)獨(dú)游戲)

人工智能課程設(shè)計(jì)報(bào)告

數(shù)獨(dú)游戲

班級(jí)：

學(xué)號(hào)：

姓名：指導(dǎo)老師：日期：

一、游戲介紹：

在9×9的格子中，用1到9共9個(gè)阿拉伯?dāng)?shù)字填滿整個(gè)格子。

要求：1.每一行都用到1到9，位置不限

2.每一列都用到1到9，位置不限

3.每3×3的格子都用到1到9，位置不限

開始時(shí)：填完后：

二、程序?qū)崿F(xiàn)的功能

1、玩家可以選擇游戲的難易程度

2、玩家可以自己填數(shù)字

3、電腦直接顯示答案

4、玩家如果不想玩可以開始新游戲

三、使用說明

運(yùn)行Sudoku.exe程序，初始選擇為簡單模式，玩家可以自己選擇，然后點(diǎn)擊“開始游戲”，上面顯示玩家用的時(shí)間，如果玩家想自己填數(shù)字，直接點(diǎn)要填的空格會(huì)出現(xiàn)一個(gè)編輯框，在里面輸入要填的數(shù)字，按回車鍵。想直接顯示結(jié)果，點(diǎn)擊“顯示答案”。點(diǎn)擊“開始游戲”可以開始新一盤游戲。

四、算法設(shè)計(jì)

1、算法思想：

本算法采用“挖洞”思想。經(jīng)過以下兩步生成數(shù)獨(dú)題：1)運(yùn)用拉斯維加斯隨機(jī)算法生成一個(gè)終盤；2)采用以下3個(gè)操作“抹去”一部分?jǐn)?shù)字來生成數(shù)獨(dú)題：①根據(jù)所需要的難度等級(jí)選取一種挖洞順序；②通過深度優(yōu)先搜索來求解，從而保證“挖去”一個(gè)數(shù)字后該數(shù)獨(dú)題仍有唯一解③引入剪枝技術(shù)來避免無效的“挖洞”嘗試。

偽代碼：

start生成一個(gè)完整的終盤；

if(true)生成成功；

else進(jìn)行循環(huán)，直到終盤為true，即可解；

then按照難易成都，隨機(jī)去掉幾個(gè)數(shù)，進(jìn)行檢測(cè)；

if(檢測(cè)成功)｛輸出｝；

else｛重新“挖洞”｝，直到成功；

2、問題的分析

要能保證算法生成的數(shù)獨(dú)題具有可變化的難度和唯一解，該算法內(nèi)部應(yīng)該包含有對(duì)數(shù)獨(dú)題的求解和評(píng)級(jí)功能。在此將該算法的設(shè)計(jì)工作分為生成、求解2部分工作（均在類KSudokuCaculate中）：

（1）先生成一個(gè)終盤，存在一個(gè)二維數(shù)組中。

（2）根據(jù)游戲者需求的難度等級(jí)，我們從已知格的總數(shù)和分布來確定“挖去”的個(gè)數(shù)。

3、生成終盤（算法如下）建立一個(gè)新類KSudokuCaculate，在類里面編寫下面源代碼

boolKSudokuCaculate::MakeSudokuData(SUDOKUMATRIXnGameData){

boolbRet=false;

//PROCESS_ERROR(NULL!=nGameData);//判斷指針是否為空

bRet=true;

//先隨機(jī)生成中間g_nSmallSize×方格_nSmallSize方格的個(gè)數(shù)字

RandomCenter();

//先后產(chǎn)生其他g_nSmallSize×方格_nSmallSize方格的個(gè)數(shù)字

CacMiddleUpAndDown();CacMiddleLeftAndRight();

CacCorner();

//將生成的矩陣復(fù)制輸出到參數(shù)中for(intnRow=0;nRow{

for(intnCol=0;nCol{

nGameData[nRow][nCol]=nMatrix[nRow][nCol];

}

}

Exit0:

returnbRet;

}

/**

*&brief用于隨機(jī)生成中間×方格的個(gè)數(shù)字

*&return若成功生成則返回true,否則返回false*/

boolKSudokuCaculate::RandomCenter(void)

{

//nHasAssign[i]標(biāo)志數(shù)字i+1是否已經(jīng)被分配

intnHasAssign[g_nSize]={0};intnRow,nCol,nNum;

srand(time(0));

for(nRow=g_nSmallSize;nRowfor(nCol=g_nSmallSize;nCol{

nNum=rand()%g_nSize;//隨機(jī)生成-9中的一個(gè)數(shù)字while(0!=nHasAssign[nNum])//選擇一個(gè)沒有分配的數(shù)字nNum=rand()%g_nSiz(原文來自：小草范文網(wǎng):數(shù)獨(dú)游戲?qū)嶒?yàn)報(bào)告)e;

nMatrix[nRow][nCol]=nNum+1;

nHasAssign[nNum]=1;

}

returntrue;

}

//根據(jù)中間的方格數(shù)字經(jīng)過列變換計(jì)算出中間上面和下面×方格內(nèi)的數(shù)字//若成功生成則返回true,否則返回false

boolKSudokuCaculate::CacMiddleUpAndDown(void)

{

intnUp;//上面方格的x坐標(biāo)差

intnDown;//下面方格的x坐標(biāo)差

intnRow,nCol;

//交換中間第一列

nCol=g_nSmallSize;

nUp=1;

nDown=2;

for(nRow=g_nSmallSize;nRow{

//復(fù)制數(shù)字

nMatrix[nRow-g_nSmallSize][nCol+nUp]=nMatrix[nRow][nCol];nMatrix[nRow+g_nSmallSize][nCol+nDown]=nMatrix[nRow][nCol];}

//交換中間第二列nCol++;

nUp=1;

nDown=-1;

for(nRow=g_nSmallSize;nRow//復(fù)制數(shù)字

nMatrix[nRow-g_nSmallSize][nCol+nUp]=nMatrix[nRow][nCol];nMatrix[nRow+g_nSmallSize][nCol+nDown]=nMatrix[nRow][nCol];}

//交換中間第三列

nCol++;

nUp=-2;

nDown=-1;

for(nRow=g_nSmallSize;nRow//復(fù)制數(shù)字

nMatrix[nRow-g_nSmallSize][nCol+nUp]=nMatrix[nRow][nCol];nMatrix[nRow+g_nSmallSize][nCol+nDown]=nMatrix[nRow][nCol];