Solution For Interview Question: Sudoku2 | Asked By Apple & Uber
The Sudoku problem has been a part of many interview question and many companies including Apple & Uber. During the practice problem solving, here's how I solve Sudoku problem in Javascript.
Problem
Sudoku is a number-placement puzzle. The objective is to fill a 9 × 9
grid with numbers in such a way that each column, each row, and each of the nine 3 × 3
sub-grids that compose the grid all contain all of the numbers from 1
to 9
one time.
Implement an algorithm that will check whether the given grid
of numbers represents a valid Sudoku puzzle according to the layout rules described above. Note that the puzzle represented by grid
does not have to be solvable.
Example
For
grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '1', '.', '.', '.', '.', '.', '.'], ['.', '6', '7', '.', '.', '.', '.', '.', '9'], ['.', '.', '.', '.', '.', '.', '8', '1', '.'], ['.', '3', '.', '.', '.', '.', '.', '.', '6'], ['.', '.', '.', '.', '.', '7', '.', '.', '.'], ['.', '.', '.', '5', '.', '.', '.', '7', '.']]
the output should be
sudoku2(grid) = true
;
For
grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'], ['.', '.', '.', '.', '6', '.', '.', '.', '.'], ['7', '1', '.', '.', '7', '5', '.', '.', '.'], ['.', '7', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '8', '3', '.', '.', '.'], ['.', '.', '8', '.', '.', '7', '.', '6', '.'], ['.', '.', '.', '.', '.', '2', '.', '.', '.'], ['.', '1', '.', '2', '.', '.', '.', '.', '.'], ['.', '2', '.', '.', '3', '.', '.', '.', '.']]
the output should be
sudoku2(grid) = false
.
The given grid
is not correct because there are two 1
s in the second column. Each column, each row, and each 3 × 3
subgrid can only contain the numbers 1
through 9
one time.
Solution
- We can use 1 hash map or 3 different hash map to :
- Create a map to store unique numbers for each column
- Create a map to store unique numbers for each row
- Create a map to store unique numbers for each 3X3 sub grid
- We don't need to fill the dot values. we will only check that we have unique values in each column, row and sub grid
Complexity: O(N^2)
Comments
Leave a comment
You are not LoggedIn but you can comment as an anonymous user which requires manual approval. For better experience please Login.