# Is Sudoku Valid

Last updated: 8th Sept, 2020

#### Problem Statement

Given an incomplete Sudoku configuration in terms of a 9x9 2-D square matrix (mat[][]) the task to check if the configuration has a solution or not. Note: an incomplete Sudoku state - that is a 0 represents empty block.
Example 1:
1
3 0 6 5 0 8 4 0 0
5 2 0 0 0 0 0 0 0
0 8 7 0 0 0 0 3 1
0 0 3 0 1 0 0 8 0
9 0 0 8 6 3 0 0 5
0 5 0 0 9 0 6 0 0
1 3 0 0 0 0 2 5 0
0 0 0 0 0 0 0 7 4
0 0 5 2 0 6 3 0 0
>> 1
Example 2:
1
3 6 7 5 3 5 6 2 9
1 2 7 0 9 3 6 0 6
2 6 1 8 7 9 2 0 2
3 7 5 9 2 2 8 9 7
3 6 1 2 9 3 1 9 4
7 8 4 5 0 3 6 1 0
6 3 2 0 6 1 5 5 4
7 6 5 6 9 3 7 4 5
2 5 4 7 4 4 3 0 7
>> 0

Approach:

The above problem takes input T, mat indicating testcases and list of numbers ranging from 0 to 9 in 1D array. This matrix is converted into 2D matrix ,i.e, 9x9 matrix and stored in variable array. Each element in the matrix has its own position i denoting position of the element in row and j denoting the position of the element in column. The output can be obtained by looping through the entire elements in the matrix array.
CONDITIONS FOR SUDOKU CONFIGURATION TO BE INVALID :
Consider if array[1][2] = 4 then

- If element 4 is present in same row of index 1
- If element 4 is present in same column of index 2
- If element 4 is present twice in the same box
- If the sum on each row equals 45
- If the sum on each column equals 45
- If the sum on each box equals 45

Complexity Analysis :

- Time Complexity- O(n^2)
- Space Complexity- O(n^2)

###### Python Code

    class Sudoku:

        # method used to check validity of the inputs in sudoku
        def solution(self):
            T = int(input())
            for i in range(T):
                mat = [x for x in input().replace("0",".").split()]
                array = []
                for i in range(0,81,9):
                    array.append(mat[i:i+9])
                    row = [set() for _ in range(0,9)]
                    col = [set() for _ in range(0,9)]
                    box = [set() for _ in range(0,9)]
                    flag = True
                for i in range(0,9):
                    for j in range(0,9):
                        num = array[i][j]
                        if num == ".":
                            continue
                        if num in row[i] or num in col[j] or num in box[(i//3)*3 + j // 3]:
                            flag = False
                            break
                        row[i].add(num)
                        col[j].add(num)
                        box[i//3*3 + j // 3].add(num)
                if flag:
                    print(1)
                else:
                    print(0)
    a = Sudoku()
    a.solution()