java数度破解
java数度破解
在国外网站上扒了一段不错的数度自动破解代码。是用java写的所以对着写了下，还有个用js写的因为平时不怎么用js也就没深究了
话不多说上源码
数度用一个txt存着，格式如下
1 | |
- 首先是个SudokuSolver类
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
50import java.io.*;
import java.util.*;
public class SudokuSolver {
public static void main(String[] args) throws Exception {
String arg = "存放数度的文件路径";
FileReader rd = new FileReader(arg);
while (true) {
Grid grid = Grid.create(rd);
if (grid == null) {
break;
}
List<Grid> solutions = new ArrayList<Grid>();
solve(grid, solutions);
printSolutions(grid, solutions);
}
}
private static void solve(Grid grid, List<Grid> solutions) {
if (solutions.size() >= 2) {
return;
}
int loc = grid.findEmptyCell();
if (loc < 0) {
solutions.add(grid.clone());
return;
}
for (int n=1; n<10; n++) {
if (grid.set(loc, n)) {
solve(grid, solutions);
grid.clear(loc);
}
}
}
private static void printSolutions(Grid grid, List<Grid> solutions) {
System.out.println("Original");
System.out.println(grid);
if (solutions.size() == 0) {
System.out.println("Unsolveable");
} else if (solutions.size() == 1) {
System.out.println("Solved");
} else {
System.out.println("At least two solutions");
}
for (int i=0; i<solutions.size(); i++) {
System.out.println(solutions.get(i));
}
System.out.println();
System.out.println();
}
} - 然后是一个Grid类
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
92import java.io.Reader;
public class Grid implements Cloneable {
int[] cells = new int[81];
int[] colsSet = new int[9];
int[] rowsSet = new int[9];
int[] subgridSet = new int[9];
public static Grid create(Reader rd) throws Exception {
Grid grid = new Grid();
for (int loc=0; loc<grid.cells.length; ) {
int ch = rd.read();
if (ch < 0) {
return null;
}
if (ch == '#') {
while (ch >= 0 && ch != '\n' && ch != '\r') {
ch = rd.read();
}
} else if (ch >= '1' && ch <= '9') {
grid.set(loc, ch-'0');
loc++;
} else if (ch == '.' || ch == '0') {
loc++;
}
}
return grid;
}
public int findEmptyCell() {
for (int i=0; i<cells.length; i++) {
if (cells[i] == 0) {
return i;
}
}
return -1;
}
public boolean set(int loc, int num) {
int r = loc/9;
int c = loc%9;
int blockLoc = (r/3)*3+c/3;
boolean canSet = cells[loc] == 0
&& (colsSet[c] & (1<<num)) == 0
&& (rowsSet[r] & (1<<num)) == 0
&& (subgridSet[blockLoc] & (1<<num)) == 0;
if (!canSet) {
return false;
}
cells[loc] = num;
colsSet[c] |= (1<<num);
rowsSet[r] |= (1<<num);
subgridSet[blockLoc] |= (1<<num);
return true;
}
public void clear(int loc) {
int r = loc/9;
int c = loc%9;
int blockLoc = (r/3)*3+c/3;
int num = cells[loc];
cells[loc] = 0;
colsSet[c] ^= (1<<num);
rowsSet[r] ^= (1<<num);
subgridSet[blockLoc] ^= (1<<num);
}
public Grid clone() {
Grid grid = new Grid();
grid.cells = cells.clone();
grid.colsSet = colsSet.clone();
grid.rowsSet = rowsSet.clone();
grid.subgridSet = subgridSet.clone();
return grid;
}
public String toString() {
StringBuffer buf = new StringBuffer();
for (int r=0; r<9; r++) {
if (r%3 == 0) {
buf.append("-------------------------\n");
}
for (int c=0; c<9; c++) {
if (c%3 == 0) {
buf.append("| ");
}
int num = cells[r*9+c];
if (num == 0) {
buf.append(". ");
} else {
buf.append(num+" ");
}
}
buf.append("|\n");
}
buf.append("-------------------------");
return buf.toString();
}
}
本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！