数独问题流程图_数独-分析、设计、求解思路
需求分析
需求
運(yùn)行一個(gè)命令行程序，程序能：
1. 生成不重復(fù)的數(shù)獨(dú)終局至文件。
2. 讀取文件內(nèi)的數(shù)獨(dú)問(wèn)題，求解并將結(jié)果輸出到文件。
數(shù)據(jù)建模
將數(shù)獨(dú)分成9個(gè)宮進(jìn)行求解，ER表示如下，因?yàn)閿?shù)獨(dú)左上角第一塊確定，所以將其看作數(shù)獨(dú)的屬性。
功能建模
數(shù)據(jù)源：用戶
數(shù)據(jù)終點(diǎn)：文件
主要數(shù)據(jù)流：生成指令、求解指令、數(shù)獨(dú)(待求解)，以及終局
主要支持文件：待求解數(shù)獨(dú)文件
主要處理過(guò)程：生成終局、求解數(shù)獨(dú)
0層圖
對(duì)系統(tǒng)進(jìn)行求精，劃分系統(tǒng)的子系統(tǒng)。
行為建模
解題思路
在最開(kāi)始拿到題目的時(shí)候，想起上學(xué)期算法課程學(xué)過(guò)的回溯算法，決定用會(huì)回溯算法進(jìn)行實(shí)現(xiàn)，所以翻看了算法設(shè)計(jì)的課本和ppt，對(duì)回溯算法重新進(jìn)行了學(xué)習(xí)。在生成n個(gè)不同局面和求解給定數(shù)獨(dú)的思路大致一致，但有在細(xì)節(jié)處的處理有些不同。首先是生成n個(gè)不同的局面，按行進(jìn)行循環(huán)，有一個(gè)二維數(shù)組保存每個(gè)位置的可能數(shù)字，從可能數(shù)字中隨機(jī)選一個(gè)放在該位置，若該位置找不到可能的位置，則回到上一個(gè)，修改上一個(gè)位置的解。不斷進(jìn)行回溯，直到所有的位置都合法。若是對(duì)給定局面進(jìn)行求解，則將空白位置用數(shù)組記錄下來(lái)，只對(duì)空白位置進(jìn)行回溯即可。
但在該回溯算法中，搜索時(shí)盲目的，效率較低，最差的實(shí)現(xiàn)對(duì)每個(gè)空方格試探所有可能的數(shù)字，有大量的時(shí)間浪費(fèi)。并且如果需要生成多個(gè)終局時(shí)，每一個(gè)終局都是通過(guò)回溯實(shí)現(xiàn)，且生成不同的終局由Random()進(jìn)行數(shù)字選擇實(shí)現(xiàn)，但實(shí)際上Random生成偽隨機(jī)數(shù)，在一定時(shí)間會(huì)生成相同隨機(jī)數(shù)，無(wú)法保證在生成終局?jǐn)?shù)目足夠大時(shí)，不會(huì)產(chǎn)生兩個(gè)相同的終局。
因?yàn)樗惴ㄐ视泻艽蟮母倪M(jìn)空間，以及無(wú)法保證在n足夠大時(shí)，所有終局都相異，所以在對(duì)代碼重構(gòu)的過(guò)程中，引入了排列組合的算法，對(duì)原有進(jìn)行優(yōu)化。將數(shù)獨(dú)分成9個(gè)3X3的小方塊，每個(gè)小方塊是一個(gè)宮。
參考維基百科提供的一個(gè)生成終局思路，由第一宮生成其余八個(gè)宮。對(duì)第一宮中的塊進(jìn)行排列組合即可，因?yàn)樯山K局時(shí)，要求左上角的第一個(gè)數(shù)為：(學(xué)號(hào)后兩位相加)%9+1，(1+3)%9+1=5，所以左上角為5，且不允許改變。即在第一宮內(nèi)只有八個(gè)塊可以移動(dòng)，有8!=40320種情況，并且在每一宮內(nèi)(除了第一宮)進(jìn)行列列變換有3!×3!×3!×3!=1296，第二宮和第三宮可以交換，第四宮和第七宮可以交換有2!×2!=4，總共可以生成209,018,880個(gè)終局(大于1,000,000)，此方案可行。
對(duì)于各種全排列，使用遞歸的方式實(shí)現(xiàn)。
設(shè)計(jì)實(shí)現(xiàn)過(guò)程
???編譯器：Intellij IDEA 2019.2
???語(yǔ)言：java
???運(yùn)行環(huán)境：JDK 1.8
活動(dòng)圖
順序圖
下面是生成終局的順序圖
下面是求解數(shù)獨(dú)的順序圖
類圖
???共有三個(gè)類，Main用于判斷輸入是否合法、將終局寫(xiě)入文件、判斷輸入命令是否合法，Generate類用于生成終局，Solve類用于求解數(shù)獨(dú)。
具體代碼說(shuō)明
Generate中主要函數(shù)：
?generateSudoku 外部調(diào)用的接口，傳入一個(gè)n(n<=1,000,000)，即可以生成n個(gè)終局。
createSeed 將第一宮作為種子，進(jìn)行交換操作，得到不同的種子。
createMap 通過(guò)種子的變換，得到該種子生成的第一個(gè)終局。
changeIndex 對(duì)于第一個(gè)終局進(jìn)行行列變換，生成不同的終局。
writeToOutput 將生成的int[ ] [ ]的終局，按照輸出格式要求，存放在一個(gè)char[]中 。
changeIndex流程圖如下
具體實(shí)現(xiàn)代碼如下所示，在goalNum=1時(shí)，不用進(jìn)行變換，在>1開(kāi)始，先交換index[16]和index[17]，即先在第三大列內(nèi)進(jìn)行列變換，可以有6中不同的終局，接著在第二大列內(nèi)進(jìn)行交換，依次類推，到行進(jìn)行交換，可以快速產(chǎn)生大量不相同的終局。
/**
* @Title: changeIndex
* @Description: 對(duì)宮內(nèi)的行列進(jìn)行全排列
* @param a
* @param start
* @param end
* @return void
* @throws
*/
public void changeIndex( int start, int end) {
int i;
//分段進(jìn)行全排列
if (start == end) {
if (end == 5) {
changeIndex( 6, 8);
}else if(end==8){
changeIndex( 12, 14);
}else if(end==14){
changeIndex( 15, 17);
}
else {
writeToOutput();
}
}
else {
for (i = start; i <= end; i++) {
swap(index, start, i);
changeIndex( start + 1, end);
if (nowNum == goalNum) break;
swap(index, start, i);
}
}
}
Solve中主要函數(shù)
findSolution外部調(diào)用的接口，傳入一個(gè)txt的絕對(duì)路徑，即可對(duì)該txt中的數(shù)獨(dú)進(jìn)行求解。
dealFile將txt中的所有數(shù)獨(dú)，存在一個(gè)int[]中，并得到要求解的數(shù)獨(dú)數(shù)目。
initCriterion將Criterion(表示行列宮沒(méi)有用過(guò)的數(shù))初始化，并將數(shù)獨(dú)中出現(xiàn)過(guò)的數(shù)在Criterion進(jìn)行標(biāo)記。
chooseCriterion遞歸對(duì)數(shù)獨(dú)進(jìn)行求解。
chooseCriterion流程圖
chooseCriteron和dealWithCriterion是求解數(shù)獨(dú)的主要兩個(gè)函數(shù)。chooseCriterion中state表示當(dāng)前是否能找到可行解，找到返回true，沒(méi)找返回false。先循環(huán)1-9九個(gè)數(shù)，找到一個(gè)所在行、列、宮都沒(méi)有使用過(guò)的數(shù)放入，然后調(diào)用dealWithCriterion函數(shù)，若后面的位置沒(méi)有待求解位置，則返回true，此時(shí)state為true，結(jié)束求解。若后面仍有待求解位置(a,b)，則dealWithCriterion函數(shù)返回chooseCriterion(a, b)進(jìn)行求解，若可以找到可行解，則前面所求解保留，若找不到，則修改前面找到的可行解。本質(zhì)是利用回溯算法進(jìn)行求解。
起初兩個(gè)函數(shù)寫(xiě)在一起，但在代碼質(zhì)量檢查時(shí)，該函數(shù)復(fù)雜度太高，所以拆分成兩個(gè)函數(shù)
/**
* @Title: chooseCriterion
* @Description: 回溯選擇合適的數(shù)
* @param row
* @param col
* @return boolean
* @throws
*/
private boolean chooseCriterion(int row, int col) {
int value;
boolean state = false;
for (int k = 0; k < 9; k++) {
if(!state) {
value = k + 1;
if (!fill(row, col, value)) {
continue;
}
map[row][col] = value;
usedNum(row, col, value);
state = dealWithCriterion(row, col);
if (!state) {
releaseNum(row, col, value);
map[row][col] = 0;
}
}
}
return state;
}
/**
* @Title: dealWithCriterion
* @Description: 查找是否有空位要求解
* @param row
* @param col
* @return boolean
* @throws
*/
public boolean dealWithCriterion( int row, int col) {
//沒(méi)有空位
boolean state = false;
for (; row < 9; row++) {
for (; col < 9; col++) {
if (map[row][col] == 0) {
state = true;
break;
}
}
if (state)
break;
col = 0;
}
//沒(méi)有空位
if (!state) {
return true;
}
return chooseCriterion(row, col);
}
Main中主要函數(shù)
stringToFile傳入一個(gè)char[]，將其寫(xiě)入可執(zhí)行文件同級(jí)文件夾中的layout.txt(沒(méi)有會(huì)創(chuàng)建)。
isNumeric，whetherSolve，whetherGenerate都是判斷輸入是否合法。
總結(jié)
以上是生活随笔為你收集整理的数独问题流程图_数独-分析、设计、求解思路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 西北大学计算机科学排名,西北大学计算机科
- 下一篇： 记第一次组装台式电脑的小经历