本文介绍了一种用Java实现的数独生成器。
算法:数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。
本文的实现采用的是回溯法。也就是说,从盘面的第一个格出发,按顺序遍历所有格子。对每一个格子随机生成一个数字,并判断该数字在当前的盘面下是否是合法的。如果不合法,比如同一行已经有相同的数字了,则随机换一个数字。如果当前位置所有数字都不合法,那么就回退到前一个位置,换一个数字,以此类推。
要点:- 在为每一个格子随机生成数字的时候,为了提高效率,要保证生成的数据是不重复的。这里使用的方法是,在初始化阶段就为每一个格子生成一个包含1~9的随机顺序的List。这样在遍历到某一个格子时,只需要按顺序把这个格子所对应的list里的值以此取出,就可以获取随机并且不重复的1~9的值。生成随机顺序列表可以利用Java的Collections.shuffle方法:
private static List randomValues() {
List result = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
Collections.shuffle(result);
return result;
}
- 为了判断指定位置的某一个值是否合法,我们需要判断三个条件:
- 该点所在行是否有相同值
- 该点所在列是否有相同值
- 该点所在九宫是否有相同值
- 遍历和回退采用的是递归的方法,这样使得逻辑更加清晰。
下面是完整代码:
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.*;
public class Sudoku {
private static final Logger LOG = LoggerFactory.getLogger( Sudoku.class );
private static List[][] grid = new List[9][];
private static int[][] gridIndex = new int[9][];
private static HashSet[] rowSets = new HashSet[9];
private static HashSet[] colSets = new HashSet[9];;
private static HashSet[] blockSets = new HashSet[9];;
private static List randomValues() {
List result = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);
Collections.shuffle(result);
return result;
}
private static int blockIndex(int row, int col) {
return (row / 3) * 3 + (col / 3);
}
private static boolean check(int row, int col) {
if (row == 9 || col == 9) {
return true;
}
while (gridIndex[row][col] < 9) {
Integer value = grid[row][col].get(gridIndex[row][col]);
if (rowSets[row].contains(value) ||
colSets[col].contains(value) ||
blockSets[blockIndex(row, col)].contains(value)) {
gridIndex[row][col]++;
continue;
}
// the current value looks good, set maps
rowSets[row].add(value);
colSets[col].add(value);
blockSets[blockIndex(row, col)].add(value);
// check next point
int nextCol = (col + 1) % 9;
int nextRow = row + (col + 1) / 9;
if (check(nextRow, nextCol) == false) {
// rollback
rowSets[row].remove(value);
colSets[col].remove(value);
blockSets[blockIndex(row, col)].remove(value);
gridIndex[row][col]++;
continue;
}
return true;
}
gridIndex[row][col] = 0;
return false;
}
private static void printResult() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.printf("%d ", grid[i][j].get(gridIndex[i][j]));
}
System.out.println("");
}
}
public static void main(String[] args) {
// init random value lists
for (int i = 0; i < grid.length; i++) {
grid[i] = new List[9];
gridIndex[i] = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0};
for (int j = 0; j < grid[i].length; j++) {
grid[i][j] = randomValues();
}
}
// init hashsets for rows, cols and blocks
for (int i = 0; i < 9; i++) {
rowSets[i] = new HashSet<>();
colSets[i] = new HashSet<>();
blockSets[i] = new HashSet<>();
}
check(0, 0);
printResult();
}
}
运行结果:
9 6 5 8 3 7 4 1 2
1 7 8 6 2 4 5 9 3
4 2 3 1 5 9 6 7 8
8 3 1 2 9 5 7 6 4
2 9 6 7 4 1 8 3 5
5 4 7 3 8 6 1 2 9
6 8 4 9 7 3 2 5 1
3 1 2 5 6 8 9 4 7
7 5 9 4 1 2 3 8 6
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)