Valid Sudoku
Check a partially filled 9 by 9 Sudoku board. Filled digits must not repeat within a row, column, or 3 by 3 box. You do not need to solve it.
Work through the cases
3 examplesInput notation
Nine lines of nine characters, each a digit 1-9 or a dot for an empty cell.Expected result
true or false.Case 1
Input
1........ .2....... ..3...... ...4..... ....5.... .....6... ......7.. .......8. ........9
Expected output
true
Case 2
Input
11....... ......... ......... ......... ......... ......... ......... ......... .........
Expected output
false
Case 3
Input
......... ......... ......... ......... ......... ......... ......... ......... .........
Expected output
true
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is, for each filled digit, to rescan its row, column, and box. The board is only 9 × 9, so that would pass. The bottleneck is rescanning the same row, column, and box. We only need to remember whether digit v has already appeared in that unit. One pass is enough: three boolean tables row[i][v], col[j][v], and sub[k][v], with box index k = \lfloor i/3 \rfloor × 3 + \lfloor j/3 \rfloor. A second hit of the same digit returns false immediately.
The valid sudoku satisfies the following three conditions:
- The digits are not repeated in each row; - The digits are not repeated in each column; - The digits are not repeated in each 3 × 3 box.
Traverse the sudoku, for each digit, check whether the row, column and 3 × 3 box it is in have appeared the digit. If it is, return false. If the traversal is over, return true.
The time complexity is O(C) and the space complexity is O(C), where C is the number of empty spaces in the sudoku. In this question, C=81.
class Solution {
public boolean isValidSudoku(char[][] board) {
boolean[][] row = new boolean[9][9];
boolean[][] col = new boolean[9][9];
boolean[][] sub = new boolean[9][9];
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
char c = board[i][j];
if (c == '.') {
continue;
}
int num = c - '0' - 1;
int k = i / 3 * 3 + j / 3;
if (row[i][num] || col[j][num] || sub[k][num]) {
return false;
}
row[i][num] = true;
col[j][num] = true;
sub[k][num] = true;
}
}
return true;
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.