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

Java

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

All Problems

All Solutions