Leetcode — Valid Sudoku #36
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 digits1-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.

What we need to do?
basically we need to check if a Sudoku board is a valid board following the rules above.
First intuition is that we must go throw all the rows/cols/sub-boxes and check for duplication.
remember: almost always, duplication = Set()
Brute Force Solution
The naive solution would be, for each board[row][column]
check for duplication on each row
and each column
. While that would solve the row/column
search, how can we check for the sub-box
duplication?
Let’s start write the naive code solution.
In the above gist, we iterate over the board
and for each cell
we check wether NOT isRowValid
, isColumnValid
when in each function we check the current cell
on the current row/column
. We create a new Set
on each function call and add the current cell
value to the set so on the next iteration we can check if we already have the same number on the row / column
. If we found a duplication, we return false
.
isSubBoxValid
to check the sub-box
, we need to know what is the sub-box
we need to check for each row and column
.
Let’s say we are on the 3rd row and the 4th column
, if we look at the board image above, the number/cell
we are looking at is 6
. This cell is on the middle sub-box. To know if the number 6 has a repetition in this sub-box we need to start with the board[3,3]
cell and go 3
steps to the right and 3
down (because it is a 3X3
box).
So if we do board[row-row%3, column — column%3]
we would get the starting cell for our iteration.
board[row-row%3, column — column%3] =
board[3–3%3, 4–4%3] =
board[3,3]
The above code would work BUT it is very inefficient. Why?
Let’s say we start with board[0,0]
and search on the 0
row and the 0
column. Next, we will look at board[0,1]
, now we search again on the 0
row, but we already looked at that row, do we really need to search on it again?
What if we would create a Set
for each row, and then for each row[ith]
we will create another Set
? and then while we are iterating the board
we will check/add the current number on that Set
.
If we look at the board, we have
9 rows
and9 column
and9 sub-boxes
, so we only need to know if we already have a specific number in theN row
/N column
/N box
.
Let’s start with create a new Set
for each row/column/box
let row = new Set();
let column = new Set();
let box = new Set();
Then, for each row/column/box we will create a new Set
for each ith
(since we have only 9 rows/columns/boxes, we can have a simple loop)
for(let i = 0; i < 9; i++){
row[i] = new Set();
column[i] = new Set();
box[i] = new Set();
}
If we want to visualize it, we have something like that

Writing the code for the row/column
should be pretty straight forward, we simply iterate the board
, and for each r
(stands for row) and c
(stands for column) we check if we already have the cell number on that Set.
What about the box?
The tricky part would be to understand how can we find the correct sub-box for the given cell.
As we said, we can see that we have 9 sub-boxes and we can divide them like so

We can also see that rows 0, 1, 2
belong to the same sub-box and also rows 3, 4, 5
and rows 6, 7, 8
.
So how can we find the right sub-box?
Let’s say we are on the 0 row and 0 column, we know it should be on the 0 sub-box. We can use calculation (0 / 3) * 3 + 0 / 3
that would give us 0
. Same, if we are on the 3rd row and the 4th column
we can calculate it like
(3 / 3) * 3 + 4 / 3
that would give us 4
.