其实也就是用到了回溯算法。
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
首先定义一个Sudoku类，用来保存和处理9*9的数组
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
| import java.util.ArrayList;
import java.util.List;
public class Sudoku {
private int[][] src;
private List<IRule> ruleList = new ArrayList<>();
private List<Result> resultList = new ArrayList<>();
private boolean findOne = true;
private boolean check(int x,int y){
if(ruleList.size()>0){
for (IRule iRule : ruleList) {
boolean flag=iRule.check(src,x,y);
if(flag==false){
return false;
}
}
}
return true;
}
public Result backTrace(int x,int y){
if(x==8 && y==9){
Result result = new Result(src,x,y);
resultList.add(result);
return result;
}
if(y==9){
x++;
y=0;
}
if(src[x][y]==0){
for (int i = 1; i <=9 ; i++) {
src[x][y] = i;
if(check(x,y)){
Result result = backTrace(x,y+1);
if(result.isSuccess() && findOne){
return result;
}
}
src[x][y]=0;
}
return new Result(x,y);
}else{
Result result = backTrace(x,y+1);
return result;
}
}
public List<Result> getResultList() {
return resultList;
}
public void addRule(IRule rule){
ruleList.add(rule);
}
public void clearRule(){
ruleList.clear();
}
public Sudoku(String[] str){
int[][] x=new int[9][9];
for (int i = 0; i <9 ; i++) {
for (int j = 0; j <9 ; j++) {
x[i][j]=Integer.parseInt(str[i].charAt(j)+"");
}
}
src=x;
}
public Sudoku(int[][] x){
src=x;
}
public void display(){
for (int i = 0; i <src.length ; i++) {
for (int j = 0; j <src[i].length ; j++) {
System.out.print(src[i][j]);
}
System.out.println();
}
}
public boolean isFindOne() {
return findOne;
}
public void setFindOne(boolean findOne) {
this.findOne = findOne;
}
}
|
可以看到主要的解题算法在backTrace函数中，通过不断尝试，正确的则继续调用自身，错误的则返回上层尝试其他数值。
check方法用来判断当前数组是否符合规范，这里为了扩展一些其他特殊数独规则，使用了接口，把判断依据放入了ruleList里面。
接着看一下规则接口
1
2
3
| public interface IRule {
public boolean check(final int[][] src,int x,int y);
}
|
只是简单的定义入参，和判断返回boolean值
接着是基础的规则，横竖判断不能重复
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
| import java.util.ArrayList;
import java.util.List;
public class BaseSudokuRule implements IRule {
private final boolean isX;
public BaseSudokuRule(boolean isX) {
this.isX = isX;
}
@Override
public boolean check(int[][] src, int x, int y) {
if(isX){
List<Integer> list = new ArrayList<>(9);
for (int i = 0; i <9 ; i++) {
if(src[i][y]!=0){
Integer one = new Integer(src[i][y]);
if(list.contains(one)){
return false;
}
list.add(one);
}
}
}else{
List<Integer> list = new ArrayList<>(9);
for (int i = 0; i <9 ; i++) {
if(src[x][i]!=0){
Integer one = new Integer(src[x][i]);
if(list.contains(one)){
return false;
}
list.add(one);
}
}
}
return true;
}
}
|
还有3*3不能重复规则
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
| import java.util.ArrayList;
import java.util.List;
public class SubSudokuRule implements IRule{
@Override
public boolean check(int[][] src, int x, int y) {
int startX=x/3;
int startY=y/3;
List<Integer> list = new ArrayList<>(9);
for (int i = startX*3; i <startX*3+3 ; i++) {
for (int j = startY*3; j <startY*3+3 ; j++) {
if(src[i][j]!=0){
Integer one = new Integer(src[i][j]);
if(list.contains(one)){
return false;
}
list.add(one);
}
}
}
return true;
}
}
|
以及保存正确结果的返回对象
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
|
public class Result {
private int x;
private int y;
private int[][] src;
private boolean success=true;
public boolean hasNext(){
if(x==8 && y>=9){
return false;
}
return true;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
public int[][] getSrc() {
return src;
}
public boolean isSuccess() {
return success;
}
public void display(){
if(src!=null){
for (int i = 0; i <src.length ; i++) {
for (int j = 0; j <src[i].length ; j++) {
System.out.print(src[i][j]);
}
System.out.println();
}
}
}
public Result(int x,int y){
this(null,x,y);
}
public Result(int[][] data,int x,int y){
this.x=x;
this.y=y;
if(data==null){
success=false;
}else{
src=new int[9][9];
for (int i = 0; i <9 ; i++) {
for (int j = 0; j <9 ; j++) {
src[i][j]=data[i][j];
}
}
}
}
}
|
可以额外增加规则，例如与之上下左右相邻的总和等于多少的规则
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
| import java.util.ArrayList;
import java.util.List;
public class SumRule implements IRule{
private final int destX;
private final int destY;
private final int sum;
public SumRule(int destX, int destY, int sum) {
this.destX = destX;
this.destY = destY;
this.sum = sum;
}
@Override
public boolean check(int[][] src, int x, int y) {
boolean needCheck=false;
if(destX == x && destY==y){
needCheck=true;
}else if(destX==x){
if(destY==y-1 || destY==y+1){
needCheck=true;
}
}else if(destY==y){
if(destX==x-1 || destX==x+1){
needCheck=true;
}
}
if(needCheck==false){
return true;
}
List<Integer> list = new ArrayList<>();
list.add(src[destX-1][destY]);
list.add(src[destX+1][destY]);
list.add(src[destX][destY]);
list.add(src[destX][destY+1]);
list.add(src[destX][destY-1]);
int sum=0;
for (Integer integer : list) {
if(integer==0){
return true;
}
sum=sum+integer;
}
return this.sum==sum;
}
}
|
最后是main函数调用
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
| import java.util.List;
public class Demo {
public static void main(String[] args) {
String x[]={
"001000500",
"020000010",
"500000009",
"000000000",
"000000000",
"000000000",
"900000004",
"010000060",
"004000100"
};
Sudoku sudoku = new Sudoku(x);
sudoku.setFindOne(false);
BaseSudokuRule xRule = new BaseSudokuRule(true);
BaseSudokuRule yRule = new BaseSudokuRule(false);
sudoku.addRule(xRule);
sudoku.addRule(yRule);
SubSudokuRule subSudokuRule = new SubSudokuRule();
sudoku.addRule(subSudokuRule);
sudoku.addRule(new SumRule(1,4,17));
sudoku.addRule(new SumRule(2,2,29));
sudoku.addRule(new SumRule(2,6,22));
sudoku.addRule(new SumRule(4,1,34));
sudoku.addRule(new SumRule(4,4,23));
sudoku.addRule(new SumRule(4,7,20));
sudoku.addRule(new SumRule(6,2,22));
sudoku.addRule(new SumRule(6,6,29));
sudoku.addRule(new SumRule(7,4,33));
sudoku.backTrace(0,0);
List<Result> list = sudoku.getResultList();
for (Result result : list) {
if(result.isSuccess()){
System.out.println("============");
result.display();
System.out.println("============");
}
}
}
}
|
