Given an incomplete Sudoku configuration in terms of a 9x9  2-D square matrix(mat[][]) the task to check if the current configuration is valid or not where a 0 represents an empty block.
Note: Current valid configuration does not ensure validity of the final solved sudoku. 
Refer to this : https://en.wikipedia.org/wiki/Sudoku
Example 1:
Input: mat[][] = [
[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]
]
Output: 1
Explaination: It is possible to have a
proper sudoku.
Your Task:
You do not need to read input or print anything. Your task is to complete the function isValid() which takes mat[][] as input parameter and returns 1 if any solution is possible. Otherwise, returns 0.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)
Constraints:
0 ≤ mat[i][j] ≤ 9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3

class Solution:
    def isValid(self, mat):
        # code here

Solutions:
import collections

class Solution:

	def isValid(self, mat):
		rows = collections.defaultdict(set)
		cols = collections.defaultdict(set)
		squares = collections.defaultdict(set)
		for r in range(9):
			for c in range(9):
				if mat[r][c] == 0:
					continue
				if mat[r][c] in rows[r] or mat[r][c] in cols[c] or mat[r][c] in squares[r // 3, c // 3]:
					return 0
				rows[r].add(mat[r][c])
				cols[c].add(mat[r][c])
				squares[r // 3, c // 3].add(mat[r][c])
		return 1


from collections import defaultdict

class Solution:

	def isValid(self, mat):
		n = len(mat)
		m = len(mat[0])
		rows = defaultdict(set)
		cols = defaultdict(set)
		rectangle = defaultdict(set)
		for i in range(0, n):
			for j in range(0, m):
				if mat[i][j] == 0:
					continue
				if mat[i][j] in rows[i] or mat[i][j] in cols[j] or mat[i][j] in rectangle[i // 3, j // 3]:
					return 0
				rows[i].add(mat[i][j])
				cols[j].add(mat[i][j])
				rectangle[i // 3, j // 3].add(mat[i][j])
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			dicr = {}
			dicc = {}
			for j in range(9):
				if mat[i][j] != 0:
					if mat[i][j] in dicr:
						return 0
					else:
						dicr[mat[i][j]] = 1
			for k in range(9):
				if mat[k][i] != 0:
					if mat[k][i] in dicc:
						return 0
					else:
						dicc[mat[k][i]] = 1
		r = 0
		c = 0
		for i in range(9):
			if i == 3 or i == 6:
				c = 0
				r = i
			else:
				c = 3 * (i % 3)
			dup = []
			for j in range(r, r + 3):
				for k in range(c, c + 3):
					if mat[j][k] != 0:
						if mat[j][k] in dup:
							return 0
						else:
							dup.append(mat[j][k])
		return 1


class Solution:

	def isValid(self, mat):
		col = [set() for _ in range(9)]
		row = [set() for _ in range(9)]
		squares = [[set() for _ in range(9)] for _ in range(9)]
		for i in range(9):
			for j in range(9):
				if mat[i][j] == 0:
					continue
				if mat[i][j] in col[j] or mat[i][j] in row[i] or mat[i][j] in squares[i // 3][j // 3]:
					return 0
				col[j].add(mat[i][j])
				row[i].add(mat[i][j])
				squares[i // 3][j // 3].add(mat[i][j])
		return 1


class Solution:

	def isValid(self, mat):
		r = [[0 for i in range(9)] for i in range(9)]
		c = [[0 for i in range(9)] for i in range(9)]
		s = [[[0 for i in range(9)] for i in range(3)] for i in range(3)]
		number = 0
		for i in range(0, 9):
			for j in range(0, 9):
				if mat[i][j] > 0 and mat[i][j] <= 9:
					number = mat[i][j] - 1
					if r[i][number] != 0:
						return 0
					r[i][number] = 1
					if c[j][number] != 0:
						return 0
					c[j][number] = 1
					if s[i // 3][j // 3][number] != 0:
						return 0
					s[i // 3][j // 3][number] = 1
		return 1


def isValidSudoku(board):
	N = 9
	unique = [False] * (N + 1)
	for i in range(0, N):
		for m in range(0, N + 1):
			unique[m] = False
		for j in range(0, N):
			Z = board[i][j]
			if Z and unique[Z] == True:
				return False
			unique[Z] = True
	for i in range(0, N):
		for m in range(0, N + 1):
			unique[m] = False
		for j in range(0, N):
			Z = board[j][i]
			if Z and unique[Z] == True:
				return False
			unique[Z] = True
	for i in range(0, N - 2, 3):
		for j in range(0, N - 2, 3):
			for m in range(0, N + 1):
				unique[m] = False
			for k in range(0, 3):
				for l in range(0, 3):
					X = i + k
					Y = j + l
					Z = board[X][Y]
					if Z and unique[Z] == True:
						return False
					unique[Z] = True
	return True

class Solution:

	def isValid(self, mat):
		return int(isValidSudoku(mat))


class Solution:

	def isValid(self, mat):

		def isValidBlock(block):
			value_set = set()
			for x in block:
				if x in value_set:
					return False
				elif x != 0:
					value_set.add(x)
			return True
		for i in range(9):
			if not isValidBlock(mat[i]):
				return 0
			if not isValidBlock([mat[j][i] for j in range(9)]):
				return 0
			block = mat[3 * (i // 3)][3 * (i % 3):3 * (i % 3) + 3] + mat[3 * (i // 3) + 1][3 * (i % 3):3 * (i % 3) + 3] + mat[3 * (i // 3) + 2][3 * (i % 3):3 * (i % 3) + 3]
			if not isValidBlock(block):
				return 0
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			c = [0] * 10
			for j in range(9):
				if mat[i][j] == 0:
					continue
				c[mat[i][j]] += 1
				if c[mat[i][j]] > 1:
					return 0
		for j in range(9):
			c = [0] * 10
			for i in range(9):
				if mat[i][j] == 0:
					continue
				c[mat[i][j]] += 1
				if c[mat[i][j]] > 1:
					return 0
		for k in range(9):
			x = k // 3
			y = k % 3
			c = [0] * 10
			for i in range(3 * x, 3 * x + 3):
				for j in range(3 * y, 3 * y + 3):
					if mat[i][j] == 0:
						continue
					c[mat[i][j]] += 1
					if c[mat[i][j]] > 1:
						return 0
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			l = []
			for x in mat[i]:
				if x in l:
					return 0
				if x != 0:
					l.append(x)
		for i in range(9):
			l = []
			for j in range(9):
				if mat[j][i] in l:
					return 0
				if mat[j][i] != 0:
					l.append(mat[j][i])
		lst = []
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				l = []
				l += mat[i][j:j + 3]
				l += mat[i + 1][j:j + 3]
				l += mat[i + 2][j:j + 3]
				lst.append(l)
		for i in range(9):
			l = []
			for x in lst[i]:
				if x in l:
					return 0
				if x != 0:
					l.append(x)
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					inx = mat[i][j]
					mat[i][j] = 0
					if self.isvalid(i, j, mat, inx):
						continue
					else:
						return 0
		return 1

	def isvalid(self, row, col, mat, inx):
		for i in range(9):
			if mat[row][i] == inx:
				return 0
			if mat[i][col] == inx:
				return 0
			if mat[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == inx:
				return 0
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			row = set()
			for j in range(9):
				if mat[i][j] == 0:
					continue
				if mat[i][j] in row:
					return 0
				row.add(mat[i][j])
		for j in range(9):
			col = set()
			for i in range(9):
				if mat[i][j] == 0:
					continue
				if mat[i][j] in col:
					return 0
				col.add(mat[i][j])
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				subgrid = set()
				for k in range(3):
					for l in range(3):
						x = i + k
						y = j + l
						if mat[x][y] == 0:
							continue
						if mat[x][y] in subgrid:
							return 0
						subgrid.add(mat[x][y])
		return 1


import collections

class Solution:

	def isValid(self, mat):
		row = collections.defaultdict(set)
		col = collections.defaultdict(set)
		box = collections.defaultdict(set)
		for i in range(9):
			for j in range(9):
				if mat[i][j] == 0:
					continue
				if mat[i][j] in row[i] or mat[i][j] in col[j] or mat[i][j] in box[i // 3, j // 3]:
					return 0
				row[i].add(mat[i][j])
				col[j].add(mat[i][j])
				box[i // 3, j // 3].add(mat[i][j])
		return 1


class Solution:

	def isValid(self, board):
		import collections
		row = collections.defaultdict(set)
		col = collections.defaultdict(set)
		square = collections.defaultdict(set)
		for i in range(9):
			for j in range(9):
				num = board[i][j]
				if num == 0:
					continue
				if num in row[i] or num in col[j] or num in square[i // 3, j // 3]:
					return 0
				row[i].add(num)
				col[j].add(num)
				square[i // 3, j // 3].add(num)
		return 1


class Solution:

	def isValid(self, board):

		def find(values):
			ans = [i for i in values if i != 0]
			if len(ans) == len(set(ans)):
				return True
			return False

		def validrows(board):
			for i in board:
				if find(i) == False:
					return False
			return True

		def validcol(board):
			for i in zip(*board):
				if find(i) == False:
					return False
			return True

		def validsq(board):
			for i in range(0, len(board), 3):
				for j in range(0, len(board), 3):
					sq = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
					if find(sq) == False:
						return False
			return True
		if validrows(board) and validcol(board) and validsq(board):
			return 1
		return 0


class Solution:

	def isValid(self, mat):
		for row in mat:
			seen = set()
			for num in row:
				if num != 0:
					if num in seen:
						return 0
					seen.add(num)
		for j in range(9):
			seen = set()
			for i in range(9):
				if mat[i][j] != 0:
					if mat[i][j] in seen:
						return 0
					seen.add(mat[i][j])
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				seen = set()
				for x in range(3):
					for y in range(3):
						num = mat[i + x][j + y]
						if num != 0:
							if num in seen:
								return 0
							seen.add(num)
		return 1


class Solution:

	def isCheck(self, arr):
		data = {}
		for x in arr:
			if x:
				if data.get(x) == None:
					data[x] = 1
				else:
					return False
		return True

	def isValid(self, mat):
		for x in range(9):
			if not self.isCheck(mat[x]):
				return 0
			if not self.isCheck([y[x] for y in mat]):
				return 0
		for x in range(3):
			for y in range(3):
				data = []
				for _x in range(3 * x, 3 * x + 3):
					for _y in range(3 * y, 3 * y + 3):
						data.append(mat[_x][_y])
				if not self.isCheck(data):
					return 0
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					val = mat[i][j]
					mat[i][j] = 0
					if self.check(i, j, mat, val) == True:
						mat[i][j] = val
					else:
						return 0
		return 1

	def check(self, row, col, mat, c):
		for i in range(9):
			if mat[i][col] == c:
				return False
			elif mat[row][i] == c:
				return False
			elif mat[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
				return False
		return True


class Solution:

	def is_valid(self, row, col, mat, val):
		for i in range(9):
			if mat[i][col] == val:
				return False
		for i in range(9):
			if mat[row][i] == val:
				return False
		for i in range(9):
			if mat[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == val:
				return False
		return True

	def isValid(self, mat):
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					val = mat[i][j]
					mat[i][j] = 0
					if not self.is_valid(i, j, mat, val):
						mat[i][j] == val
						return 0
					mat[i][j] == val
		return 1


from collections import defaultdict

class Solution:

	def isValid(self, mat):
		board = mat
		col = defaultdict(set)
		row = defaultdict(set)
		box = defaultdict(set)
		for r in range(9):
			for c in range(9):
				if board[r][c] == 0:
					continue
				if board[r][c] in row[r] or board[r][c] in col[c] or board[r][c] in box[r // 3, c // 3]:
					return 0
				row[r].add(board[r][c])
				col[c].add(board[r][c])
				box[r // 3, c // 3].add(board[r][c])
		return 1


class Solution:

	def isValid(self, board):
		r_d = {}
		c_d = {}
		b_d = [[set() for i in range(3)] for j in range(3)]
		for i in range(9):
			r_d[i] = set()
			c_d[i] = set()
		for i in range(9):
			for j in range(9):
				if board[i][j] != 0:
					if board[i][j] in r_d[i]:
						return 0
					else:
						r_d[i].add(board[i][j])
				if board[j][i] != 0:
					if board[j][i] in c_d[i]:
						return 0
					else:
						c_d[i].add(board[j][i])
				if board[i][j] != 0:
					_i = i // 3
					_j = j // 3
					if board[i][j] in b_d[_i][_j]:
						return 0
					else:
						b_d[_i][_j].add(board[i][j])
		return 1


class Solution:

	def isValid(self, matrix):

		def isValid(r, c, nbr):
			for i in range(n):
				if i != c and matrix[r][i] == nbr:
					return False
			for i in range(n):
				if i != r and matrix[i][c] == nbr:
					return False
			(mr, mc) = (r // 3, c // 3)
			for i in range(3):
				for j in range(3):
					(cr, cc) = (3 * mr + i, 3 * mc + j)
					if cr == r and cc == c:
						continue
					if matrix[cr][cc] == nbr:
						return False
			return True
		n = 9
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == 0:
					continue
				res = isValid(i, j, matrix[i][j])
				if not res:
					return 0
		return 1


class Solution:

	def isValid(self, mat):

		def check(p, q):
			for m in range(9):
				if m != q and mat[p][m] == mat[p][q]:
					return 0
			for m in range(9):
				if m != p and mat[m][q] == mat[p][q]:
					return 0
			a = p // 3 * 3
			b = q // 3 * 3
			for row in range(a, a + 3):
				for col in range(b, b + 3):
					if row != p and col != q:
						if mat[p][q] == mat[row][col]:
							return 0
			return 1
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0 and check(i, j) == 0:
					return 0
		return 1


class Solution:

	def isValid(self, mat):
		n = len(mat)
		m = len(mat[0])
		ret = 1
		for i in range(n):
			cur_map = {}
			for j in range(m):
				if mat[i][j] == 0:
					continue
				if mat[i][j] in cur_map:
					ret = 0
					break
				cur_map[mat[i][j]] = 1
			if ret == 0:
				break
		if ret == 0:
			return ret
		for j in range(m):
			cur_map = {}
			for i in range(n):
				if mat[i][j] == 0:
					continue
				if mat[i][j] in cur_map:
					ret = 0
					break
				cur_map[mat[i][j]] = 1
			if ret == 0:
				break
		if ret == 0:
			return ret
		for i in range(0, n, 3):
			for j in range(0, m, 3):
				cur_map = {}
				for k in range(3):
					for l in range(3):
						if mat[i + k][j + l] == 0:
							continue
						if mat[i + k][j + l] in cur_map:
							ret = 0
							break
						cur_map[mat[i + k][j + l]] = 1
				if ret == 0:
					break
		return ret


class Solution:

	def isValid(self, board):

		def rows(board):
			return board

		def cols(board):
			columns = []
			for i in range(9):
				line = []
				for j in range(9):
					line.append(board[j][i])
				columns.append(line)
			return columns

		def boxes_3_3(board):
			box = []
			for i in range(1, 9, 3):
				for j in range(1, 9, 3):
					l = [board[i - 1][j - 1], board[i - 1][j], board[i - 1][j + 1]]
					l += [board[i][j - 1], board[i][j], board[i][j + 1]]
					l += [board[i + 1][j - 1], board[i + 1][j], board[i + 1][j + 1]]
					box.append(l)
			return box

		def valid(boxes, columns, rows):
			for i in range(9):
				(d1, d2, d3) = ({}, {}, {})
				for j in boxes[i]:
					if j not in d1:
						d1[j] = 1
					else:
						d1[j] += 1
				for j in columns[i]:
					if j not in d2:
						d2[j] = 1
					else:
						d2[j] += 1
				for j in rows[i]:
					if j not in d3:
						d3[j] = 1
					else:
						d3[j] += 1
				for j in d1:
					if d1[j] > 1 and j != 0:
						return False
				for j in d2:
					if d2[j] > 1 and j != 0:
						return False
				for j in d3:
					if d3[j] > 1 and j != 0:
						return False
			return True
		rows = rows(board)
		columns = cols(board)
		boxes = boxes_3_3(board)
		if valid(boxes, columns, rows):
			return 1
		return 0


class Solution:

	def isValid(self, mat):
		h = set()
		for i in range(9):
			for j in range(9):
				char = str(mat[i][j])
				if int(char) != 0:
					if (i, char) in h or (char, j) in h or (char, i // 3, j // 3) in h:
						return 0
					h.add((i, char))
					h.add((char, j))
					h.add((char, i // 3, j // 3))
		return 1


class Solution:

	def isValid(self, mat):
		col = [[] for i in range(9)]
		row = [[] for i in range(9)]
		grid = [[] for i in range(9)]
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					if mat[i][j] not in row[i]:
						row[i] += [mat[i][j]]
					else:
						return 0
					if mat[i][j] not in col[j]:
						col[j] += [mat[i][j]]
					else:
						return 0
					if mat[i][j] not in grid[3 * (i // 3) + j // 3]:
						grid[3 * (i // 3) + j // 3] += [mat[i][j]]
					else:
						return 0
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			row = []
			for j in range(9):
				if mat[i][j] == 0:
					continue
				elif mat[i][j] not in row:
					row.append(mat[i][j])
				else:
					return 0
		for i in range(9):
			col = []
			for j in range(9):
				if mat[j][i] == 0:
					continue
				elif mat[j][i] not in col:
					col.append(mat[j][i])
				else:
					return 0

		def is3by3valid(r, c):
			elements = []
			for i in range(r, r + 3):
				for j in range(c, c + 3):
					if mat[i][j] == 0:
						continue
					elif mat[i][j] not in elements:
						elements.append(mat[i][j])
					else:
						return False
			return True
		for r in range(0, 9, 3):
			for c in range(0, 9, 3):
				if not is3by3valid(r, c):
					return 0
		return 1


class Solution:

	def isValid(self, mat):
		for r in range(9):
			row = [c for c in mat[r] if c != 0]
			if len(row) != len(set(row)):
				return 0
		for c in range(9):
			col = [mat[r][c] for r in range(9) if mat[r][c] != 0]
			if len(col) != len(set(col)):
				return 0

		def subbox(R, C):
			l = set()
			for r in range(R, R + 3):
				for c in range(C, C + 3):
					if mat[r][c] == 0:
						continue
					if mat[r][c] not in l:
						l.add(mat[r][c])
					else:
						return False
			return True
		for r in range(0, 9, 3):
			for c in range(0, 9, 3):
				if not subbox(r, c):
					return 0
		return 1


class Solution:

	def isValid(self, mat):
		row = col = len(mat)
		if isRowValid(mat) == 0:
			return 0
		elif isColValid(mat) == 0:
			return 0
		elif is3by3Valid(mat) == 0:
			return 0
		else:
			return 1

def isRowValid(mat):
	for i in range(len(mat)):
		dict_ = {}
		for j in range(len(mat)):
			if mat[i][j] == 0:
				continue
			if mat[i][j] not in dict_:
				dict_[mat[i][j]] = 1
			else:
				return 0
	return 1

def isColValid(mat):
	for i in range(len(mat)):
		dict_ = {}
		for j in range(len(mat)):
			if mat[j][i] == 0:
				continue
			if mat[j][i] not in dict_:
				dict_[mat[j][i]] = 1
			else:
				return 0
	return 1

def is3by3Valid(mat):
	for p in range(0, 9, 3):
		for i in range(0, 9, 3):
			dict_ = {}
			for j in range(i, i + 3):
				for k in range(p, p + 3):
					if mat[j][k] == 0:
						continue
					if mat[j][k] not in dict_:
						dict_[mat[j][k]] = 1
					else:
						return 0
	return 1


class Solution:

	def isValid(self, mat):
		rowCheck = {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: []}
		colCheck = {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: []}
		gridCheck = {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: []}
		for i in range(len(mat)):
			for j in range(len(mat)):
				check = mat[i][j]
				if check != 0:
					if check in rowCheck[i] or check in colCheck[j]:
						return 0
					rowCheck[i].append(check)
					colCheck[j].append(check)
					grid = i // 3 * 3 + j // 3
					if check in gridCheck[grid]:
						return 0
					gridCheck[grid].append(check)
		return 1


class Solution:

	def isValid(self, M):
		for i in range(9):
			vis = [False] * 10
			for j in range(9):
				v = M[i][j]
				if v and vis[v]:
					return 0
				vis[v] = True
		for j in range(9):
			vis = [False] * 10
			for i in range(9):
				v = M[i][j]
				if v and vis[v]:
					return 0
				vis[v] = True
		for a in range(3):
			for b in range(3):
				(r, c) = (a * 3, b * 3)
				vis = [False] * 10
				for i in range(3):
					for j in range(3):
						v = M[r + i][c + j]
						if v and vis[v]:
							return 0
						vis[v] = True
		return 1


def isRowValid(mat, row):
	arr = set()
	for i in range(9):
		if mat[row][i] == 0:
			continue
		elif mat[row][i] in arr:
			return False
		arr.add(mat[row][i])
	return True

def isColValid(mat, col):
	arr = set()
	for i in range(9):
		if mat[i][col] == 0:
			continue
		elif mat[i][col] in arr:
			return False
		arr.add(mat[i][col])
	return True

def isSmallMatValid(mat, row, col):
	arr = set()
	for i in range(row, row + 3):
		for j in range(col, col + 3):
			if mat[i][j] == 0:
				continue
			elif mat[i][j] in arr:
				return False
			arr.add(mat[i][j])
	return True

class Solution:

	def isValid(self, mat):
		for row in range(0, 9):
			if isRowValid(mat, row) is False:
				return 0
		for col in range(0, 9):
			if isColValid(mat, col) is False:
				return 0
		for col in range(0, 9, 3):
			for row in range(0, 9, 3):
				if isSmallMatValid(mat, row, col) is False:
					return 0
		return 1


from collections import defaultdict

class Solution:

	def isValid(self, mat):
		rows = defaultdict(list)
		cols = defaultdict(list)
		cells = defaultdict(list)
		for i in range(9):
			for j in range(9):
				val = mat[i][j]
				if val != 0:
					if val in rows[i]:
						return 0
					else:
						rows[i].append(val)
					if val in cols[j]:
						return 0
					else:
						cols[j].append(val)
					if val in cells[i // 3, j // 3]:
						return 0
					else:
						cells[i // 3, j // 3].append(val)
		return 1


class Solution:

	def isValid(self, mat):

		def check(row, col, mat, val):
			for i in range(9):
				if mat[row][i] == val:
					return 0
			for i in range(9):
				if mat[i][col] == val:
					return 0
			for i in range(9):
				if mat[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == val:
					return 0
			return 1
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					val = mat[i][j]
					mat[i][j] = 0
					if check(i, j, mat, val) == 1:
						mat[i][j] = val
					else:
						return 0
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			mp = {}
			for j in range(9):
				if mat[i][j] != 0 and mat[i][j] in mp:
					return 0
				mp[mat[i][j]] = 1
		for i in range(9):
			mp = {}
			for j in range(9):
				if mat[j][i] != 0 and mat[j][i] in mp:
					return 0
				mp[mat[j][i]] = 1
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				mp = {}
				for p in range(i, i + 3):
					for q in range(j, j + 3):
						if mat[p][q] != 0 and mat[p][q] in mp:
							return 0
						mp[mat[p][q]] = 1
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


class Solution:

	def isValid(self, mat):
		rc = []
		cc = []
		for i in range(9):
			for j in range(9):
				re = mat[i][j]
				ce = mat[j][i]
				if re != 0:
					if re in rc:
						return 0
					else:
						rc.append(re)
				if ce != 0:
					if ce in cc:
						return 0
					else:
						cc.append(ce)
			cc = []
			rc = []
		check = []
		for l in range(0, 8, 3):
			for i in range(0, 8, 3):
				for j in range(3):
					for k in range(3):
						temp = mat[j + l][k + i]
						if temp != 0:
							if temp in check:
								return 0
							else:
								check.append(temp)
				check = []
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


class Solution:

	def getSquareRange(self, num):
		if num in range(0, 3):
			return (0, 3)
		elif num in range(3, 6):
			return (3, 6)
		else:
			return (6, 9)

	def isSameSquare(self, mat, i, j):
		(x, y) = self.getSquareRange(i)
		(q, r) = self.getSquareRange(j)
		for m in range(x, y):
			for n in range(q, r):
				if not (i == m and j == n) and mat[m][n] == mat[i][j]:
					return True
		return False

	def isSameRow(self, mat, i, j):
		for m in range(9):
			if i != m and mat[i][j] == mat[m][j]:
				return True
		return False

	def isSameColumn(self, mat, i, j):
		for m in range(9):
			if j != m and mat[i][m] == mat[i][j]:
				return True
		return False

	def isValid(self, mat):
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0 and (self.isSameRow(mat, i, j) or self.isSameColumn(mat, i, j) or self.isSameSquare(mat, i, j)):
					return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


from collections import defaultdict

class Solution:

	def isValid(self, board):
		rows = defaultdict(set)
		cols = defaultdict(set)
		subMatrix = defaultdict(set)
		for r in range(9):
			for c in range(9):
				if board[r][c] == 0:
					continue
				if board[r][c] in rows[r] or board[r][c] in cols[c] or board[r][c] in subMatrix[r // 3, c // 3]:
					return 0
				rows[r].add(board[r][c])
				cols[c].add(board[r][c])
				subMatrix[r // 3, c // 3].add(board[r][c])
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


class Solution:

	def isValid(self, mat):
		cols = {1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 0: []}
		rows = {1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 0: []}
		squares = {(0, 0): [], (1, 1): [], (2, 2): [], (0, 1): [], (0, 2): [], (1, 0): [], (1, 2): [], (2, 0): [], (2, 1): []}
		for r in range(9):
			for c in range(9):
				if mat[r][c] == 0:
					continue
				if mat[r][c] in rows[r] or mat[r][c] in cols[c] or mat[r][c] in squares[r // 3, c // 3]:
					return 0
				rows[r].append(mat[r][c])
				cols[c].append(mat[r][c])
				squares[r // 3, c // 3].append(mat[r][c])
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


class Solution:

	def notInRow(self, arr, row):
		flag = [0] * 9
		for i in range(0, 9):
			curr = arr[row][i]
			if curr != 0:
				if flag[curr - 1]:
					return False
				flag[curr - 1] = 1
		return True

	def notInCol(self, arr, col):
		flag = [0] * 9
		for i in range(0, 9):
			curr = arr[i][col]
			if curr != 0:
				if flag[curr - 1]:
					return False
				flag[curr - 1] = 1
		return True

	def notInBox(self, arr, startRow, startCol):
		flag = [0] * 9
		for row in range(startRow, startRow + 3):
			for col in range(startCol, startCol + 3):
				curr = arr[row][col]
				if curr != 0:
					if flag[curr - 1]:
						return False
					flag[curr - 1] = 1
		return True

	def isValid(self, arr):
		n = len(arr)
		for i in range(n):
			if not self.notInRow(arr, i):
				return 0
		for i in range(n):
			if not self.notInCol(arr, i):
				return 0
		for i in range(0, n, 3):
			for j in range(0, n, 3):
				if not self.notInBox(arr, i, j):
					return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


import collections

class Solution:

	def isValid(self, mat):
		for r in range(9):
			for c in range(9):
				if mat[r][c] != 0 and (not self.isValidUtil(mat, r, c)):
					return 0
		return 1

	def isValidUtil(self, mat, rowIdx, colIdx):
		for i in range(9):
			if mat[rowIdx][colIdx] == mat[rowIdx][i] and colIdx != i:
				return False
			if mat[rowIdx][colIdx] == mat[i][colIdx] and rowIdx != i:
				return False
		r = rowIdx - rowIdx % 3
		c = colIdx - colIdx % 3
		for i in range(3):
			for j in range(3):
				if mat[rowIdx][colIdx] == mat[r + i][c + j] and rowIdx != r + i and (colIdx != c + j):
					return False
		return True

	def isValid(self, mat):
		rows = collections.defaultdict(set)
		cols = collections.defaultdict(set)
		squares = collections.defaultdict(set)
		for r in range(9):
			for c in range(9):
				if mat[r][c] == 0:
					continue
				if mat[r][c] in rows[r] or mat[r][c] in cols[c] or mat[r][c] in squares[r // 3, c // 3]:
					return 0
				rows[r].add(mat[r][c])
				cols[c].add(mat[r][c])
				squares[r // 3, c // 3].add(mat[r][c])
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


import collections

class Solution:

	def isValid(self, mat):
		for r in range(9):
			for c in range(9):
				if mat[r][c] != 0 and (not self.isValidUtil(mat, r, c)):
					return 0
		return 1

	def isValidUtil(self, mat, rowIdx, colIdx):
		for i in range(9):
			if mat[rowIdx][colIdx] == mat[rowIdx][i] and colIdx != i:
				return False
			if mat[rowIdx][colIdx] == mat[i][colIdx] and rowIdx != i:
				return False
		r = rowIdx - rowIdx % 3
		c = colIdx - colIdx % 3
		for i in range(3):
			for j in range(3):
				if mat[rowIdx][colIdx] == mat[r + i][c + j] and rowIdx != r + i and (colIdx != c + j):
					return False
		return True
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


class Solution:

	def isValid(self, mat):

		def isrowvalid(mat):
			for i in range(len(mat)):
				dicc = {}
				for j in range(len(mat)):
					if mat[i][j] == 0:
						continue
					if mat[i][j] not in dicc:
						dicc[mat[i][j]] = 1
					else:
						return 0
			return 1

		def iscolvalid(mat):
			for i in range(len(mat)):
				dicc = {}
				for j in range(len(mat)):
					if mat[j][i] == 0:
						continue
					if mat[j][i] not in dicc:
						dicc[mat[j][i]] = 1
					else:
						return 0
			return 1

		def is3by3valid(mat):
			for k in range(0, 9, 3):
				for l in range(0, 9, 3):
					dicc = {}
					for i in range(l, l + 3):
						for j in range(k, k + 3):
							if mat[i][j] == 0:
								continue
							if mat[i][j] not in dicc:
								dicc[mat[i][j]] = 1
							else:
								return 0
			return 1
		if isrowvalid(mat) == 0:
			return 0
		if iscolvalid(mat) == 0:
			return 0
		if is3by3valid(mat) == 0:
			return 0
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


from collections import defaultdict

class Solution:

	def isValid(self, mat):
		row = defaultdict(set)
		col = defaultdict(set)
		grid = defaultdict(set)
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					if mat[i][j] in row[i] or mat[i][j] in col[j] or mat[i][j] in grid[i // 3, j // 3]:
						return 0
					row[i].add(mat[i][j])
					col[j].add(mat[i][j])
					grid[i // 3, j // 3].add(mat[i][j])
		return 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		arr = input().split()
		mat = [[0] * 9 for x in range(9)]
		for i in range(81):
			mat[i // 9][i % 9] = int(arr[i])
		ob = Solution()
		print(ob.isValid(mat))


class Solution:

	def isValid(self, mat):
		big = set()
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					curr = str(mat[i][j])
					if (i, curr) in big or (curr, j) in big or (i // 3, j // 3, curr) in big:
						return 0
					big.add((i, curr))
					big.add((curr, j))
					big.add((i // 3, j // 3, curr))
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(9):
			d = {}
			for j in range(9):
				if mat[i][j] in d:
					return 0
				elif mat[i][j] == 0:
					pass
				else:
					d[mat[i][j]] = True
		for j in range(9):
			d = {}
			for i in range(9):
				if mat[i][j] == 0:
					pass
				elif mat[i][j] in d:
					return 0
				else:
					d[mat[i][j]] = True
		for m in range(0, 9, 3):
			for n in range(0, 9, 3):
				d = {}
				for i in range(n, n + 3):
					for j in range(m, m + 3):
						if mat[i][j] == 0:
							pass
						elif mat[i][j] in d:
							return 0
						else:
							d[mat[i][j]] = True
		return 1


class Solution:

	def isValid(self, mat):
		if rowisvalid(mat) == 0:
			return 0
		elif colisvalid(mat) == 0:
			return 0
		elif is3by3valid(mat) == 0:
			return 0
		else:
			return 1

def rowisvalid(mat):
	for i in range(len(mat)):
		dict = {}
		for j in range(len(mat)):
			if mat[i][j] == 0:
				continue
			if mat[i][j] not in dict:
				dict[mat[i][j]] = 1
			else:
				return 0
	return 1

def colisvalid(mat):
	for i in range(len(mat)):
		dict = {}
		for j in range(len(mat)):
			if mat[j][i] == 0:
				continue
			if mat[j][i] not in dict:
				dict[mat[j][i]] = 1
			else:
				return 0
	return 1

def is3by3valid(mat):
	for p in range(0, 9, 3):
		for i in range(0, 9, 3):
			dict = {}
			for j in range(p, p + 3):
				for k in range(i, i + 3):
					if mat[j][k] == 0:
						continue
					if mat[j][k] not in dict:
						dict[mat[j][k]] = 1
					else:
						return 0
	return 1


class Solution:

	def isValid(self, mat):

		def isSafe(mat, ele, r, c):
			rc = 0
			for i in range(9):
				if mat[i][c] == ele:
					rc += 1
					if rc > 1:
						return 0
			cc = 0
			for i in range(9):
				if mat[r][i] == ele:
					cc += 1
					if cc > 1:
						return 0
			br = r // 3 * 3
			bc = c // 3 * 3
			boc = 0
			for i in range(br, br + 3):
				for j in range(bc, bc + 3):
					if mat[i][j] == ele:
						boc += 1
						if boc > 1:
							return 0
			return 1
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					if isSafe(mat, mat[i][j], i, j) == 0:
						return 0
		return 1


class Solution:

	def isValid(self, board):
		record = set()
		(m, n) = (len(board), len(board[0]))
		for i in range(m):
			for j in range(n):
				if board[i][j] != 0:
					item1 = (board[i][j], 'in row', i)
					item2 = (board[i][j], 'in column', j)
					item3 = (board[i][j], 'in block', i // 3, j // 3)
					if item1 not in record:
						record.add(item1)
					else:
						return 0
					if item2 not in record:
						record.add(item2)
					else:
						return 0
					if item3 not in record:
						record.add(item3)
					else:
						return 0
		return 1


from collections import defaultdict

class Solution:

	def isValid(self, mat):
		flag = True
		for row in range(9):
			used = [0] * 9
			for i in range(9):
				if mat[row][i]:
					if used[mat[row][i] - 1]:
						flag = False
						break
					else:
						used[mat[row][i] - 1] = 1
		for col in range(9):
			used = [0] * 9
			for j in range(9):
				if mat[j][col]:
					if used[mat[j][col] - 1]:
						flag = False
						break
					else:
						used[mat[j][col] - 1] = 1
		for i in range(0, 7, 3):
			for j in range(0, 7, 3):
				used = [0] * 9
				for k in range(0, 3):
					for l in range(0, 3):
						if mat[i + k][j + l]:
							if used[mat[i + k][j + l] - 1]:
								flag = False
							else:
								used[mat[i + k][j + l] - 1] = 1
		if flag:
			return 1
		return 0


class Solution:

	def isValid(self, mat):
		(n, m) = (len(mat), len(mat[0]))
		for l in mat:
			s = set()
			for v in l:
				if v == 0:
					continue
				if v in s:
					return 0
				s.add(v)
		for j in range(m):
			s = set()
			for i in range(n):
				v = mat[i][j]
				if v == 0:
					continue
				if v in s:
					return 0
				s.add(v)
		for r in range(0, n, 3):
			for c in range(0, m, 3):
				s = set()
				for i in range(r, r + 3):
					for j in range(c, c + 3):
						v = mat[i][j]
						if v == 0:
							continue
						if v in s:
							return 0
						s.add(v)
		return 1


class Solution:

	def isValid(self, mat):

		def issafe(row, col, c):
			for i in range(9):
				if mat[row][i] == c:
					return False
				if mat[i][col] == c:
					return False
				if mat[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
					return False
			return True
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				if mat[i][j] != 0:
					temp = mat[i][j]
					mat[i][j] = '#'
					if issafe(i, j, temp) == False:
						return 0
					mat[i][j] = temp
		return 1


class Solution:

	def isValid(self, mat):
		rows = [set() for i in range(9)]
		cols = [set() for i in range(9)]
		boxes = [set() for i in range(9)]
		for r in range(9):
			for c in range(9):
				n = mat[r][c]
				if n != 0:
					if n in rows[r]:
						return 0
					else:
						rows[r].add(n)
					if n in cols[c]:
						return 0
					else:
						cols[c].add(n)
					b = r // 3 * 3 + c // 3
					if n in boxes[b]:
						return 0
					else:
						boxes[b].add(n)
		return 1


class Solution:

	def isValid(self, mat):
		for i in range(0, 9, 1):
			for j in range(0, 9, 1):
				if mat[i][j] != 0:
					if not self.isSafe(mat, i, j):
						return 0
		return 1

	def isSafe(self, sudoku, row, col):
		val = sudoku[row][col]
		for i in range(0, 9, 1):
			if sudoku[i][col] == val and i != row:
				return False
			if sudoku[row][i] == val and i != col:
				return False
			newRow = 3 * (row // 3) + i // 3
			newCol = 3 * (col // 3) + i % 3
			if newRow != row and newCol != col and (sudoku[newRow][newCol] == val):
				return False
		return True


import collections

class Solution:

	def isValid(self, mat):
		board = mat
		rows = collections.defaultdict(set)
		cols = collections.defaultdict(set)
		squares = collections.defaultdict(set)
		for i in range(9):
			for j in range(9):
				if board[i][j] == 0:
					continue
				if board[i][j] in rows[i] or board[i][j] in cols[j] or board[i][j] in squares[i // 3, j // 3]:
					return 0
				cols[j].add(board[i][j])
				rows[i].add(board[i][j])
				squares[i // 3, j // 3].add(board[i][j])
		return 1


class Solution:

	def isValid(self, mat):
		flag = 0
		for i in range(0, 9):
			d = {}
			for j in range(0, 9):
				if mat[i][j] == 0:
					continue
				if mat[i][j] not in d.keys():
					d[mat[i][j]] = 1
				else:
					return 0
		for i in range(0, 9):
			d = {}
			for j in range(0, 9):
				if mat[j][i] == 0:
					continue
				if mat[j][i] not in d.keys():
					d[mat[j][i]] = 1
				else:
					return 0
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				d = {}
				for p in range(j, j + 3):
					for q in range(i, i + 3):
						if mat[p][q] == 0:
							continue
						if mat[p][q] not in d.keys():
							d[mat[p][q]] = 1
						else:
							return 0
		return 1


class Solution:

	def isValid(self, mat):
		n = len(mat)
		for row in mat:
			found = [False] * 10
			for v in row:
				if v:
					if found[v]:
						return 0
					found[v] = True
		for i in range(n):
			found = [False] * 10
			for row in mat:
				if row[i]:
					if found[row[i]]:
						return 0
					found[row[i]] = True
		for i in range(n):
			found = [False] * 10
			for j in range(n):
				(a, b) = (i // 3 * 3 + j // 3, i % 3 * 3 + j % 3)
				if mat[a][b]:
					if found[mat[a][b]]:
						return 0
					found[mat[a][b]] = True
		return 1


class Solution:

	def isValid(self, mat):
		n = len(mat)
		for row in mat:
			c = [0] * 9
			for v in row:
				if v:
					c[v - 1] += 1
			if max(c) > 1:
				return 0
		for i in range(n):
			c = [0] * 9
			for row in mat:
				if row[i]:
					c[row[i] - 1] += 1
			if max(c) > 1:
				return 0
		for i in range(n):
			c = [0] * 9
			for j in range(n):
				(a, b) = (i // 3 * 3 + j // 3, i % 3 * 3 + j % 3)
				if mat[a][b]:
					c[mat[a][b] - 1] += 1
			if max(c) > 1:
				return 0
		return 1


class Solution:

	def isValid(self, mat):
		row_list = [set() for i in range(len(mat))]
		col_list = [set() for i in range(len(mat[0]))]
		block_list = [set() for i in range(9)]
		for r in range(len(mat)):
			for c in range(len(mat[r])):
				val = mat[r][c]
				if val == 0:
					continue
				if val in row_list[r]:
					return 0
				elif val in col_list[c]:
					return 0
				block_idx = r // 3 * 3 + c // 3
				if val in block_list[block_idx]:
					return 0
				row_list[r].add(val)
				col_list[c].add(val)
				block_list[block_idx].add(val)
		return 1


class Solution:

	def isValid(self, mat):
		moves = []
		for i in [-1, 0, 1]:
			for j in [-1, 0, 1]:
				moves.append((i, j))
		for i in range(9):
			row_wise = [0 for _ in range(11)]
			column_wise = [0 for _ in range(11)]
			for j in range(9):
				val = mat[i][j]
				if val != 0:
					if row_wise[val] == 1:
						return 0
					else:
						row_wise[val] = 1
				val = mat[j][i]
				if val != 0:
					if column_wise[val] == 1:
						return 0
					else:
						column_wise[val] = 1
		for i in range(1, 9, 3):
			for j in range(1, 9, 3):
				rowcol9_wise = [0 for _ in range(10)]
				for (dx, dy) in moves:
					val = mat[i + dx][j + dy]
					if val == 0:
						continue
					if rowcol9_wise[val] == 1:
						return 0
					else:
						rowcol9_wise[val] = 1
		return 1


class Solution:

	def isValid(self, mat):
		s = set()
		for i in range(9):
			for j in range(9):
				if mat[i][j] != 0:
					row = str(mat[i][j]) + 'row' + str(i)
					col = str(mat[i][j]) + 'col' + str(j)
					b = i // 3 * 3 + j // 3
					box = str(mat[i][j]) + 'box' + str(b)
					if row in s or col in s or box in s:
						return 0
					else:
						s.add(row)
						s.add(col)
						s.add(box)
		return 1


class Solution:

	def isValid(self, board):

		def isrowsafe(board, row):
			l = {}
			for i in range(9):
				if board[row][i] != 0:
					if board[row][i] not in l:
						l[board[row][i]] = 1
					else:
						return False
			else:
				return True

		def iscolsafe(board, col):
			l = {}
			for i in range(9):
				if board[i][col] != 0:
					if board[i][col] not in l:
						l[board[i][col]] = 1
					else:
						return False
			else:
				return True

		def isboxsafe(board, row, col):
			r = row - row % 3
			c = col - col % 3
			l = {}
			for i in range(3):
				for j in range(3):
					if board[i + r][j + c] != 0:
						if board[i + r][j + c] not in l:
							l[board[i + r][j + c]] = 1
						else:
							return False
			else:
				return True
		for i in range(9):
			if not isrowsafe(board, i):
				return 0
			if not iscolsafe(board, i):
				return 0
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				if not isboxsafe(board, i, j):
					return 0
		return 1


class Solution:

	def isRowValid(self, mat):
		for i in range(len(mat)):
			dict_ = {}
			for j in range(len(mat[i])):
				if mat[i][j] == 0:
					continue
				if mat[i][j] not in dict_:
					dict_[mat[i][j]] = 1
				else:
					return 0
		return 1

	def isColValid(self, mat):
		for i in range(len(mat)):
			dict_ = {}
			for j in range(len(mat[i])):
				if mat[j][i] == 0:
					continue
				if mat[j][i] not in dict_:
					dict_[mat[j][i]] = 1
				else:
					return 0
		return 1

	def is3by3Valid(self, mat):
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				dict_ = {}
				for jj in range(j, j + 3):
					for ii in range(i, i + 3):
						if mat[jj][ii] == 0:
							continue
						if mat[jj][ii] not in dict_:
							dict_[mat[jj][ii]] = 1
						else:
							return 0
		return 1

	def isValid(self, mat):
		if self.isRowValid(mat) == 0:
			return 0
		elif self.isColValid(mat) == 0:
			return 0
		elif self.is3by3Valid(mat) == 0:
			return 0
		else:
			return 1


class Solution:

	def isValid(self, mat):
		for i in range(len(mat)):
			row_set = set()
			for j in range(len(mat[0])):
				if not mat[i][j]:
					continue
				if mat[i][j] in row_set:
					return 0
				row_set.add(mat[i][j])
		for j in range(len(mat)):
			col_set = set()
			for i in range(len(mat[0])):
				if not mat[i][j]:
					continue
				if mat[i][j] in col_set:
					return 0
				col_set.add(mat[i][j])
		for i in range(0, 9, 3):
			for j in range(0, 9, 3):
				non_set = set()
				for k in range(i, i + 3):
					for l in range(j, j + 3):
						if not mat[k][l]:
							continue
						if mat[k][l] in non_set:
							return 0
						non_set.add(mat[k][l])
		return 1