Valid Sudoku (Leet Code-36)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 36. This is a Leet code problem named Valid Sudoku We will solve it using python and it is the best space and time-optimized solution.

Question of 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:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
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

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 '.'.

Approach to solve Valid Sudoku

Since we can see that there are three conditions for Sudoku to be valid so we will split our problem into three steps.

Step 1: In the first step, we will check for each row such that any single row cannot contain the same element.

Step 2: In the second step, we will check for each column such that any single column cannot contain the same element.

Step 3: In the third step, we will check for each 3*3 box such that any single 3*3 box cannot contain the same element.

Python Code for Valid Sudoku

class Solution:
    def isValidSudoku(self, board ) -> bool:
              
        #check if there any same number in a row
        for row in board:
            elem=[]            
            for j in row :
                if(j!="."):
                    if (j in elem):
                         
                        return False
                    else:
                        elem.append(j)
        
  
        #check if there any same number in a column
        for i in range(len(board)):
            elem = [] 
            for j in range(9):
                if(board[j][i] not in elem and board[j][i]!="."):
                    elem.append(board[j][i])
                elif (board[j][i]!="."):
                    return False
 
        
    
        #check if there any same number in a 3*3 box
        #run for 3 rows at a time
        for i in range(0,9,3):   
            #run for 3 cols at a time
            for j in range(0,9,3) :
                elem=[]
                for k in range(i,i+3):                    
                    for l in range(j,j+3):
                        if(board[k][l] not in elem and board[k][l]!="."):
                            elem.append(board[k][l])
                        elif (board[k][l]!="."):
                            return False
                           
            
        return True