在上一篇博文介紹了用矩陣轉(zhuǎn)換法來產(chǎn)生數(shù)獨(dú)終盤。關(guān)于矩陣轉(zhuǎn)換法產(chǎn)生終盤矩陣請(qǐng)參考如下的文章。

[b]Swing數(shù)獨(dú)游戲(一)：終盤生成之矩陣轉(zhuǎn)換法 [/b]==> [url]http://mouselearnjava.iteye.com/blog/1941483[/url]

本篇博文將對(duì)數(shù)獨(dú)游戲隨機(jī)產(chǎn)生數(shù)獨(dú)終盤展開說明。

[size=medium][color=blue][b]用什么樣的隨機(jī)方法？[/b][/color][/size]

讀過一些文章，關(guān)于隨機(jī)產(chǎn)生數(shù)據(jù)終盤比較流行的是將拉斯維加斯算法與回溯法相結(jié)合。比如下面的文章都有提及：

[url]http://zhangroup.aporc.org/images/files/Paper_3485.pdf[/url]
[url]http://wenku.baidu.com/view/f9e3f17101f69e31433294e1.html[/url]

[img]http://dl2.iteye.com/upload/attachment/0089/2557/e887ce09-1027-319f-b4d1-cf4a7947f2f8.jpg[/img]

看了如下PPT: Java算法[url]http://wenku.baidu.com/view/0a67634de518964bcf847c80.html[/url]

[img]http://dl2.iteye.com/upload/attachment/0089/2564/4105d102-57b2-3228-8aa9-dd18e581007e.jpg[/img]

[img]http://dl2.iteye.com/upload/attachment/0089/2566/3e2b4b61-33d4-3787-8b86-da572118371d.jpg[/img]

從上面的兩個(gè)PPT截圖中可以看出，拉斯維加斯算法思想去解決N皇后時(shí)所花費(fèi)的時(shí)間不少。
數(shù)獨(dú)中的判斷不比N皇后少，如果想要在1秒內(nèi)或者更短的時(shí)間產(chǎn)生1000個(gè)數(shù)獨(dú)終盤，個(gè)人覺得并不是很容易（當(dāng)然了，這個(gè)希望以后去證明一下是正確的 :)）。

所以，我想選擇另外的途徑去完成。

[size=medium][color=blue][b]我的隨機(jī)方法思想[/b][/color][/size]

在給出我的隨機(jī)方法思想之前，我們先來看看數(shù)獨(dú)終盤的數(shù)量。

[b]終盤數(shù)量[/b]

終盤數(shù)量數(shù)獨(dú)中的數(shù)字排列千變?nèi)f化，那么究竟有多少種終盤的數(shù)字組合呢？
6,670,903,752,021,072,936,960（約有[b]6.67×10的21次方[/b]）種組合，2005年由Bertram Felgenhauer和Frazer Jarvis計(jì)算出該數(shù)字，并將計(jì)算方法發(fā)布在他們網(wǎng)站上，[b]如果將等價(jià)終盤（如旋轉(zhuǎn)、翻轉(zhuǎn)、行行對(duì)換，數(shù)字對(duì)換等變形）不計(jì)算，則有5,472,730,538個(gè)組合[/b]。數(shù)獨(dú)終盤的組合數(shù)量都如此驚人，那么數(shù)獨(dú)題目數(shù)量就更加不計(jì)其數(shù)了，因?yàn)槊總€(gè)數(shù)獨(dú)終盤又可以制作出無數(shù)道合格的數(shù)獨(dú)題目。
-- 參考自[url]http://baike.baidu.com/link?url=ePXUCvpBaRKBkEA3pVfOkg3m-NBozO6a4GDS0N3E5_gK1nnJCDzd5O-YL1w7c5S3[/url]


[color=blue][b]按照這個(gè)數(shù)量，如果我們將一個(gè)[1,2,3,4,5,6,7,8,9]的數(shù)組隨機(jī)化，然后將其作為一行數(shù)據(jù)添加到一個(gè)二維數(shù)組中去，該行能滿足數(shù)獨(dú)終盤規(guī)則的概率是很大的。[/b][/color]

