本文实例为大家分享了java回溯算法解数独问题，供大家参考，具体内容如下
下图是一个数独题，也是号称世界上最难的数独。当然了，对于计算机程序来说，只要算法是对的，难不难就不知道了，反正计算机又不累。回溯算法基本上就是穷举，解这种数独类的问题逻辑比较简单。
不管算法懂不懂，先把类建出来，变量定义好，那放大学试卷上就是可以拿两分了。
|
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) {
// 号称世界上最难数独
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);
}
/**
* 数独算法
* @param i
* 行号
* @param j
* 列号
*/
private void backtrace(int i, int j) {
}
}
|
用一个二维数组来存储这个矩阵，然后定义一个方法来计算。方法里有两个属性——行号和列号。
我们的原理就是从第0行0列开始，依次往里面填入1-9之间的数字，然后判断填入的这个数字是否能放进去（该行该列和它所在的小九宫格是否有重复数字）。如果能放进去，那么就继续用1-9去试该行的下一列。一直到该行的最后一列，然后换行继续重复上面的步骤（也就是执行backtrace方法）。一直执行到最后一个空格，也就是i=8,j=8的时候，且最后这个空格所放的值也完全符合规则，那么此时就算完成，不用再继续调用backtrace方法了，输出正确解即可。
所以回溯法样子看起来是这样的。给第一个空格填1-9中任何一个，开始判断，如果ok，然后进入下一层，如果不ok，就断掉了。下一层还是从1-9开始试，然后ok，不ok……当最终目标达到时，空格已填满又满足条件，那么中断该分支，输出结果。
继续我们的程序。
由于有些位置已经有数字了，所以我们需要判断，如果该坑已经有人蹲了，那么就把列号j加1，进入下一列。如果到第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) {
// 号称世界上最难数独
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);
}
/**
* 数独算法
*
* @param i 行号
* @param j 列号
*/
private void backtrace(int i, int j) {
//如果i行j列是空格，那么才进入给空格填值的逻辑
if (matrix[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
//判断给i行j列放1-9中的任意一个数是否能满足规则
if (check(i, j, k)) {
//将该值赋给该空格，然后进入下一个空格
matrix[i][j] = k;
backtrace(i, j + 1);
}
}
} else {
//如果该位置已经有值了，就进入下一个空格进行计算
backtrace(i, j + 1);
}
}
/**
* 判断给某行某列赋值是否符合规则
*
* @param row 被赋值的行号
* @param line 被赋值的列号
* @param number 赋的值
* @return
*/
private boolean check(int row, int line, int number) {
//判断该行该列是否有重复数字
for (int i = 0; i < 9; i++) {
if (matrix[row][i] == number || matrix[i][line] == number) {
return false;
}
}
//判断小九宫格是否有重复
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;
}
}
|
此时已经写好了判断某行某列赋某个值是否ok的方法，通过该方法就能校验出数字是否能放到该位置。
还缺少的是边界值的判断，就是当已经到最后一列了，还没到最后一行时，需要对行号加1，然后恢复列号为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) {
// 号称世界上最难数独
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);
}
/**
* 数独算法
*
* @param i 行号
* @param j 列号
*/
private void backtrace(int i, int j) {
if (i == 8 && j == 9) {
//已经成功了，打印数组即可
system.out.println("获取正确解");
printarray();
return;
}
//已经到了列末尾了，还没到行尾，就换行
if (j == 9) {
i++;
j = 0;
}
//如果i行j列是空格，那么才进入给空格填值的逻辑
if (matrix[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
//判断给i行j列放1-9中的任意一个数是否能满足规则
if (check(i, j, k)) {
//将该值赋给该空格，然后进入下一个空格
matrix[i][j] = k;
backtrace(i, j + 1);
}
}
} else {
//如果该位置已经有值了，就进入下一个空格进行计算
backtrace(i, j + 1);
}
}
/**
* 判断给某行某列赋值是否符合规则
*
* @param row 被赋值的行号
* @param line 被赋值的列号
* @param number 赋的值
* @return
*/
private boolean check(int row, int line, int number) {
//判断该行该列是否有重复数字
for (int i = 0; i < 9; i++) {
if (matrix[row][i] == number || matrix[i][line] == number) {
return false;
}
}
//判断小九宫格是否有重复
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();
}
}
|
可以看到，判断成功的标志是行号为8，且列号为9时，认为找到了正确解。为什么是9呢，因为在check(i,j,k)那一步，通过了的话，将值k赋给最后一个空格，此时并没有中断程序，而且进入了下一层循环backtrace（i，j + 1），所以i为8j为9时才是终解。程序到这里，运行一下看看，发现并没有任何输出值，并没有找到正确解，why？
下面要讲的就是该程序最关键的地方，也是比较难以理解的地方，就是对根节点的初始化。回溯算法讲究的是一条道走到黑，不撞南墙不回头，并且把所有的道都走完。
我们把问题简单化，譬如一共只有两个空格，只能放0和1，正确答案是00和11.我们给第一个空格放了0，此时我们不知道是否放了0之后，后面是否能完全正确的走完全程。就像走迷宫一样，你选择了第一个岔道，此时有可能第一个岔道就是错的，后面无论怎么走都对了不了，也有可能有多条道可以走。那么我们的做法是先第一步放0，发现没问题（符合只能放0和1的规则），然后走第二步，第二步如果走对了，那就直接走出去了，获得了一次正确的解（00）。如果第二步是个死胡同（01），那就要回头了，就是要回到原点，把第一步初始化一下，然后第一步走1，然后再继续后面的步骤。所以无论怎么样，你都需要在第二步走完之后，把第一步走的值给清掉，回归到原点。这样才能找到所有的正确路线。
问题放大一下，有n步（n未知），第一步有1-9共9种情况，第一步放了1，后面还有未知的步，那无论后面成功与否，你肯定都要去试第一步放2-9之间的数字。
看第51行for循环那里，第一次将数字1赋给第一个空格。然后判断是否ok，如果ok了，就进入第二个空格去了，后面具体走多少步我们就不管了，我们只需要在后面的走完之后，初始化第一个空格就行了。那要是不ok呢，不ok当然就不用管他了，这一层走完就没下文了，等于该分支就断了。所以我们要在第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) {
// 号称世界上最难数独
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);
}
/**
* 数独算法
*
* @param i 行号
* @param j 列号
*/
private void backtrace(int i, int j) {
if (i == 8 && j == 9) {
//已经成功了，打印数组即可
system.out.println("获取正确解");
printarray();
return;
}
//已经到了列末尾了，还没到行尾，就换行
if (j == 9) {
i++;
j = 0;
}
//如果i行j列是空格，那么才进入给空格填值的逻辑
if (matrix[i][j] == 0) {
for (int k = 1; k <= 9; k++) {
//判断给i行j列放1-9中的任意一个数是否能满足规则
if (check(i, j, k)) {
//将该值赋给该空格，然后进入下一个空格
matrix[i][j] = k;
backtrace(i, j + 1);
//初始化该空格
matrix[i][j] = 0;
}
}
} else {
//如果该位置已经有值了，就进入下一个空格进行计算
backtrace(i, j + 1);
}
}
/**
* 判断给某行某列赋值是否符合规则
*
* @param row 被赋值的行号
* @param line 被赋值的列号
* @param number 赋的值
* @return
*/
private boolean check(int row, int line, int number) {
//判断该行该列是否有重复数字
for (int i = 0; i < 9; i++) {
if (matrix[row][i] == number || matrix[i][line] == number) {
return false;
}
}
//判断小九宫格是否有重复
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();
}
}
|
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持快网idc。
原文链接：https://blog.csdn.net/tianyaleixiaowu/article/details/50912924
相关文章
- 个人网站搭建：如何挑选具有弹性扩展能力的服务器？ 2025-06-10
- 个人服务器网站搭建：如何选择适合自己的建站程序或框架？ 2025-06-10
- 64M VPS建站：能否支持高流量网站运行？ 2025-06-10
- 64M VPS建站：怎样选择合适的域名和SSL证书？ 2025-06-10
- 64M VPS建站：怎样优化以提高网站加载速度？ 2025-06-10
