Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/36.html
36. Valid Sudoku
Level
Medium
Description
Determine if a 9x9 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 9
3x3sub-boxes of the grid must contain the digits1-9without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Example 1:
Input:
[
["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:
[
["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.
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.
- The given board contain only digits
1-9and the character'.'. - The given board size is always
9x9.
Algorithm
The criterion is to see whether there are repeated numbers in each row and column, and whether there are repeated numbers in each small 3x3 square matrix. If there are no repeats, the current matrix is a Sudoku matrix, but it does not mean that the Sudoku matrix to be solved has a solution, it simply judges whether the currently unfilled matrix is a Sudoku matrix.
Then according to the definition of the Sudoku matrix, when traversing each number, look at the row and column containing the current position and whether the number has appeared in the 3x3 small square matrix.
Here we need three boolean matrices with the same size as the original array Same, record each row, each column, each small square matrix whether there is a certain number, the row and column mark subscripts correspond well, that is, the subscripts of the small square matrix need to be slightly changed
subsquare indexing i - i%3 + j/3 or j - j%3 + i/3
Code
-
public class Valid_Sudoku { /* * @note: 三个连续if-else可以优化到一个if-else * * 记住subsquare编号 i - i%3 + j/3 * 或者 j - j%3 + i/3 */ public class Solution_optimized { // my thought is to use hashmap counting // or maybe bitmap is better, less memory required public boolean isValidSudoku(char[][] board) { final int SIZE = 9; if(board == null || board.length != SIZE || board[0].length != SIZE) return false; boolean[][] row = new boolean[SIZE][SIZE]; // i-th row, number j boolean[][] col = new boolean[SIZE][SIZE]; boolean[][] matrix = new boolean[SIZE][SIZE]; for(int i = 0; i < SIZE; i++){ for(int j = 0; j < SIZE; j++){ if(board[i][j] == '.') continue; // that number-1, is its index in every checking array int n = board[i][j] - '1'; // check three array, if already set true // sub-matrix index: i%3 + j%3 if(row[i][n] || col[j][n] || matrix[i - i % 3 + j / 3][n]){ return false; } // if not set, now set this number exists row[i][n] = true; col[j][n] = true; matrix[i - i % 3 + j / 3][n] = true; } } return true; } } } ############ class Solution { public boolean isValidSudoku(char[][] board) { boolean[][] row = new boolean[9][9]; boolean[][] col = new boolean[9][9]; boolean[][] sub = new boolean[9][9]; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { char c = board[i][j]; if (c == '.') { continue; } int num = c - '0' - 1; int k = i / 3 * 3 + j / 3; if (row[i][num] || col[j][num] || sub[k][num]) { return false; } row[i][num] = true; col[j][num] = true; sub[k][num] = true; } } return true; } } -
// OJ: https://leetcode.com/problems/valid-sudoku/ // Time: O(1) // Space: O(1) class Solution { public: bool isValidSudoku(vector<vector<char>>& A) { int row[9][9] = {}, col[9][9] = {}, box[9][9] = {}; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (A[i][j] == '.') continue; int n = A[i][j] - '1'; if (row[i][n] || col[j][n] || box[i / 3 * 3 + j / 3][n]) return false; row[i][n] = col[j][n] = box[i / 3 * 3 + j / 3][n] = 1; } } return true; } }; -
class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: row = [[False] * 9 for _ in range(9)] col = [[False] * 9 for _ in range(9)] sub = [[False] * 9 for _ in range(9)] for i in range(9): for j in range(9): c = board[i][j] if c == '.': continue num = int(c) - 1 k = i // 3 * 3 + j // 3 if row[i][num] or col[j][num] or sub[k][num]: return False row[i][num] = True col[j][num] = True sub[k][num] = True return True ############ class Solution(object): def isValidSudoku(self, board): """ :type board: List[List[str]] :rtype: bool """ cacheCol = [[0] * 9 for _ in range(0, 10)] cacheRow = [[0] * 9 for _ in range(0, 10)] cacheBox = [[0] * 9 for _ in range(0, 10)] for i in range(0, 9): for j in range(0, 9): ib = (i / 3) * 3 + j / 3 if board[i][j] == ".": continue num = int(board[i][j]) - 1 if cacheRow[i][num] != 0 or cacheCol[j][num] != 0 or cacheBox[ib][num] != 0: return False cacheRow[i][num] = 1 cacheCol[j][num] = 1 cacheBox[ib][num] = 1 return True -
func isValidSudoku(board [][]byte) bool { row, col, sub := [9][9]bool{}, [9][9]bool{}, [9][9]bool{} for i := 0; i < 9; i++ { for j := 0; j < 9; j++ { num := board[i][j] - byte('1') if num < 0 || num > 9 { continue } k := i/3*3 + j/3 if row[i][num] || col[j][num] || sub[k][num] { return false } row[i][num] = true col[j][num] = true sub[k][num] = true } } return true } -
/** * @param {character[][]} board * @return {boolean} */ var isValidSudoku = function (board) { let row = [...Array(9)].map(() => Array(9).fill(false)); let col = [...Array(9)].map(() => Array(9).fill(false)); let sub = [...Array(9)].map(() => Array(9).fill(false)); for (let i = 0; i < 9; ++i) { for (let j = 0; j < 9; ++j) { const num = board[i][j].charCodeAt() - '1'.charCodeAt(); if (num < 0 || num > 9) { continue; } const k = Math.floor(i / 3) * 3 + Math.floor(j / 3); if (row[i][num] || col[j][num] || sub[k][num]) { return false; } row[i][num] = true; col[j][num] = true; sub[k][num] = true; } } return true; }; -
function isValidSudoku(board: string[][]): boolean { const row: boolean[][] = Array.from({ length: 9 }, () => Array.from({ length: 9 }, () => false), ); const col: boolean[][] = Array.from({ length: 9 }, () => Array.from({ length: 9 }, () => false), ); const sub: boolean[][] = Array.from({ length: 9 }, () => Array.from({ length: 9 }, () => false), ); for (let i = 0; i < 9; ++i) { for (let j = 0; j < 9; ++j) { const num = board[i][j].charCodeAt(0) - '1'.charCodeAt(0); if (num < 0 || num > 8) { continue; } const k = Math.floor(i / 3) * 3 + Math.floor(j / 3); if (row[i][num] || col[j][num] || sub[k][num]) { return false; } row[i][num] = true; col[j][num] = true; sub[k][num] = true; } } return true; }