{x}
blog image

Valid Sudoku

Determine if a 9 x 9 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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without 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 == 9
  • board[i].length == 9
  • board[i][j] is a digit 1-9 or '.'.

Solution Explanation: Valid Sudoku

The problem requires determining if a 9x9 Sudoku board is valid. A valid Sudoku board adheres to three rules:

  1. Each row contains the digits 1-9 without repetition.
  2. Each column contains the digits 1-9 without repetition.
  3. Each of the nine 3x3 sub-boxes contains the digits 1-9 without repetition.

The most efficient approach involves a single pass through the board. We use three 9x9 boolean arrays (row, col, sub) to track seen numbers. row[i][j] will be true if digit j+1 has been seen in row i. Similarly, col[i][j] tracks columns and sub[i][j] tracks 3x3 sub-boxes.

The algorithm works as follows:

  1. Initialization: Create the three boolean arrays and initialize them to false.
  2. Iteration: Iterate through each cell of the Sudoku board.
  3. Check and Update: If the cell is not empty (i.e., not a '.'), convert the character to an integer num (subtracting 1 to use 0-based indexing). Calculate the index k for the 3x3 sub-box. If row[i][num], col[j][num], or sub[k][num] is already true, it means the number has been seen before in the same row, column, or sub-box, indicating an invalid Sudoku. Return false immediately. Otherwise, set row[i][num], col[j][num], and sub[k][num] to true.
  4. Return True: If the iteration completes without finding any violations, return true, indicating a valid Sudoku.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the number of cells in the Sudoku board (81). We visit each cell once.
  • Space Complexity: O(N), where N is the number of cells. We use three 9x9 arrays to track seen numbers.

Code in Different Languages

The code implementations in various programming languages reflect the algorithm described above. Each implementation utilizes boolean arrays to efficiently check for repeated numbers in rows, columns, and sub-boxes. The code examples provided earlier demonstrate this approach. Note the minor variations to handle array/list creation and indexing conventions specific to each language. They all achieve the same underlying logic and complexity.