[b]基于這個(gè)假設(shè)(假設(shè)的有效性會(huì)在文章后面驗(yàn)證)，我的隨機(jī)算法思想如下：[/b]

[list]
[*][b]1. 寫一個(gè)方法用于獲取一個(gè)由1到9九個(gè)數(shù)隨機(jī)排列的一維數(shù)組。
[*]2. 循環(huán)行(下標(biāo)從0到8)，將這個(gè)隨機(jī)產(chǎn)生的一維數(shù)組作為當(dāng)前行的內(nèi)容，如果是第一行（行標(biāo)為0），那么直接作為該行的內(nèi)容。如果是其它行，則驗(yàn)證數(shù)據(jù)是否都符合條件。
[*] 如果符合條件，則再產(chǎn)生一個(gè)由1到9九個(gè)數(shù)隨機(jī)排列的一維數(shù)組作為下一行的內(nèi)容并驗(yàn)證數(shù)據(jù)是否可用。
[*] 如果不符合條件，則將該行數(shù)據(jù)設(shè)置為0，調(diào)整row和col，產(chǎn)生一個(gè)由1到9九個(gè)數(shù)隨機(jī)排列的一維數(shù)組，重新對(duì)該行驗(yàn)證。
[*]3. 程序中為了防止產(chǎn)生一維隨機(jī)數(shù)組的方法調(diào)用很多次而沒有產(chǎn)生結(jié)果，設(shè)置一個(gè)最多調(diào)用該方法次數(shù)的閾值，當(dāng)達(dá)到這個(gè)閾值還沒有產(chǎn)生結(jié)果，重新從 row =0 col =0 開始。[/b]
[/list]

實(shí)現(xiàn)的程序如下：

package my.utils.algorithm.sudoku;

import java.util.Random;

public class SudokuPuzzleGenerator {

private Random random = new Random();

/**運(yùn)行此程序300次，最大值是217，最小值11，平均約等于50
* 閾值設(shè)置為220， 能滿足大部分程序，二維矩陣不會(huì)置為0，重新再產(chǎn)生值。
*/
private static final int MAX_CALL_RANDOM_ARRAY_TIMES = 220;

/**記錄當(dāng)前buildRandomArray()方法調(diào)用的次數(shù)*/
private int currentTimes = 0;

public int[][] generatePuzzleMatrix() {

int[][] randomMatrix = new int[9][9];

for (int row = 0; row < 9; row++) {
if (row == 0) {
currentTimes = 0;
randomMatrix[row] = buildRandomArray();

} else {
int[] tempRandomArray = buildRandomArray();

for (int col = 0; col < 9; col++) {
if (currentTimes < MAX_CALL_RANDOM_ARRAY_TIMES) {
if (!isCandidateNmbFound(randomMatrix, tempRandomArray,
row, col)) {

/*
* 將該行的數(shù)據(jù)置為0，并重新為其準(zhǔn)備一維隨機(jī)數(shù)數(shù)組
*/
resetValuesInRowToZero(randomMatrix,row);
row -= 1;
col = 8;
tempRandomArray = buildRandomArray();
}
} else {
/*
* 將二維矩陣中的數(shù)值置為0，
* row賦值為-1 col賦值為8， 下一個(gè)執(zhí)行的就是row =0 col=0，
*
* 重頭開始
*/
row = -1;
col = 8;
resetValuesToZeros(randomMatrix);
currentTimes = 0;
}
}
}
}
return randomMatrix;
}

private void resetValuesInRowToZero(int[][] matrix, int row)
{
for (int j = 0; j < 9; j++) {
matrix[row][j] = 0;
}

}

private void resetValuesToZeros(int[][] matrix) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
matrix[row][col] = 0;
}
}
}

private boolean isCandidateNmbFound(int[][] randomMatrix,
int[] randomArray, int row, int col) {
for (int i = 0; i < randomArray.length; i++) {
/**
* 試著給randomMatrix[row][col] 賦值,并判斷是否合理
*/

randomMatrix[row][col] = randomArray[i];
if (noConflict(randomMatrix, row, col)) {
return true;
}
}
return false;
}

private boolean noConflict(int[][] candidateMatrix, int row, int col) {
return noConflictInRow(candidateMatrix, row, col)
&& noConflictInColumn(candidateMatrix, row, col)
&& noConflictInBlock(candidateMatrix, row, col);
}

