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];

Comment