Java解“数独”之二

2017-01-12 09:53:55来源:oschina作者:TimeClean人点击

用到Shudu和Grid两个类,


运行 Shudu里的main方法,


读取的是本地文件



/**
* 创建时间:2017-1-11
* @author Dsz
*/
import java.io.FileReader;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
public class ShuDu2 {
public static void main(String[] args) throws Exception {
SimpleDateFormat dfs = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
Date begin = dfs.parse(dfs.format(new Date()));
String arg = "D://ENV//workspace//zisNumber//shudu.txt";
FileReader rd = new FileReader(arg);
while (true) {
Grid grid = Grid.create(rd);
if (grid == null) {
break;
}
List solutions = new ArrayList();
solve(grid, solutions);
printSolutions(grid, solutions);
}
Date end = dfs.parse(dfs.format(new Date()));
long between = end.getTime() - begin.getTime();
System.out.println("use Time:" + between + "ms");
}
private static void solve(Grid grid, List 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 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();
}
}/**
* 创建时间:2017-1-11
* @author Dsz
*/
import 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) {
// Compute row and column
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) {
// Compute row and column
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("0 ");
} else {
buf.append(num + " ");
}
}
buf.append("|/n");
}
buf.append("-------------------------");
return buf.toString();
}
}

输出结果:


Original
-------------------------
| 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 |
-------------------------
Solved
-------------------------
| 8 1 2 | 7 5 3 | 6 4 9 |
| 9 4 3 | 6 8 2 | 1 7 5 |
| 6 7 5 | 4 9 1 | 2 8 3 |
-------------------------
| 1 5 4 | 2 3 7 | 8 9 6 |
| 3 6 9 | 8 4 5 | 7 2 1 |
| 2 8 7 | 1 6 9 | 5 3 4 |
-------------------------
| 5 2 1 | 9 7 4 | 3 6 8 |
| 4 3 8 | 5 2 6 | 9 1 7 |
| 7 9 6 | 3 1 8 | 4 5 2 |
-------------------------use Time:561ms

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台