本文介绍了一种用Java实现的数独生成器。
算法：数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。
本文的实现采用的是回溯法。也就是说，从盘面的第一个格出发，按顺序遍历所有格子。对每一个格子随机生成一个数字，并判断该数字在当前的盘面下是否是合法的。如果不合法，比如同一行已经有相同的数字了，则随机换一个数字。如果当前位置所有数字都不合法，那么就回退到前一个位置，换一个数字，以此类推。
要点：- 在为每一个格子随机生成数字的时候，为了提高效率，要保证生成的数据是不重复的。这里使用的方法是，在初始化阶段就为每一个格子生成一个包含1~9的随机顺序的List。这样在遍历到某一个格子时，只需要按顺序把这个格子所对应的list里的值以此取出，就可以获取随机并且不重复的1~9的值。生成随机顺序列表可以利用Java的Collections.shuffle方法:
private static ListrandomValues() { 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
