This question is part of NeetCode150 series.
Problem 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.
Solution
Checking the rows and columns is straight forward. For each row and each column, we can use a temp hashmap and check for duplicates.
For each 3x3 square, we need a way to determine which cell belongs to which big box. An easy way to do this is by dividing the row and column index by 3 (There are 3 big boxed in each row and column). This will be an integer division. Example: a[8,8] -> big[8/3,8/3] = big[2,2].
Detailed Explanation - YouTube - NeetCode
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public boolean isValidSudoku(char[][] board) {
return checkRows(board) && checkColumns(board) && checkBigSquares(board);
}
public boolean checkBigSquares(char[][] b){
Map<String, Set<Character>> map = new HashMap<>(); //Key: RowColumn as string
for(int i=0; i<b.length; i++){
for(int j=0; j<b.length; j++){
String rc = (i/3)+""+(j/3);
Character c = b[i][j];
if(c == '.') continue;
if(map.containsKey(rc)){
Set<Character> set = map.get(rc);
if(set.contains(c)) return false;
else set.add(c);
}else{
Set<Character> set = new HashSet<>();
set.add(c);
map.put(rc, set);
}
}
}
return true;
}
public boolean checkColumns(char[][] b){
Set<Character> set = new HashSet<>();
for(int i=0; i<b[0].length; i++){
set = new HashSet<>();
for(int j=0; j<b.length; j++){
Character c = b[j][i];
if(c == '.') continue;
if(set.contains(c)) return false;
else set.add(c);
}
}
return true;
}
public boolean checkRows(char[][] b){
Set<Character> set = new HashSet<>();
for(int i=0; i<b.length; i++){
set = new HashSet<>();
for(int j=0; j<b[0].length; j++){
Character c = b[i][j];
if(c == '.') continue;
if(set.contains(c)){
return false;
}else{
set.add(c);
}
}
}
return true;
}
}