本文實(shí)例為大家分享了java回溯算法解數(shù)獨(dú)問題，供大家參考，具體內(nèi)容如下
下面來詳細(xì)講一下如何用回溯算法來解數(shù)獨(dú)問題。
下圖是一個(gè)數(shù)獨(dú)題，也是號(hào)稱世界上最難的數(shù)獨(dú)。當(dāng)然了，對(duì)于計(jì)算機(jī)程序來說，只要算法是對(duì)的，難不難就不知道了，反正計(jì)算機(jī)又不累?；厮菟惴ɑ旧暇褪歉F舉，解這種數(shù)獨(dú)類的問題邏輯比較簡單。
不管算法懂不懂，先把類建出來，變量定義好，那放大學(xué)試卷上就是可以拿兩分了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
package shudu; /** * created by wolf on 2016/3/17. */public class sudoku { private int[][] matrix; public sudoku(int[][] matrix) { this.matrix = matrix; } public static void main(string[] args) { // 號(hào)稱世界上最難數(shù)獨(dú) int[][] sudoku = { {8, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 3, 6, 0, 0, 0, 0, 0}, {0, 7, 0, 0, 9, 0, 2, 0, 0}, {0, 5, 0, 0, 0, 7, 0, 0, 0}, {0, 0, 0, 0, 4, 5, 7, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 3, 0}, {0, 0, 1, 0, 0, 0, 0, 6, 8}, {0, 0, 8, 5, 0, 0, 0, 1, 0}, {0, 9, 0, 0, 0, 0, 4, 0, 0}}; sudoku s = new sudoku(sudoku); s.backtrace(0, 0); } /** * 數(shù)獨(dú)算法 * @param i * 行號(hào) * @param j * 列號(hào) */ private void backtrace(int i, int j) { }} |
用一個(gè)二維數(shù)組來存儲(chǔ)這個(gè)矩陣，然后定義一個(gè)方法來計(jì)算。方法里有兩個(gè)屬性——行號(hào)和列號(hào)。
我們的原理就是從第0行0列開始，依次往里面填入1-9之間的數(shù)字，然后判斷填入的這個(gè)數(shù)字是否能放進(jìn)去（該行該列和它所在的小九宮格是否有重復(fù)數(shù)字）。如果能放進(jìn)去，那么就繼續(xù)用1-9去試該行的下一列。一直到該行的最后一列，然后換行繼續(xù)重復(fù)上面的步驟（也就是執(zhí)行backtrace方法）。一直執(zhí)行到最后一個(gè)空格，也就是i=8,j=8的時(shí)候，且最后這個(gè)空格所放的值也完全符合規(guī)則，那么此時(shí)就算完成，不用再繼續(xù)調(diào)用backtrace方法了，輸出正確解即可。
所以回溯法樣子看起來是這樣的。給第一個(gè)空格填1-9中任何一個(gè)，開始判斷，如果ok，然后進(jìn)入下一層，如果不ok，就斷掉了。下一層還是從1-9開始試，然后ok，不ok……當(dāng)最終目標(biāo)達(dá)到時(shí)，空格已填滿又滿足條件，那么中斷該分支，輸出結(jié)果。
繼續(xù)我們的程序。
由于有些位置已經(jīng)有數(shù)字了，所以我們需要判斷，如果該坑已經(jīng)有人蹲了，那么就把列號(hào)j加1，進(jìn)入下一列。如果到第8列了，就換行。
修改程序如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
package shudu; /** * created by wolf on 2016/3/17. */public class sudoku { private int[][] matrix; public sudoku(int[][] matrix) { this.matrix = matrix; } public static void main(string[] args) { // 號(hào)稱世界上最難數(shù)獨(dú) int[][] sudoku = { {8, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 3, 6, 0, 0, 0, 0, 0}, {0, 7, 0, 0, 9, 0, 2, 0, 0}, {0, 5, 0, 0, 0, 7, 0, 0, 0}, {0, 0, 0, 0, 4, 5, 7, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 3, 0}, {0, 0, 1, 0, 0, 0, 0, 6, 8}, {0, 0, 8, 5, 0, 0, 0, 1, 0}, {0, 9, 0, 0, 0, 0, 4, 0, 0}}; sudoku s = new sudoku(sudoku); s.backtrace(0, 0); } /** * 數(shù)獨(dú)算法 * * @param i 行號(hào) * @param j 列號(hào) */ private void backtrace(int i, int j) { //如果i行j列是空格，那么才進(jìn)入給空格填值的邏輯 if (matrix[i][j] == 0) { for (int k = 1; k <= 9; k++) { //判斷給i行j列放1-9中的任意一個(gè)數(shù)是否能滿足規(guī)則 if (check(i, j, k)) { //將該值賦給該空格，然后進(jìn)入下一個(gè)空格 matrix[i][j] = k; backtrace(i, j + 1); } } } else { //如果該位置已經(jīng)有值了，就進(jìn)入下一個(gè)空格進(jìn)行計(jì)算 backtrace(i, j + 1); } } /** * 判斷給某行某列賦值是否符合規(guī)則 * * @param row 被賦值的行號(hào) * @param line 被賦值的列號(hào) * @param number 賦的值 * @return */ private boolean check(int row, int line, int number) { //判斷該行該列是否有重復(fù)數(shù)字 for (int i = 0; i < 9; i++) { if (matrix[row][i] == number || matrix[i][line] == number) { return false; } } //判斷小九宮格是否有重復(fù) int temprow = row / 3; int templine = line / 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (matrix[temprow * 3 + i][templine * 3 + j] == number) { return false; } } } return true; }} |
此時(shí)已經(jīng)寫好了判斷某行某列賦某個(gè)值是否ok的方法，通過該方法就能校驗(yàn)出數(shù)字是否能放到該位置。
還缺少的是邊界值的判斷，就是當(dāng)已經(jīng)到最后一列了，還沒到最后一行時(shí)，需要對(duì)行號(hào)加1，然后恢復(fù)列號(hào)為0。
修改一下backtrace方法，增加邊界值判斷。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
package shudu; /** * created by wolf on 2016/3/17. */public class sudoku { private int[][] matrix; public sudoku(int[][] matrix) { this.matrix = matrix; } public static void main(string[] args) { // 號(hào)稱世界上最難數(shù)獨(dú) int[][] sudoku = { {8, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 3, 6, 0, 0, 0, 0, 0}, {0, 7, 0, 0, 9, 0, 2, 0, 0}, {0, 5, 0, 0, 0, 7, 0, 0, 0}, {0, 0, 0, 0, 4, 5, 7, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 3, 0}, {0, 0, 1, 0, 0, 0, 0, 6, 8}, {0, 0, 8, 5, 0, 0, 0, 1, 0}, {0, 9, 0, 0, 0, 0, 4, 0, 0}}; sudoku s = new sudoku(sudoku); s.backtrace(0, 0); } /** * 數(shù)獨(dú)算法 * * @param i 行號(hào) * @param j 列號(hào) */ private void backtrace(int i, int j) { if (i == 8 && j == 9) { //已經(jīng)成功了，打印數(shù)組即可 system.out.println("獲取正確解"); printarray(); return; } //已經(jīng)到了列末尾了，還沒到行尾，就換行 if (j == 9) { i++; j = 0; } //如果i行j列是空格，那么才進(jìn)入給空格填值的邏輯 if (matrix[i][j] == 0) { for (int k = 1; k <= 9; k++) { //判斷給i行j列放1-9中的任意一個(gè)數(shù)是否能滿足規(guī)則 if (check(i, j, k)) { //將該值賦給該空格，然后進(jìn)入下一個(gè)空格 matrix[i][j] = k; backtrace(i, j + 1); } } } else { //如果該位置已經(jīng)有值了，就進(jìn)入下一個(gè)空格進(jìn)行計(jì)算 backtrace(i, j + 1); } } /** * 判斷給某行某列賦值是否符合規(guī)則 * * @param row 被賦值的行號(hào) * @param line 被賦值的列號(hào) * @param number 賦的值 * @return */ private boolean check(int row, int line, int number) { //判斷該行該列是否有重復(fù)數(shù)字 for (int i = 0; i < 9; i++) { if (matrix[row][i] == number || matrix[i][line] == number) { return false; } } //判斷小九宮格是否有重復(fù) int temprow = row / 3; int templine = line / 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (matrix[temprow * 3 + i][templine * 3 + j] == number) { return false; } } } return true; } /** * 打印矩陣 */ public void printarray() { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { system.out.print(matrix[i][j] + " "); } system.out.println(); } system.out.println(); }} |
可以看到，判斷成功的標(biāo)志是行號(hào)為8，且列號(hào)為9時(shí)，認(rèn)為找到了正確解。為什么是9呢，因?yàn)樵赾heck(i,j,k)那一步，通過了的話，將值k賦給最后一個(gè)空格，此時(shí)并沒有中斷程序，而且進(jìn)入了下一層循環(huán)backtrace（i，j + 1），所以i為8j為9時(shí)才是終解。程序到這里，運(yùn)行一下看看，發(fā)現(xiàn)并沒有任何輸出值，并沒有找到正確解，why？
下面要講的就是該程序最關(guān)鍵的地方，也是比較難以理解的地方，就是對(duì)根節(jié)點(diǎn)的初始化?；厮菟惴ㄖv究的是一條道走到黑，不撞南墻不回頭，并且把所有的道都走完。
我們把問題簡單化，譬如一共只有兩個(gè)空格，只能放0和1，正確答案是00和11.我們給第一個(gè)空格放了0，此時(shí)我們不知道是否放了0之后，后面是否能完全正確的走完全程。就像走迷宮一樣，你選擇了第一個(gè)岔道，此時(shí)有可能第一個(gè)岔道就是錯(cuò)的，后面無論怎么走都對(duì)了不了，也有可能有多條道可以走。那么我們的做法是先第一步放0，發(fā)現(xiàn)沒問題（符合只能放0和1的規(guī)則），然后走第二步，第二步如果走對(duì)了，那就直接走出去了，獲得了一次正確的解（00）。如果第二步是個(gè)死胡同（01），那就要回頭了，就是要回到原點(diǎn)，把第一步初始化一下，然后第一步走1，然后再繼續(xù)后面的步驟。所以無論怎么樣，你都需要在第二步走完之后，把第一步走的值給清掉，回歸到原點(diǎn)。這樣才能找到所有的正確路線。
問題放大一下，有n步（n未知），第一步有1-9共9種情況，第一步放了1，后面還有未知的步，那無論后面成功與否，你肯定都要去試第一步放2-9之間的數(shù)字。
看第51行for循環(huán)那里，第一次將數(shù)字1賦給第一個(gè)空格。然后判斷是否ok，如果ok了，就進(jìn)入第二個(gè)空格去了，后面具體走多少步我們就不管了，我們只需要在后面的走完之后，初始化第一個(gè)空格就行了。那要是不ok呢，不ok當(dāng)然就不用管他了，這一層走完就沒下文了，等于該分支就斷了。所以我們要在第55行后面加一句初始化的操作matrix[i][j]=0.
完整代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
package shudu; /** * created by wolf on 2016/3/17. */public class sudoku { private int[][] matrix; public sudoku(int[][] matrix) { this.matrix = matrix; } public static void main(string[] args) { // 號(hào)稱世界上最難數(shù)獨(dú) int[][] sudoku = { {8, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 3, 6, 0, 0, 0, 0, 0}, {0, 7, 0, 0, 9, 0, 2, 0, 0}, {0, 5, 0, 0, 0, 7, 0, 0, 0}, {0, 0, 0, 0, 4, 5, 7, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 3, 0}, {0, 0, 1, 0, 0, 0, 0, 6, 8}, {0, 0, 8, 5, 0, 0, 0, 1, 0}, {0, 9, 0, 0, 0, 0, 4, 0, 0}}; sudoku s = new sudoku(sudoku); s.backtrace(0, 0); } /** * 數(shù)獨(dú)算法 * * @param i 行號(hào) * @param j 列號(hào) */ private void backtrace(int i, int j) { if (i == 8 && j == 9) { //已經(jīng)成功了，打印數(shù)組即可 system.out.println("獲取正確解"); printarray(); return; } //已經(jīng)到了列末尾了，還沒到行尾，就換行 if (j == 9) { i++; j = 0; } //如果i行j列是空格，那么才進(jìn)入給空格填值的邏輯 if (matrix[i][j] == 0) { for (int k = 1; k <= 9; k++) { //判斷給i行j列放1-9中的任意一個(gè)數(shù)是否能滿足規(guī)則 if (check(i, j, k)) { //將該值賦給該空格，然后進(jìn)入下一個(gè)空格 matrix[i][j] = k; backtrace(i, j + 1); //初始化該空格 matrix[i][j] = 0; } } } else { //如果該位置已經(jīng)有值了，就進(jìn)入下一個(gè)空格進(jìn)行計(jì)算 backtrace(i, j + 1); } } /** * 判斷給某行某列賦值是否符合規(guī)則 * * @param row 被賦值的行號(hào) * @param line 被賦值的列號(hào) * @param number 賦的值 * @return */ private boolean check(int row, int line, int number) { //判斷該行該列是否有重復(fù)數(shù)字 for (int i = 0; i < 9; i++) { if (matrix[row][i] == number || matrix[i][line] == number) { return false; } } //判斷小九宮格是否有重復(fù) int temprow = row / 3; int templine = line / 3; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (matrix[temprow * 3 + i][templine * 3 + j] == number) { return false; } } } return true; } /** * 打印矩陣 */ public void printarray() { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { system.out.print(matrix[i][j] + " "); } system.out.println(); } system.out.println(); }} |
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：https://blog.csdn.net/tianyaleixiaowu/article/details/50912924
