Reference: LeetCode
Difficulty: Hard

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  • Each of the digits 1-9 must occur exactly once in each row.
  • Each of the digits 1-9 must occur exactly once in each column.
  • Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

Note:

  • The given board contain only digits 1-9 and the character '.'.
  • You may assume that the given Sudoku puzzle will have a single unique solution.
  • The given board size is always 9x9.

Analysis

Brute-Force

Each cell could be filled number from 1 to 9 and then check validity. There could be $9^81$ operations to do, where $81$ is the number of cells to fill.

Backtracking

From LeetCode solution section:

The basic idea is to do some pre-processing. We calculate many sets in advance to make operations in backtracking faster. In backtracking, we examine each empty position’s all possibilities, which could be calculated by set operations.

Note:

  • Set Operations (the modification):
    • Union: A.addAll(B)
    • Intersection: A.retainAll(B)
    • Difference: A.removeAll(B)
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
// You may assume that the given Sudoku puzzle will have a single unique solution.
Set<Integer>[] rowSetArr;
Set<Integer>[] colSetArr;
Set<Integer>[] boxSetArr;

public void solveSudoku(char[][] board) {
initSets(board); // init set
List<int[]> steps = getSteps(board); // get steps (get all position (i, j) where it is empty)
backtrack(0, steps, board);
}

private boolean backtrack(int d, List<int[]> steps, char[][] board) {
// Base case
if (d == steps.size()) {
return true; // when a result is found, return immediately
}
// Step (current empty position)
int[] currStep = steps.get(d);
int i = currStep[0], j = currStep[1]; // row and column
int boxNum = i / 3 * 3 + j / 3;
// Set
Set<Integer> option = getOptionSet(i, j, boxNum);
if (option.size() == 0) return false; // no more option to choose (should backtrack now)
// For each option (val)
for (int val : option) {
// pick
board[i][j] = (char) ('0' + val); // convert from int to char. Note: (char) is a must
rowSetArr[i].add(val);
colSetArr[j].add(val);
boxSetArr[boxNum].add(val);
if (backtrack(d + 1, steps, board)) return true;
// restore
board[i][j] = '.';
rowSetArr[i].remove(val);
colSetArr[j].remove(val);
boxSetArr[boxNum].remove(val);
}
return false;
}

private Set<Integer> getOptionSet(int i, int j, int boxNum) {
// whole set
Set<Integer> wholeSet = new HashSet<>();
for (int val = 1; val <= 9; ++val) wholeSet.add(val);
wholeSet.removeAll(rowSetArr[i]); // equivalent to doing addAll (union) + removeAll (difference)
wholeSet.removeAll(colSetArr[j]);
wholeSet.removeAll(boxSetArr[boxNum]);
return wholeSet;
}

private void initSets(char[][] board) {
// row/col/box sets
rowSetArr = new HashSet[9];
colSetArr = new HashSet[9];
boxSetArr = new HashSet[9];

for (int i = 0; i < 9; ++i) {
rowSetArr[i] = new HashSet<>();
colSetArr[i] = new HashSet<>();
boxSetArr[i] = new HashSet<>();
}

for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char ch = board[i][j];
if (ch == '.') continue;
rowSetArr[i].add(ch - '0');
colSetArr[j].add(ch - '0');
boxSetArr[i / 3 * 3 + j / 3].add(ch - '0');
}
}
}

private List<int[]> getSteps(char[][] board) {
List<int[]> steps = new ArrayList<>();
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char ch = board[i][j];
if (ch == '.') {
steps.add(new int[] { i, j }); // cannot specify length in this case
}
}
}
return steps;
}

Time: $O(1)$
Space: $O(1)$


Comment