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)$