LeetCode 37 - Sudoku Solver

作者 QIFAN 日期 2017-02-16
LeetCode 37 - Sudoku Solver

原题链接: 37. Sudoku Solver


题干

给一个没填满的数独矩阵,返回唯一解。
空位置用 . 表示。

思路

想到了这道题 LeetCode 63 - Valid Sudoku ,准备用类似的解法 + DFS 。

  1. 需要三个长度为 9 的 HashSet 矩阵,分别存储行、列、3x3 的数字。
  2. 每一次数字的选择就是该位置所在三个 HashSet 的交集
    • 如果交集为空,则不能继续,返回 false 。
    • 如果有交集,将交集中的数字依次测试进行下一步,若有满足的解法,返回 true 。
    • 如果全部试完都没有满足的,则说明无解(题目说明了一定会有一个解,所以这个情况就不用考虑了)。
  3. 如果遍历到最后一个,且三个矩阵都空了,说明有解,返回当前矩阵。(base case)
// 求交集
List<Character> intersect = intersect(row, col);
if (intersect.size() == 0) {
return false;
}

代码:

List<HashSet<Character>> rows = new ArrayList<>();
List<HashSet<Character>> cols = new ArrayList<>();
List<HashSet<Character>> grids = new ArrayList<>();
//boolean solved = false;
public void solveSudoku(char[][] board) {
// 初始化
for (int i = 0; i < 9; i++) {
rows.add(new HashSet<>());
cols.add(new HashSet<>());
grids.add(new HashSet<>());
for (int j = 0; j < 9; j++) {
char num = (char)('1' + j);
add(i, num);
}
}
// 移除已存在的数字
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
char c = board[row][col];
if (c != '.') {
remove(row, col, c);
}
}
}
solve(board, 0, 0);
}
private boolean solve(char[][] board, int row, int col) {
// base case;
if (row == 9) {
return true;
}
int nextRow = (col + 1) / 9 + row;
int nextCol = (col + 1) % 9;
if (board[row][col] == '.') {
// 求交集
List<Character> intersect = intersect(row, col);
for (Character num: intersect) {
board[row][col] = num;
remove(row, col, num);
if (solve(board, nextRow, nextCol)) {
return true;
}
add(row, col, num);
}
board[row][col] = '.';
return false;
} else {
return solve(board, nextRow, nextCol);
}
}
private List<Character> intersect(int row, int col) {
List<Character> res = new ArrayList<>();
int gridIndex = row / 3 * 3 + col / 3;
Iterator<Character> iterator = rows.get(row).iterator();
while (iterator.hasNext()) {
Character num = iterator.next();
if (cols.get(col).contains(num) && grids.get(gridIndex).contains(num)) {
res.add(num);
}
}
return res;
}
private void add(int i, char num) {
rows.get(i).add(num);
cols.get(i).add(num);
grids.get(i).add(num);
}
private void add(int row, int col, char num) {
rows.get(row).add(num);
cols.get(col).add(num);
grids.get(row / 3 * 3 + col / 3).add(num);
}
private void remove(int row, int col, char num) {
rows.get(row).remove(num);
cols.get(col).remove(num);
grids.get(row / 3 * 3 + col / 3).remove(num);
}