[LeetCode] Problem 36 - Valid Sudoku

Posted on | In ,

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

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

Zv4Ey4.png

A partially filled sudoku which is valid.

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

Example

No.1

Input:

1
2
3
4
5
6
7
8
9
10
11
[
  ["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

No.2

Input:

1
2
3
4
5
6
7
8
9
10
11
[
  ["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

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8’s in the top left 3x3 sub-box, it is invalid.

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isValidSudoku(char[][] board) {
    boolean[][] row = new boolean[9][9];
    boolean[][] col = new boolean[9][9];
    boolean[][] cell = new boolean[9][9];

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.')
                continue;

            int num = board[i][j] - '1';

            if (row[i][num] || col[j][num] || cell[(i / 3) * 3 + (j / 3)][num])
                return false;

            row[i][num] = true;
            col[j][num] = true;
            cell[(i / 3) * 3 + (j / 3)][num] = true;
        }
    }

    return true;
}