private boolean noConflictInRow(int[][] candidateMatrix, int row, int col) {
/**
* 因?yàn)楫a(chǎn)生隨機(jī)數(shù)矩陣是按照先行后列，從左到右產(chǎn)生的 ，該行當(dāng)前列后面的所有列的值都還是0， 所以在行比較的時(shí)候，
* 只要判斷該行當(dāng)前列與之前的列有無相同的數(shù)字即可。
*
*/
int currentValue = candidateMatrix[row][col];

for (int colNum = 0; colNum < col; colNum++) {
if (currentValue == candidateMatrix[row][colNum]) {
return false;
}
}

return true;
}

private boolean noConflictInColumn(int[][] candidateMatrix, int row, int col) {

/**
* 與noConflictInRow(...)方法類似：
*
*
* 因?yàn)楫a(chǎn)生隨機(jī)數(shù)矩陣是按照先行后列，從左到右產(chǎn)生的，該列當(dāng)前行后面的所有行的值都還是0，
*
* 所以在列比較的時(shí)候， 只要判斷該列當(dāng)前行與之前的行有無相同的數(shù)字即可。
*
*/

int currentValue = candidateMatrix[row][col];

for (int rowNum = 0; rowNum < row; rowNum++) {
if (currentValue == candidateMatrix[rowNum][col]) {
return false;
}
}

return true;
}

private boolean noConflictInBlock(int[][] candidateMatrix, int row, int col) {

/**
* 為了比較3 x 3 塊里面的數(shù)是否合理， 需要確定是哪一個(gè)Block，我們先要求出3 x 3的起始點(diǎn)。 比如： Block 1
* 的起始點(diǎn)是[0][0] Block 2 的起始點(diǎn)是[3]][0]
*
* ... Block 9 的起始點(diǎn)是[6][6]
*/

int baseRow = row / 3 * 3;
int baseCol = col / 3 * 3;

for (int rowNum = 0; rowNum < 8; rowNum++) {
if (candidateMatrix[baseRow + rowNum / 3][baseCol + rowNum % 3] == 0) {
continue;
}
for (int colNum = rowNum + 1; colNum < 9; colNum++) {
if (candidateMatrix[baseRow + rowNum / 3][baseCol + rowNum % 3] == candidateMatrix[baseRow
+ colNum / 3][baseCol + colNum % 3]) {
return false;
}
}
}
return true;

}

/**
* 返回一個(gè)有1到9九個(gè)數(shù)隨機(jī)排列的一維數(shù)組,
*/
private int[] buildRandomArray() {
currentTimes++;
int[] array = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int randomInt = 0;
/*
* 隨機(jī)產(chǎn)生一個(gè)1到8的隨機(jī)數(shù)，使得該下標(biāo)的數(shù)值與下標(biāo)為0的數(shù)值交換，
*
* 處理20次，能夠獲取一個(gè)有1到9九個(gè)數(shù)隨機(jī)排列的一維數(shù)組,
*/
for (int i = 0; i < 20; i++) {
randomInt = random.nextInt(8) + 1;
int temp = array[0];
array[0] = array[randomInt];
array[randomInt] = temp;
}

return array;
}

/**
* @return the currentTimes
*/
public int getCurrentTimes() {
return currentTimes;
}

/**
* @param currentTimes the currentTimes to set
*/
public void setCurrentTimes(int currentTimes) {
this.currentTimes = currentTimes;
}

}
[b]

[size=medium][color=blue][b]假設(shè)有效性驗(yàn)證及閾值設(shè)定[/b][/color][/size]

針對(duì)上述的代碼，我跑10組，每組30個(gè)實(shí)例，看看這300個(gè)例子中，產(chǎn)生數(shù)獨(dú)終盤所需要調(diào)用隨機(jī)產(chǎn)生由1到9的一維數(shù)組的次數(shù)各是多少， 結(jié)果如下：

[img]http://dl2.iteye.com/upload/attachment/0089/2535/0c1df9c0-bad5-3fa5-8393-d4298f635528.jpg[/img]

