LeetCode Valid Sudoku my Solution and Explanation
Here is my solution explanation and implementation of the LeetCode problem Valid Sudoku.
The problem
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.
Constraints:
- board.length == 9
- board[i].length == 9
- board[i][j] is a digit 1–9 or .
The solution
Use a hash map for each row and column with unique values and their count.
I can determine if a value exists if I remember how many times I have seen it or use a boolean.
How do I keep track of each nine 3x3 sub-boxes?
Each of the nine 3x3 sub-boxes must contain 1 to 9 inclusive digits.
If I am inside a box, I must check if the current value matches any existing ones.
Column and row are rules for the whole grid.
Checking if I am in the box requires row and column indices.
The first box contains row indices below or equal to 2 and column indices below or equal to 2.
Draw the matrix and extract rules for each box.
One way is to write rules for each row and column, but that is not viable.
A few of the rules are rules are:
- top-left rule: column <= 2 && row <= 2
- top-center rule: column >=3 && column <= 5 && row <= 2
- top-right rule: column >= 6 && row <= 2
- left-center rule: col <= 2 && row >= 3 && row <= 5
- center-center rule: col >= 3 && col <= 5 && row >= 3 && row <= 5
After reducing those conditions to common ones, I have:
- below: value <= 2
- between: value >= 3 && value <= 5
- above: value >= 6
That means I have a table like this:
- below(row) && below(column) yields top left
- below(row) && between(column) yields top center
- below(row) && above(column) yields top right
That allowed me to combine them.
After that, I could assign indices to each sub-box.
- top-left sub-box had an index of 0
- top-center sub-box had index 1
- top-right sub-box had index 2
The indices for each box ranged from 0 to 9 inclusive.
Each sub-box must have unique values ranging from 1 to 9 inclusive.
Each cell is a number from 1 to 9 inclusive.
Each cell should ignore the character that indicates the cell is empty.
For each cell, verify that each of the rules holds.
The loop’s role is to terminate and exit the function if the table is invalid. In other words, the loop should check for broken rules and terminate, indicating an invalid sudoku table. On the other hand, an unterminated loop means the sudoku table is valid.
Each row knows its values.
Each column knows its values.
Each sub-box knows its values.
We can break down the problem as follows:
- Ignore empty cell
- Check if the value has been seen and terminate if that holds true
- Otherwise, mark the value as already seen
Each cell belongs to each of the rules.