36. Valid Sudoku
December 15, 2025 · View on GitHub
Description
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.
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.
Example 1:
Input: board = [["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
Example 2:
Input: board = [["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.
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit1-9or'.'.
Solutions
Solution 1: Traversal once
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 \times 3$ box.
Traverse the sudoku, for each digit, check whether the row, column and $3 \times 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 and the space complexity is , where is the number of empty spaces in the sudoku. In this question, .
Python3
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
row = [[False] * 9 for _ in range(9)]
col = [[False] * 9 for _ in range(9)]
sub = [[False] * 9 for _ in range(9)]
for i in range(9):
for j in range(9):
c = board[i][j]
if c == '.':
continue
num = int(c) - 1
k = i // 3 * 3 + j // 3
if row[i][num] or col[j][num] or sub[k][num]:
return False
row[i][num] = True
col[j][num] = True
sub[k][num] = True
return True
Java
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;
}
}
C++
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<vector<bool>> row(9, vector<bool>(9, false));
vector<vector<bool>> col(9, vector<bool>(9, false));
vector<vector<bool>> sub(9, vector<bool>(9, false));
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;
}
};
Go
func isValidSudoku(board [][]byte) bool {
row, col, sub := [9][9]bool{}, [9][9]bool{}, [9][9]bool{}
for i := 0; i < 9; i++ {
for j := 0; j < 9; j++ {
num := board[i][j] - byte('1')
if num < 0 || num > 9 {
continue
}
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
}
TypeScript
function isValidSudoku(board: string[][]): boolean {
const row: boolean[][] = Array.from({ length: 9 }, () =>
Array.from({ length: 9 }, () => false),
);
const col: boolean[][] = Array.from({ length: 9 }, () =>
Array.from({ length: 9 }, () => false),
);
const sub: boolean[][] = Array.from({ length: 9 }, () =>
Array.from({ length: 9 }, () => false),
);
for (let i = 0; i < 9; ++i) {
for (let j = 0; j < 9; ++j) {
const num = board[i][j].charCodeAt(0) - '1'.charCodeAt(0);
if (num < 0 || num > 8) {
continue;
}
const k = Math.floor(i / 3) * 3 + Math.floor(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;
}
Rust
impl Solution {
pub fn is_valid_sudoku(board: Vec<Vec<char>>) -> bool {
let mut row = vec![vec![false; 9]; 9];
let mut col = vec![vec![false; 9]; 9];
let mut sub = vec![vec![false; 9]; 9];
for i in 0..9 {
for j in 0..9 {
let c = board[i][j];
if c == '.' {
continue;
}
let num = (c as u8 - b'0' - 1) as usize;
let 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;
}
}
true
}
}
JavaScript
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function (board) {
const row = [...Array(9)].map(() => Array(9).fill(false));
const col = [...Array(9)].map(() => Array(9).fill(false));
const sub = [...Array(9)].map(() => Array(9).fill(false));
for (let i = 0; i < 9; ++i) {
for (let j = 0; j < 9; ++j) {
const num = board[i][j].charCodeAt() - '1'.charCodeAt();
if (num < 0 || num > 8) {
continue;
}
const k = Math.floor(i / 3) * 3 + Math.floor(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;
};
C#
public class Solution {
public bool IsValidSudoku(char[][] board) {
bool[,] row = new bool[9, 9];
bool[,] col = new bool[9, 9];
bool[,] sub = new bool[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;
}
}
PHP
class Solution {
/**
* @param String[][] $board
* @return Boolean
*/
function isValidSudoku($board) {
$row = array_fill(0, 9, array_fill(0, 9, false));
$col = array_fill(0, 9, array_fill(0, 9, false));
$sub = array_fill(0, 9, array_fill(0, 9, false));
for ($i = 0; $i < 9; $i++) {
for ($j = 0; $j < 9; $j++) {
$c = $board[$i][$j];
if ($c === '.') {
continue;
}
$num = intval($c) - 1;
$k = intdiv($i, 3) * 3 + intdiv($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;
}
}