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-9 without repetition.
- Each column must contain the digits
1-9 without repetition.
- Each of the nine
3 x 3 sub-boxes of the grid must contain the digits 1-9 without 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 digit 1-9 or '.'.
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 × 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.
PythonJavaC++GoTypeScriptRustJavaScriptC#PHP
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
/**
* @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;
};(code-box)
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;
}
}(code-box)
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;
}
}(code-box)
