36. Valid Sudoku
Valid Sudoku
Determine if a 9 x 9 The Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits
1-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without 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.
Example 1:
Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] Output: true
Example 2:
Input: board = [["8","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]] Output: false Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Constraints:
board.length == 9board[i].length == 9board[i][j]is a digit1-9or'.'.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
Approach) Hashtable and Set
Loop the
irow, column, block and find jthe position on the board corresponding to the first pointCode:
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
for (let i = 0; i < 9; ++i) {
let row = new Set(), col = new Set(), cub = new Set();
let rowIdx = 3*(parseInt(i/3)), colIdx = 3*(parseInt(i%3));
for (let j = 0; j < 9; ++j) {
if (board[i][j] != '.' && row.has(board[i][j])) return false;
row.add(board[i][j]);
if (board[j][i] != '.' && col.has(board[j][i])) return false;
col.add(board[j][i]);
if (board[rowIdx+parseInt(j/3)][colIdx+parseInt(j%3)] != '.' && cub.has(board[rowIdx+parseInt(j/3)][colIdx+parseInt(j%3)])) return false;
cub.add(board[rowIdx+parseInt(j/3)][colIdx+parseInt(j%3)]);
}
}
return true;
};Approach) Using array
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
for (let i = 0; i < 9; ++i) {
//vector<bool> row(9, false), col(9,false), cub(9,false);
let row = {1: false,
2: false,
3: false,
4: false,
5: false,
6: false,
7: false,
8: false,
9: false
}, col = {1: false,
2: false,
3: false,
4: false,
5: false,
6: false,
7: false,
8: false,
9: false
}, cub = {1: false,
2: false,
3: false,
4: false,
5: false,
6: false,
7: false,
8: false,
9: false
};
let rowIdx = 3*(parseInt(i/3)), colIdx = 3*(parseInt(i%3));
for (let j = 0; j < 9; ++j) {
if (board[i][j] != '.') {
if (row[board[i][j]-'1']) return false;
row[board[i][j]-'1'] = true;
}
if (board[j][i] != '.') {
if (col[board[j][i]-'1']) return false;
col[board[j][i]-'1'] = true;
}
if (board[rowIdx+parseInt(j/3)][colIdx+parseInt(j%3)] != '.') {
if (cub[board[rowIdx+parseInt(j/3)][colIdx+parseInt(j%3)]-'1']) return false;
cub[board[rowIdx+parseInt(j/3)][colIdx+parseInt(j%3)]-'1'] = true;
}
}
}
return true;
};Approach) Bit Manipulation
For each point loop on the board, find the row, column, and block number (0-8) where it is located. Use the bit of short to correspond to each digit.
Code:
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
let row = {1: 0,
2: 0,
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
8: 0,
9: 0
}, col = {1: 0,
2: 0,
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
8: 0,
9: 0
}, cub = {1: 0,
2: 0,
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
8: 0,
9: 0
};
for (let i = 0; i < 9; ++i) {
for (let j = 0; j < 9; ++j) {
if (board[i][j] != '.') {
let idx = 1 << (board[i][j] - '0');
if (row[i] & idx || col[j] & idx || cub[parseInt((i/3))*3+parseInt(j/3)] & idx) return false;
row[i] |= idx;
col[j] |= idx;
cub[parseInt((i/3))*3+parseInt(j/3)] |= idx;
}
}
}
return true;
};Approach) Brute Force
/**
* @param {character[][]} board
* @return {boolean}
*/
var isValidSudoku = function(board) {
let rows = [];
let columns = [];
let boxes = [];
for (let i = 0; i < 9; i++) {
rows.push([]);
columns.push([]);
boxes.push([]);
}
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board.length; j++) {
let cell = board[i][j];
if(cell !== ".") {
if (rows[i].includes(cell)) {
return false
} else rows[i].push(cell);
if (columns[j].includes(cell)) {
return false;
} else columns[j].push(cell);
let boxIndex = Math.floor((i / 3)) * 3 + Math.floor(j / 3);
if (boxes[boxIndex].includes(cell)) {
return false;
} else boxes[boxIndex].push(cell);
}
}
}
return true;
};Conclusion
That’s all folks! In this post, we solved LeetCode problem #36. Valid Sudoku
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment