Leetcode — Valid Sudoku #36

Photo by Richard Bell on Unsplash

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. 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.

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 and 9 column and 9 sub-boxes , so we only need to know if we already have a specific number in the N 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 .