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
19
without repetition.  Each column must contain the digits
19
without repetition.  Each of the 9
3x3
subboxes of the grid must contain the digits19
without 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 subbox, 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
19
and 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
Java

public class Valid_Sudoku { /* * @note: 三个连续ifelse可以优化到一个ifelse * * 记住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]; // ith 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 number1, is its index in every checking array int n = board[i][j]  '1'; // check three array, if already set true // submatrix 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; } } }

// OJ: https://leetcode.com/problems/validsudoku/ // 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(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