Array
Hash Table
Matrix
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 == 9
board[i].length == 9
board[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 \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 $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$.
Python3 Java C++ Go TypeScript JavaScript PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 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 ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 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
}
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 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 ;
}
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 /**
* @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 ;
};
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
35
36
37
38
39 class Solution {
/**
* @param string[][] $board
* @return boolean
*/
function isValidSudoku($board) {
$rows = [];
$columns = [];
$boxes = [];
for ($i = 0; $i < 9; $i++) {
$rows[$i] = [];
$columns[$i] = [];
$boxes[$i] = [];
}
for ($row = 0; $row < 9; $row++) {
for ($column = 0; $column < 9; $column++) {
$cell = $board[$row][$column];
if ($cell != '.') {
if (
in_array($cell, $rows[$row]) ||
in_array($cell, $columns[$column]) ||
in_array($cell, $boxes[floor($row / 3) * 3 + floor($column / 3)])
) {
return false;
}
$rows[$row][] = $cell;
$columns[$column][] = $cell;
$boxes[floor($row / 3) * 3 + floor($column / 3)][] = $cell;
}
}
}
return true;
}
}
GitHub