從上面的結(jié)果圖中可以看出：[[color=blue]b]300個(gè)實(shí)例中，調(diào)用次數(shù)最小的為11，接近理想最小調(diào)用次數(shù)9.

最大值為217次，平均約50次。而且大部分實(shí)例調(diào)用的次數(shù)在100以內(nèi)。

從這些數(shù)據(jù)[/color]分析中，上述假設(shè)基本上是合適的，閾值最后選擇了接近實(shí)驗(yàn)最大值217的220.[/b]

[size=medium][color=blue][b]效果和結(jié)論[/b][/color][/size]

選擇產(chǎn)生不同的數(shù)目的數(shù)獨(dú)終盤，看看執(zhí)行的時(shí)間。
[img]http://dl2.iteye.com/upload/attachment/0089/2553/1e7bb208-1dd9-3469-97e3-f370f9296e14.jpg[/img]

[img]http://dl2.iteye.com/upload/attachment/0089/2555/772bbfe7-f06e-3f93-91cb-ecb4616f65d6.jpg[/img]


[b]結(jié)論：[/b]

[b]1. 在打印二維數(shù)組到控制臺(tái)顯示的情況下，產(chǎn)生10萬個(gè)隨機(jī)數(shù)獨(dú)終盤的時(shí)間差不多1分鐘左右。
2. 在打印二維數(shù)組到控制臺(tái)顯示的情況下，產(chǎn)生1000個(gè)隨機(jī)數(shù)獨(dú)終盤的時(shí)間差不到1秒，這個(gè)正是我們之前所期望的。
3. 產(chǎn)生大數(shù)目的隨機(jī)終盤，將二維數(shù)組打印到控制臺(tái)顯示的時(shí)間占據(jù)總時(shí)間的60%左右。
如果不在控制臺(tái)輸出二維數(shù)組，花費(fèi)的時(shí)間將少很多。 看上面的折線就可以知道。[/b]

[b]總的來說，效果還是比較不錯(cuò)的，比較適合一下需要產(chǎn)生很多的數(shù)獨(dú)終盤的情況，比如：初始化1000個(gè)或者更多個(gè)數(shù)獨(dú)終盤并寫入文件，然后作為數(shù)獨(dú)游戲的每關(guān)內(nèi)容。[/b]

在下一篇博文中將介紹使用“挖洞”的思想去生成數(shù)獨(dú)難題。

使用在Console打印出隨機(jī)產(chǎn)生二維矩陣的的測(cè)試代碼，及其產(chǎn)生50000個(gè)和100000個(gè)二維矩陣的結(jié)果截圖如下：[/b]


public class Main {
public static void main(String[] args) {
SudokuPuzzleGenerator sudokuPuzzleGenerator = new SudokuPuzzleGenerator();
long start = System.currentTimeMillis();
int numOfSudokuMatrix = 10000;
for (int count = 1; count <= numOfSudokuMatrix; count++) {
System.out.println("第" + count + "個(gè)");
int[][] randomMatrix = sudokuPuzzleGenerator.generatePuzzleMatrix();
printMatrix(randomMatrix);
}

long end = System.currentTimeMillis();

System.out.println("產(chǎn)生"+numOfSudokuMatrix+"個(gè)數(shù)獨(dú)矩陣花費(fèi)時(shí)間: " + ((end - start) / 1000.0)
+ " 秒");


}

public static void printMatrix(int[][] randomMatrix) {
for (int rowNum = 0; rowNum < 9; rowNum++) {
for (int colNum = 0; colNum < 9; colNum++) {
System.out.print(randomMatrix[rowNum][colNum] + " ");
}
System.out.println();
}
}
}


[img]http://dl2.iteye.com/upload/attachment/0089/2537/6ab07468-e52e-305e-959b-5facb63f356d.jpg[/img]

[img]http://dl2.iteye.com/upload/attachment/0089/2539/83da46e8-2e96-3a04-b66c-0e4208ce3d24.jpg[/img]


在下一篇博文中將介紹使用“挖洞”的思想去生成數(shù)獨(dú)難題。

轉(zhuǎn)載請(qǐng)注明出處：[url]http://mouselearnjava.iteye.com/blog/1941693[/url]

總結(jié)

以上是生活随笔為你收集整理的Swing数独游戏(二)：终盘生成之随机法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。