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:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Image text

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-9 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

  • 
    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;
    }
    
    

All Problems

All Solutions