Reference: LeetCode
Difficulty: Medium

Problem

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  • Each row must contain the digits 1-9 without repetition.
  • Each column must contain the digits 1-9 without repetition.
  • Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

From LeetCode

Example: 

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
Input: [
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Input: [
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

Analysis

Hash Set

Check three cases respectively.

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
public boolean isValidSudoku(char[][] board) {
  // assume board is valid
  int row = board.length;
  int col = board[0].length;
  // check each row
  for (int r = 0; r < row; ++r) {
    if (isValid(board, r, 0, r, col - 1) == false) return false;
  }
  // check each col
  for (int c = 0; c < col; ++c) {
    if (isValid(board, 0, c, row - 1, c) == false) return false;
  }
  // check each cell
  for (int i = 0; i < 9; ++i) {
    int r1 = (i / 3) * 3, r2 = r1 + 2; // index conversion
    int c1 = (i % 3) * 3, c2 = c1 + 2;
    if (isValid(board, r1, c1, r2, c2) == false) return false;
  }
  
  return true;
}

private boolean isValid(char[][] board, int r1, int c1, int r2, int c2) {
  Set<Character> set = new HashSet<>();
  for (int r = r1; r <= r2; ++r) {
    for (int c = c1; c <= c2; ++c) {
      char ch = board[r][c];
      if (ch == '.') continue;
      if (set.contains(ch)) return false;
      set.add(ch);
    }
  }
  return true;
}

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

Or, we can use 27 hash set to achieve one-pass solution.

1
2
3
Set<Integer> [] rows = new HashSet[9];
Set<Integer> [] columns = new HashSet[9];
Set<Integer> [] boxes = new HashSet[9];