Given an incomplete Sudoku configuration in terms of a 9 x 9  2-D square matrix (grid[][]), the task to find a solved Sudoku. For simplicity, you may assume that there will be only one unique solution.
A sudoku solution must satisfy all of the following rules:
	Each of the digits 1-9 must occur exactly once in each row.
	Each of the digits 1-9 must occur exactly once in each column.
	Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Sample Sudoku for you to get the logic for its solution:
Example 1:
Input:
grid[][] = 
[[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:
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
Your Task:
You need to complete the two functions:
SolveSudoku(): Takes a grid as its argument and returns true if a solution is possible and false if it is not.
printGrid(): Takes a grid as its argument and prints the 81 numbers of the solved Sudoku in a single line with space separation.
NOTE: Do not give a new line character after printing the grid. It has already been taken care of in the Driver Code.
Expected Time Complexity: O(9^{N*N}).
Expected Auxiliary Space: O(N*N).
Constraints:
0 ≤ grid[i][j] ≤ 9

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    

    #Function to find a solved Sudoku. 

    def SolveSudoku(self,grid):

        

    

    #Function to print grids of the Sudoku.    

    def printGrid(self,arr):

        

        # Your code here

Solutions:
class Solution:

	def isSafe(self, grid, r, c, val):
		for i in range(9):
			if grid[r][i] == val:
				return False
			if grid[i][c] == val:
				return False
			if grid[3 * (r // 3) + i // 3][3 * (c // 3) + i % 3] == val:
				return False
		return True

	def SolveSudoku(self, grid):
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					for val in range(1, 10):
						if self.isSafe(grid, i, j, val):
							grid[i][j] = val
							if self.SolveSudoku(grid):
								return True
							else:
								grid[i][j] = 0
					return False
		return True

	def printGrid(self, arr):
		for r in range(9):
			for c in range(9):
				print(arr[r][c], end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def check(grid, row, col, k):
			for i in range(9):
				if grid[row][i] == k:
					return False
				if grid[i][col] == k:
					return False
			startRow = row - row % 3
			startCol = col - col % 3
			for i in range(3):
				for j in range(3):
					if grid[i + startRow][j + startCol] == k:
						return False
			return True

		def solve():
			for i in range(9):
				for j in range(9):
					if grid[i][j] == 0:
						for k in range(1, 10):
							if check(grid, i, j, k):
								grid[i][j] = k
								if solve():
									return True
								else:
									grid[i][j] = 0
						return False
			return True
		solve()
		return True

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

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

	def SolveSudoku(self, grid):
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					for c in range(1, 10):
						if self.isvalid(grid, i, j, c):
							grid[i][j] = c
							if self.SolveSudoku(grid):
								return True
							else:
								grid[i][j] = 0
					return False
		return True

	def SolveSudoku1(self, grid):
		grow = len(grid)
		gcol = len(grid[0])

		def issafe(i, j, val, grid):
			for index in range(grow):
				if grid[index][j] == val:
					return False
				if grid[i][index] == val:
					return False
				duprow = 3 * (i // 3) + index // 3
				dupcol = 3 * (j // 3) + index // 3
				if grid[duprow][dupcol] == val:
					return False
			return True

		def bts(grid):
			for i in range(grow):
				for j in range(gcol):
					if grid[i][j] == 0:
						for val in range(1, grow + 1):
							if issafe(i, j, val, grid):
								grid[i][j] = val
								if bts(grid):
									return True
								grid[i][j] = 0
						return False
			return True
		return bts(grid)

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				print(arr[i][j], end=' ')


from collections import defaultdict
import sys
import copy

class Solution:

	def find_possiable(self, grid, i, j):
		return self.remove_impossiable(grid, i, j, {1, 2, 3, 4, 5, 6, 7, 8, 9})

	def remove_impossiable(self, grid, i, j, s):
		for k in range(9):
			s.discard(grid[i][k])
			s.discard(grid[k][j])
		for k in range(3):
			for l in range(3):
				p = grid[i // 3 * 3 + k][j // 3 * 3 + l]
				if isinstance(p, int):
					s.discard(p)
		return s

	def SolveSudoku(self, grid):
		while True:
			selected = False
			for i in range(9):
				for j in range(9):
					if grid[i][j] == 0:
						s = self.find_possiable(grid, i, j)
						if len(s) == 1:
							grid[i][j] = list(s)[0]
							selected = True
						else:
							grid[i][j] = s
						if len(s) == 0:
							print('xxxx')
			if not selected:
				break
		return self.solveSudoku1(grid)

	def solveSudoku1(self, grid):
		while True:
			updated = False
			set_map = defaultdict(list)
			for i in range(9):
				for j in range(9):
					if isinstance(grid[i][j], set):
						s = tuple(sorted(grid[i][j]))
						set_map['r', i, s].append((i, j))
						set_map['c', j, s].append((i, j))
						set_map['x', (i // 3, j // 3), s].append((i, j))
			for (k, v) in set_map.items():
				(t, g, s) = k
				if len(s) <= len(v):
					if t == 'r':
						for k in range(9):
							if (g, k) in v:
								continue
							if isinstance(grid[g][k], set):
								grid[g][k] -= set(s)
					if t == 'c':
						for k in range(9):
							if (k, g) in v:
								continue
							if isinstance(grid[k][g], set):
								grid[k][g] -= set(s)
					if t == 'x':
						(k, l) = g
						for i in range(3):
							for j in range(3):
								if not isinstance(grid[3 * k + i][3 * l + j], set):
									continue
								if (3 * k + i, 3 * l + j) in v:
									continue
								grid[3 * k + i][3 * l + j] -= set(s)
			while True:
				selected = False
				for i in range(9):
					for j in range(9):
						if isinstance(grid[i][j], set):
							s = self.remove_impossiable(grid, i, j, grid[i][j])
							if len(s) == 1:
								grid[i][j] = list(s)[0]
								selected = True
								updated = True
							else:
								grid[i][j] = s
				if not selected:
					break
			if not updated:
				break
		not_filled = []
		for i in range(9):
			for j in range(9):
				if isinstance(grid[i][j], set):
					not_filled.append((i, j))
		if len(not_filled) == 0:
			return True
		not_filled = sorted(not_filled, key=lambda x: len(grid[x[0]][x[1]]))
		(i, j) = not_filled[0]
		for v in grid[i][j]:
			gg = copy.deepcopy(grid)
			gg[i][j] = v
			if self.solveSudoku1(gg):
				for (k, l) in not_filled:
					grid[k][l] = gg[k][l]
				return True
		return False

	def to_s(self, a):
		if isinstance(a, set):
			return '0'
		return str(a)

	def printGrid(self, arr):
		sys.stdout.write(' '.join((' '.join((self.to_s(a) for a in arr[i])) for i in range(9))))


def canPlace(grid, i, j, num):
	for r in range(9):
		if grid[r][j] == num:
			return False
		if grid[i][r] == num:
			return False
	r3 = int(i / 3) * 3
	c3 = int(j / 3) * 3
	for r in range(3):
		for c in range(3):
			if grid[r3 + r][c3 + c] == num:
				return False
	return True

def solveMe(grid, i, j):
	if i == 9:
		return True
	if j == 9:
		return solveMe(grid, i + 1, 0)
	if grid[i][j] != 0:
		return solveMe(grid, i, j + 1)
	for num in range(1, 10):
		if canPlace(grid, i, j, num):
			grid[i][j] = num
			if solveMe(grid, i, j + 1):
				return True
			grid[i][j] = 0
	return False

class Solution:

	def SolveSudoku(self, grid):
		return solveMe(grid, 0, 0)

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(grid[i][j], end=' ')


class Solution:

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

	def SolveSudoku(self, grid):
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					for val in range(1, 10):
						if self.isValid(grid, i, j, val):
							grid[i][j] = val
							if self.SolveSudoku(grid):
								return True
							else:
								grid[i][j] = 0
					return False
		return True

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')

	def used_in_row(self, arr, row, num):
		for i in range(9):
			if arr[row][i] == num:
				return True
		return False

	def used_in_col(self, arr, col, num):
		for i in range(9):
			if arr[i][col] == num:
				return True
		return False

	def used_in_box(self, arr, row, col, num):
		for i in range(3):
			for j in range(3):
				if arr[i + row][j + col] == num:
					return True
		return False

	def check_location_is_safe(self, arr, row, col, num):
		return not self.used_in_row(arr, row, num) and (not self.used_in_col(arr, col, num)) and (not self.used_in_box(arr, row - row % 3, col - col % 3, num))

	def find_empty_location(self, arr, l):
		for row in range(9):
			for col in range(9):
				if arr[row][col] == 0:
					l[0] = row
					l[1] = col
					return True
		return False

	def SolveSudoku(self, grid):
		l = [0, 0]
		if not self.find_empty_location(grid, l):
			return True
		row = l[0]
		col = l[1]
		for num in range(1, 10):
			if self.check_location_is_safe(grid, row, col, num):
				grid[row][col] = num
				if self.SolveSudoku(grid):
					return True
				grid[row][col] = 0
		return False


class Solution:

	def SolveSudoku(self, grid):
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					break
			else:
				continue
			break
		else:
			return True
		for i in range(9):
			for j in range(9):
				if grid[i][j] != 0:
					continue
				for k in range(1, 10):
					if self.isValid(grid, i, j, k):
						grid[i][j] = k
						if self.SolveSudoku(grid):
							return True
						grid[i][j] = 0
				return False

	def isValid(self, grid, i, j, k):
		for p in range(9):
			if grid[i][p] == k or grid[p][j] == k:
				return False
		box_row = i // 3 * 3
		box_col = j // 3 * 3
		for pa in range(3):
			for pb in range(3):
				if grid[box_row + pa][box_col + pb] == k:
					return False
		return True

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(grid[i][j], end=' ')


from math import *

class Solution:

	def SolveSudoku(self, grid):
		self.N = len(grid)
		self.blockSize = int(sqrt(self.N))
		if self.SolveSudokuM(grid):
			return True
		else:
			return False

	def SolveSudokuM(self, grid):
		(row, col) = self.findNextEmpty(grid)
		if row is None:
			return True
		for guess in range(1, self.N + 1):
			if self.isSafe(grid, row, col, guess):
				grid[row][col] = guess
				if self.SolveSudokuM(grid):
					return True
				grid[row][col] = 0
		return False

	def isSafe(self, board, row, col, num):
		for iter in range(self.N):
			if board[iter][col] == num:
				return False
			if board[row][iter] == num:
				return False
		x = row - row % self.blockSize
		y = col - col % self.blockSize
		for i in range(self.blockSize):
			for j in range(self.blockSize):
				if board[x + i][y + j] == num:
					return False
		return True

	def findNextEmpty(self, grid):
		for i in range(len(grid)):
			for j in range(len(grid)):
				if grid[i][j] == 0:
					return (i, j)
		return (None, None)

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				print(arr[i][j], end=' ')


class Solution:
	ans = 0

	def issafe(self, grid, x, coord):
		for i in range(9):
			if grid[i][coord[1]] == x:
				return 0
		for i in range(9):
			if grid[coord[0]][i] == x:
				return 0
		l = coord[0] // 3
		r = coord[1] // 3
		for i in range(3 * l, 3 * (l + 1)):
			for j in range(3 * r, 3 * (r + 1)):
				if grid[i][j] == x:
					return 0
		return 1

	def gen(self, grid, space, i):
		if i == len(space):
			ans = 1
			return 1
		for k in range(1, 10):
			if self.issafe(grid, k, space[i]):
				grid[space[i][0]][space[i][1]] = k
				if self.gen(grid, space, i + 1):
					return 1
				grid[space[i][0]][space[i][1]] = 0

	def SolveSudoku(self, grid):
		space = []
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					space.append([i, j])
		return self.gen(grid, space, 0)

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

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

	def solve(self, grid):
		for row in range(9):
			for col in range(9):
				if grid[row][col] == 0:
					for val in range(1, 10):
						if self.is_safe(row, col, val, grid):
							grid[row][col] = val
							is_next_possible = self.solve(grid)
							if is_next_possible:
								return True
							grid[row][col] = 0
					return False
		return True

	def SolveSudoku(self, grid):
		return self.solve(grid)

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def fun1(r, c):
			for i in range(1, toggle + 1):
				if a[r][i] == 0 and b[c][i] == 0 and (cbox[hash1.index([r - r % 3, c - c % 3])][i] == 0):
					grid[r][c] = i
					a[r][i] = 1
					b[c][i] = 1
					cbox[hash1.index([r - r % 3, c - c % 3])][i] = 1
					if r == toggl1 and c == toggl1:
						return 1
					if c == toggl1:
						z1 = fun(r + 1, 0)
						if z1 == 1:
							return 1
						grid[r][c] = 0
						a[r][i] = 0
						b[c][i] = 0
						cbox[hash1.index([r - r % 3, c - c % 3])][i] = 0
					else:
						z1 = fun(r, c + 1)
						if z1 == 1:
							return 1
						grid[r][c] = 0
						a[r][i] = 0
						b[c][i] = 0
						cbox[hash1.index([r - r % 3, c - c % 3])][i] = 0
				elif i == toggle:
					return

		def fun(k1, k2):
			for i in range(k1, len(grid)):
				for j in range(k2, len(grid)):
					if grid[i][j] == 0:
						return fun1(i, j)
					elif i == toggl1 and j == toggl1:
						return 1
				if j == toggl1:
					k2 = 0
		a = []
		b = []
		cbox = []
		ans = []
		for i in range(9):
			a.append([0] * 10)
		for i in range(9):
			b.append([0] * 10)
		for i in range(9):
			cbox.append([0] * 10)
		toggle = 9
		toggl1 = 8
		hash1 = [[0, 0], [0, 3], [0, 6], [3, 0], [3, 3], [3, 6], [6, 0], [6, 3], [6, 6]]
		for i in range(toggle):
			for j in range(toggle):
				a[i][grid[i][j]] = 1
				b[j][grid[i][j]] = 1
				box = hash1.index([i - i % 3, j - j % 3])
				cbox[box][grid[i][j]] = 1
		fun(0, 0)
		s = ''
		for i in range(len(grid)):
			for j in range(len(grid)):
				s += str(grid[i][j]) + ' '
				if grid[i][j] == 0:
					print('cam')
					return 0
		return 1

	def printGrid(self, arr):
		s = ''
		for i in range(len(arr)):
			for j in range(len(arr)):
				print(arr[i][j], end=' ')


class Solution:

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

	def solve(self, board):
		for i in range(9):
			for j in range(9):
				if board[i][j] == 0:
					for temp in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
						if self.isValid(temp, board, i, j):
							board[i][j] = temp
							if self.solve(board) == True:
								return True
							else:
								board[i][j] = 0
					return False
		return True

	def SolveSudoku(self, grid):
		if self.solve(grid):
			return 1
		return 0

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def check(self, grid, r, c, ch):
		for i in range(9):
			if grid[r][i] == ch:
				return False
			if grid[i][c] == ch:
				return False
			if grid[int(3 * (r // 3) + i // 3)][int(3 * (c // 3) + i % 3)] == ch:
				return False
		return True

	def solve(self, grid):
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					for ch in range(1, 10):
						if self.check(grid, i, j, ch):
							grid[i][j] = ch
							if self.solve(grid):
								return True
							else:
								grid[i][j] = 0
					return False
		return True

	def SolveSudoku(self, grid):
		return self.solve(grid)

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		N = 9

		def isSafe(grid, row, col, num):
			for x in range(9):
				if grid[row][x] == num:
					return False
			for x in range(9):
				if grid[x][col] == num:
					return False
			startRow = row - row % 3
			startCol = col - col % 3
			for i in range(3):
				for j in range(3):
					if grid[i + startRow][j + startCol] == num:
						return False
			return True

		def solvesudoku(grid, row, col):
			if row == N - 1 and col == N:
				return True
			if col == N:
				row += 1
				col = 0
			if grid[row][col] > 0:
				return solvesudoku(grid, row, col + 1)
			for num in range(1, N + 1, 1):
				if isSafe(grid, row, col, num):
					grid[row][col] = num
					if solvesudoku(grid, row, col + 1) == True:
						return True
				grid[row][col] = 0
			return False
		return solvesudoku(grid, 0, 0)

	def printGrid(self, grid):
		for i in range(9):
			for j in range(9):
				print(grid[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def function1(i, j, grid, k):
			m = i
			n = j
			s = 'F'
			while m < 9:
				if grid[m][j] == k:
					return False
				m = m + 1
			m = i
			while m >= 0:
				if grid[m][j] == k:
					return False
				m = m - 1
			while n < 9:
				if grid[i][n] == k:
					return False
				n = n + 1
			n = j
			while n >= 0:
				if grid[i][n] == k:
					return False
				n = n - 1
			if i < 3:
				v = 0
				b = 3
			elif i < 6:
				v = 3
				b = 6
			elif i < 9:
				v = 6
				b = 9
			if j < 3:
				s = 0
				l = 3
			elif j < 6:
				s = 3
				l = 6
			elif j < 9:
				s = 6
				l = 9
			m = i
			n = j
			for r in range(v, b):
				for v in range(s, l):
					if grid[r][v] == k:
						return False
			return True

		def function(grid):
			for i in range(9):
				for j in range(9):
					s = 'F'
					if grid[i][j] == 0:
						for k in range(1, 10):
							if function1(i, j, grid, k):
								grid[i][j] = k
								if function(grid):
									return True
								else:
									grid[i][j] = 0
						return False
			return True
		return function(grid)

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')

	def used_in_box(self, grid, box_start_row, box_start_col, num):
		for row in range(3):
			for col in range(3):
				if grid[row + box_start_row][col + box_start_col] == num:
					return True
		return False

	def is_safe(self, grid, row, col, num):
		for c in range(9):
			if grid[row][c] == num:
				return False
		for r in range(9):
			if grid[r][col] == num:
				return False
		box_start_row = row - row % 3
		box_start_col = col - col % 3
		flag = self.used_in_box(grid, box_start_row, box_start_col, num)
		if not flag:
			return True
		return False

	def func(self, row, col, n, grid):
		flag = False
		for a in range(n):
			for b in range(n):
				if grid[a][b] == 0:
					row = a
					col = b
					flag = True
					break
			if flag:
				break
		if not flag:
			return True
		for num in range(1, n + 1):
			if self.is_safe(grid, row, col, num) and grid[row][col] == 0:
				grid[row][col] = num
				if self.func(row, col, n, grid):
					return True
				grid[row][col] = 0
		return False

	def SolveSudoku(self, grid):
		n = len(grid[0])
		row = 0
		col = 0
		if self.func(row, col, n, grid):
			return True
		return False


class Solution:

	def SolveSudoku(self, grid):
		return solve_sudoku(grid)

	def printGrid(self, arr):
		print_sudoku(arr)

def solve_sudoku_helper(grid: [[]], row: int, col: int):
	if row == 9:
		return True
	if col == 9:
		return solve_sudoku_helper(grid, row + 1, 0)
	if grid[row][col] != 0:
		return solve_sudoku_helper(grid, row, col + 1)
	for i in range(1, 10):
		if is_safe(grid, row, col, i):
			grid[row][col] = i
			if solve_sudoku_helper(grid, row, col + 1):
				return True
		grid[row][col] = 0

def is_safe(grid, row: int, col: int, number: int):
	for i in range(0, 9):
		if grid[row][i] == number:
			return False
	for i in range(0, 9):
		if grid[i][col] == number:
			return False
	start_row = row - row % 3
	start_col = col - col % 3
	for i in range(start_row, start_row + 3):
		for j in range(start_col, start_col + 3):
			if grid[i][j] == number:
				return False
	return True

def solve_sudoku(grid: [[]]):
	return solve_sudoku_helper(grid, 0, 0)

def print_sudoku(grid: [[]]):
	solve_sudoku(grid)
	for i in range(0, 9):
		for j in range(0, 9):
			print(grid[i][j], end=' ')


class Solution:

	def __init__(self):
		self.ds = []

	def SolveSudoku(self, grid):
		(rows, cols) = (len(grid), len(grid[0]))

		def isvalid(num, grid, row, col):
			for i in range(rows):
				if grid[i][col] == num:
					return False
				if grid[row][i] == num:
					return False
				if grid[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == num:
					return False
			return True

		def rec(r, c):
			for i in range(rows):
				for j in range(cols):
					if grid[i][j] == 0:
						for num in range(1, 10):
							if isvalid(num, grid, i, j):
								grid[i][j] = num
								if rec(i, j):
									return True
								else:
									grid[i][j] = 0
						return False
			return True
		return rec(0, 0)

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		n = len(grid)
		m = len(grid[0])
		for i in range(n):
			for j in range(m):
				if grid[i][j] == 0:
					for c in range(1, 10):
						if self.checkifokay(i, j, c, n, grid):
							grid[i][j] = c
							if self.SolveSudoku(grid):
								return True
							grid[i][j] = 0
					return False
		return True

	def checkifokay(self, row, col, c, n, grid):
		for k in range(0, 9):
			if grid[row][k] == c:
				return False
			if grid[k][col] == c:
				return False
			x = 3 * (row // 3) + k // 3
			y = 3 * (col // 3) + k % 3
			if grid[x][y] == c:
				return False
		return True

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[i])):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 0:
					for c in range(1, 10):
						if self.is_valid(grid, i, j, c):
							grid[i][j] = c
							if self.SolveSudoku(grid):
								return True
							else:
								grid[i][j] = 0
					return False
		return True
		self.printGrid(grid)

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

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				print(arr[i][j], end=' ')


class Solution:

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

	def helper(self, board):
		for i in range(9):
			for j in range(9):
				if board[i][j] == 0:
					for k in range(1, 10):
						if self.isValid(board, k, i, j):
							board[i][j] = k
							if self.helper(board) == True:
								return True
							board[i][j] = 0
					return False
		return True

	def SolveSudoku(self, grid):
		self.helper(grid)
		return True

	def printGrid(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')


class Solution:

	def solve(self, grid, row, col, cell, i, j):
		if j == 9:
			if i == 8:
				return True
			else:
				return self.solve(grid, row, col, cell, i + 1, 0)
		if grid[i][j]:
			return self.solve(grid, row, col, cell, i, j + 1)
		else:
			for k in range(1, 9 + 1):
				if k not in row[i] and k not in col[j] and (k not in cell[i // 3][j // 3]):
					grid[i][j] = k
					row[i].add(k)
					col[j].add(k)
					cell[i // 3][j // 3].add(k)
					if self.solve(grid, row, col, cell, i, j + 1):
						return True
					grid[i][j] = 0
					row[i].remove(k)
					col[j].remove(k)
					cell[i // 3][j // 3].remove(k)
		return False

	def SolveSudoku(self, grid):
		row = [set() for i in range(9)]
		col = [set() for j in range(9)]
		cell = [[set() for i in range(3)] for j in range(3)]
		for i in range(9):
			for j in range(9):
				if grid[i][j]:
					row[i].add(grid[i][j])
					col[j].add(grid[i][j])
					cell[i // 3][j // 3].add(grid[i][j])
		return self.solve(grid, row, col, cell, 0, 0)

	def printGrid(self, arr):
		for row in arr:
			print(*row, end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def is_safe(grid, num, i, j):
			for index in range(9):
				if grid[i][index] == num:
					return False
				if grid[index][j] == num:
					return False
			sub_row = i // 3 * 3
			sub_col = j // 3 * 3
			for s_row in range(sub_row, sub_row + 3):
				for s_col in range(sub_col, sub_col + 3):
					if grid[s_row][s_col] == num:
						return False
			return True

		def traverse(grid, i, j):
			if i == 9:
				return True
			if j == 9:
				return traverse(grid, i + 1, 0)
			if grid[i][j] != 0:
				return traverse(grid, i, j + 1)
			for num in range(1, 10):
				if is_safe(grid, num, i, j):
					grid[i][j] = num
					if traverse(grid, i, j + 1) == True:
						return True
					else:
						grid[i][j] = 0
			return False
		return traverse(grid, 0, 0)

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		empty_cell = self.find_empty_cell(grid)
		if empty_cell == -1:
			return True
		for k in range(1, 10):
			(i, j) = empty_cell
			if self.is_safe(grid, i, j, k):
				grid[i][j] = k
				if self.SolveSudoku(grid):
					return True
				grid[i][j] = 0
		return False

	def find_empty_cell(self, grid):
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					return [i, j]
		return -1

	def is_safe(self, grid, i, j, k):
		for z in range(9):
			if grid[i][z] == k or grid[z][j] == k:
				return False
		istart = i - i % 3
		jstart = j - j % 3
		for ii in range(istart, istart + 3):
			for jj in range(jstart, jstart + 3):
				if grid[ii][jj] == k:
					return False
		return True

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		return self.solveUtil(grid, 0, 0)

	def solveUtil(self, grid, ii, jj):
		found = False
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					found = True
					break
			if found:
				break
		if not found:
			return True
		for k in range(1, 10):
			if self.isSafe(grid, i, j, k):
				grid[i][j] = k
				if self.solveUtil(grid, i, j):
					return True
				grid[i][j] = 0
		return False

	def isSafe(self, grid, i, j, k):
		for z in range(9):
			if grid[i][z] == k or grid[z][j] == k:
				return False
		istart = i - i % 3
		jstart = j - j % 3
		for ii in range(istart, istart + 3):
			for jj in range(jstart, jstart + 3):
				if grid[ii][jj] == k:
					return False
		return True

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def isValid(self, row, col, grid, c):
		for i in range(len(grid)):
			if grid[row][i] == c:
				return False
			if grid[i][col] == c:
				return False
			if grid[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == c:
				return False

	def SolveSudoku(self, grid):
		for row in range(len(grid)):
			for col in range(len(grid[0])):
				if grid[row][col] == 0:
					for c in range(1, len(grid) + 1):
						if self.isValid(row, col, grid, c) == None:
							grid[row][col] = c
							if self.SolveSudoku(grid) == True:
								return True
							else:
								grid[row][col] = 0
					return False
		return True

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def issafe(grid, row, col, val):
			for i in range(9):
				if grid[row][i] == val:
					return False
				if grid[i][col] == val:
					return False
				if grid[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == val:
					return False
			return True
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 0:
					for k in range(1, len(grid) + 1):
						if issafe(grid, i, j, k):
							grid[i][j] = k
							if self.SolveSudoku(grid):
								return True
							grid[i][j] = 0
					return False
		return True

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr)):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def helper(grid):
			for i in range(9):
				for j in range(9):
					if grid[i][j] == 0:
						for inx in range(1, 10):
							if self.isvalid(i, j, grid, inx):
								grid[i][j] = inx
								ans = helper(grid)
								if ans:
									return True
								else:
									grid[i][j] = 0
						return False
			return True
		return helper(grid)

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

	def printGrid(self, arr):
		for ele in arr:
			for i in range(9):
				print(ele[i], end=' ')
		return


class Solution:

	def SolveSudoku(self, grid):

		def checkvalid(row, col, val):
			for i in range(9):
				if val == grid[row][i]:
					return False
				if val == grid[i][col]:
					return False
			r = row // 3
			c = col // 3
			for i in range(3 * r, 3 * r + 3):
				for j in range(3 * c, 3 * c + 3):
					if grid[i][j] == val:
						return False
			return True

		def findsol(i, j):
			if i == 8 and j >= 9:
				return True
			if i < 9 and j >= 9:
				return findsol(i + 1, 0)
			if i >= 9 or j >= 9:
				return False
			if grid[i][j] != 0:
				return findsol(i, j + 1)
			else:
				for x in range(1, 10):
					if checkvalid(i, j, x):
						grid[i][j] = x
						if findsol(i, j + 1) == True:
							return True
						grid[i][j] = 0
			return False
		return findsol(0, 0)

	def printGrid(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')


class Solution:

	def SolveSudoku(self, grid):
		n = len(grid[0])
		for row in range(n):
			for col in range(n):
				if grid[row][col] == 0:
					for val in range(1, 10):
						if self.isSafe(grid, row, col, val, n):
							grid[row][col] = val
							next_sol = self.SolveSudoku(grid)
							if next_sol:
								return True
							else:
								grid[row][col] = 0
					return False
		return True

	def isSafe(self, grid, row, col, val, n):
		for i in range(n):
			if grid[row][i] == val or grid[i][col] == val:
				return False
			if grid[3 * (row // 3) + i // 3][3 * (col // 3) + i % 3] == val:
				return False
		return True

	def printGrid(self, arr):
		for i in range(0, 9):
			for j in range(0, 9):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		tablePossibles = []
		sol = []

		def ad(lista):
			tmp = []
			for i in range(0, 9):
				vec = []
				for j in range(0, 9):
					vec.append(lista[i][j])
				tmp.append(vec)
			sol.append(tmp)

		def solve(grid):
			find = find_empty()
			if not find:
				for i in range(0, 9):
					for j in range(0, 9):
						if grid[i][j] == 0:
							return False
				ad(grid)
				return True
			else:
				(row, col) = find
			nums = []
			for k in tablePossibles[row][col]:
				nums.append(k)
			if len(nums) == 0:
				return False
			for i in nums:
				grid[row][col] = i
				temps = []
				for e in range(0, 9):
					if i in tablePossibles[row][e]:
						temps.append([row, e])
						tablePossibles[row][e].remove(i)
				for e in range(0, 9):
					if i in tablePossibles[e][col]:
						temps.append([e, col])
						tablePossibles[e][col].remove(i)
				box_x = col // 3
				box_y = row // 3
				for m in range(box_y * 3, box_y * 3 + 3):
					for j in range(box_x * 3, box_x * 3 + 3):
						if i in tablePossibles[m][j]:
							temps.append([m, j])
							tablePossibles[m][j].remove(i)
				if solve(grid):
					return True
				for j in temps:
					tablePossibles[j[0]][j[1]].insert(0, i)
				grid[row][col] = 0
			return False

		def getPossibles(grid, tablePossibles):
			for i in range(0, 9):
				vec = []
				for j in range(0, 9):
					if grid[i][j] == 0:
						vec.append(getNumPossibles(grid, i, j))
					else:
						vec.append([])
				tablePossibles.append(vec)

		def getNumPossibles(grid, y, x):
			nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
			for i in range(0, 9):
				el = grid[y][i]
				if el != 0 and el in nums:
					nums.remove(el)
			for i in range(0, 9):
				el = grid[i][x]
				if el != 0 and el in nums:
					nums.remove(el)
			box_x = x // 3
			box_y = y // 3
			for i in range(box_y * 3, box_y * 3 + 3):
				for j in range(box_x * 3, box_x * 3 + 3):
					el = grid[i][j]
					if el != 0 and el in nums:
						nums.remove(el)
			return nums

		def find_empty():
			min = [10, 0, 0]
			for i in range(0, 9):
				for j in range(0, 9):
					leng = len(tablePossibles[i][j])
					if leng == 0 or grid[i][j] != 0:
						continue
					if leng < min[0] and leng > 0:
						min = [leng, i, j]
			if min[0] == 10:
				return None
			return (min[1], min[2])
		getPossibles(grid, tablePossibles)
		solve(grid)
		return True

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


def valid(grid, r, c, no):
	if no in grid[r]:
		return False
	if any((grid[i][c] == no for i in range(9))):
		return False
	(br, bc) = (3 * (r // 3), 3 * (c // 3))
	for i in range(br, br + 3):
		for j in range(bc, bc + 3):
			if grid[i][j] == no:
				return False
	return True

def func(pos, board):
	(r, c) = pos
	while board[r][c] != 0:
		c += 1
		if c == 9:
			c = 0
			r += 1
		if r == 9:
			return True
	for i in range(1, 10):
		if valid(board, r, c, i):
			board[r][c] = i
			if func((r, c), board):
				return True
	board[r][c] = 0
	return False

class Solution:

	def SolveSudoku(self, grid):
		return func((0, 0), grid)

	def printGrid(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')


class Solution:

	def solving(self, grid, row, col):
		if row == 8 and col == 9:
			return True
		if col == 9:
			col = 0
			row += 1
		if grid[row][col] > 0:
			return self.solving(grid, row, col + 1)
		for i in range(1, 10, 1):
			if self.isvalidnumber(grid, i, row, col):
				grid[row][col] = i
				if self.solving(grid, row, col + 1):
					return True
			grid[row][col] = 0
		return False

	def isvalidnumber(self, grid, n, row, col):
		for i in range(9):
			if grid[row][i] == n:
				return False
		for i in range(9):
			if grid[i][col] == n:
				return False
		startRow = row - row % 3
		startCol = col - col % 3
		for i in range(3):
			for j in range(3):
				if grid[i + startRow][j + startCol] == n:
					return False
		return True

	def SolveSudoku(self, grid):
		self.solving(grid, 0, 0)
		return True

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(grid[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		n = len(grid[0])

		def isSafe(r, c, v):
			for i in range(n):
				if grid[i][c] == v:
					return False
				if grid[r][i] == v:
					return False
				if grid[3 * (r // 3) + i // 3][3 * (c // 3) + i % 3] == v:
					return False
			return True
		for r in range(n):
			for c in range(n):
				if grid[r][c] == 0:
					for v in range(1, 10):
						if isSafe(r, c, v):
							grid[r][c] = v
							if self.SolveSudoku(grid):
								return True
							else:
								grid[r][c] = 0
					return False
		return True

	def printGrid(self, arr):
		n = len(arr)
		for i in range(n):
			for j in range(n):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def isSafe(i, j, num, grid):
			for k in range(0, 9):
				if grid[i][k] == num or grid[k][j] == num:
					return False
			for x in range(i // 3 * 3, i // 3 * 3 + 3):
				for y in range(j // 3 * 3, j // 3 * 3 + 3):
					if grid[x][y] == num:
						return False
			return True

		def sol(i, j, grid):
			for x in range(i, 9):
				for y in range(j, 9):
					if grid[x][y] == 0:
						for k in range(1, 10):
							if isSafe(x, y, k, grid):
								grid[x][y] = k
								if sol(x, y, grid):
									return True
								grid[x][y] = 0
						return False
				j = 0
			return True
		return sol(0, 0, grid)

	def printGrid(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def is_placable(self, i, j, k):
		if self.grid[i][j] == 0:
			for ii in range(9):
				if self.grid[i][ii] == k:
					return False
			for ii in range(9):
				if self.grid[ii][j] == k:
					return False
			nj = int(j / 3) * 3
			ni = int(i / 3) * 3
			for ii in range(3):
				for jj in range(3):
					if self.grid[ni + ii][nj + jj] == k:
						return False
			return True
		else:
			return False

	def solve(self):
		for i in range(9):
			for j in range(9):
				if self.grid[i][j] == 0:
					for x in range(9):
						if self.is_placable(i, j, x + 1):
							self.grid[i][j] = x + 1
							if self.solve():
								return True
							self.grid[i][j] = 0
					return False
		return True

	def SolveSudoku(self, grid):
		self.grid = grid
		return self.solve()

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr)):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		for i in range(9):
			for j in range(9):
				if grid[i][j] == 0:
					for num in range(1, 10):
						if self.IsValid(grid, i, j, num):
							grid[i][j] = num
							if self.SolveSudoku(grid) == True:
								return True
							else:
								grid[i][j] = 0
					return False
		return True

	def IsValid(self, grid, row, col, num):
		for i in range(0, 9):
			if grid[row][i] == num:
				return False
			if grid[i][col] == num:
				return False
		for i in range(3):
			for j in range(3):
				if grid[int(row - row % 3 + i)][col - col % 3 + j] == num:
					return False
		return True

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				print(arr[i][j], end=' ')


class Solution:

	def find_empty_cell(self, board):
		for row in range(9):
			for col in range(9):
				if board[row][col] == 0:
					return (row, col)
		return None

	def SolveSudoku(self, board):
		empty_cell = self.find_empty_cell(board)
		if not empty_cell:
			return True
		(row, col) = empty_cell
		for num in range(1, 10):
			if self.is_valid(board, num, row, col):
				board[row][col] = num
				if self.SolveSudoku(board):
					return True
				board[row][col] = 0
		return False

	def is_valid(self, board, num, row, col):
		for i in range(9):
			if board[row][i] == num:
				return False
		for j in range(9):
			if board[j][col] == num:
				return False
		box_row = row // 3 * 3
		box_col = col // 3 * 3
		for i in range(3):
			for j in range(3):
				if board[box_row + i][box_col + j] == num:
					return False
		return True

	def printGrid(self, arr):
		for row in arr:
			for col in row:
				print(col, end=' ')


class Solution:

	def SolveSudoku(self, grid):
		ans = self.solve(grid)
		return ans

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')

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

	def solve(self, grid):
		for row in range(9):
			for col in range(9):
				if grid[row][col] == 0:
					for val in range(1, 10):
						if self.isSafe(row, col, grid, val):
							grid[row][col] = val
							is_SolutionExist = self.solve(grid)
							if is_SolutionExist:
								return True
							else:
								grid[row][col] = 0
					return False
		return True


class Solution:

	def issafe(self, arr, number, row, col):
		for i in range(len(arr)):
			if arr[row][i] == number:
				return False
			if arr[i][col] == number:
				return False
		sc = col - col % 3
		sr = row - row % 3
		for i in range(3):
			for j in range(3):
				if arr[sr + i][sc + j] == number:
					return False
		return True

	def helper(self, grid, row, col):
		if row == 8 and col == 9:
			return True
		nrow = 0
		ncol = 0
		if col == len(grid):
			row = row + 1
			col = 0
		if grid[row][col] != 0:
			if self.helper(grid, row, col + 1):
				return True
		else:
			for i in range(1, 10):
				if self.issafe(grid, i, row, col):
					grid[row][col] = i
					if self.helper(grid, row, col + 1):
						return True
				grid[row][col] = 0
		return False

	def SolveSudoku(self, grid):
		if self.helper(grid, 0, 0):
			return True
		else:
			return False

	def printGrid(self, arr):
		for i in range(len(arr)):
			for j in range(len(arr[0])):
				print(grid[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):
		ans = []
		new = [[0] * 9 for i in range(9)]

		def isSafe(grid, row, col, i):
			for k in range(0, 9):
				if grid[row][k] == i:
					return False
			for k in range(0, 9):
				if grid[k][col] == i:
					return False
			rowe = row // 3
			cole = col // 3
			(rowe, cole) = (rowe * 3, cole * 3)
			for a in range(rowe, rowe + 3):
				for b in range(cole, cole + 3):
					if grid[a][b] == i:
						return False
			return True

		def istrue(grid):
			for i in range(9):
				for j in range(9):
					if grid[i][j] == 0:
						return False
			return True

		def backtrack(grid, row, col):
			if row > 8:
				if istrue(grid):
					ans.append(True)
					for i in range(9):
						for j in range(9):
							new[i][j] = grid[i][j]
				return
			if grid[row][col] == 0:
				for i in range(1, 10):
					if isSafe(grid, row, col, i):
						grid[row][col] = i
						if col == 8:
							backtrack(grid, row + 1, 0)
						else:
							backtrack(grid, row, col + 1)
						grid[row][col] = 0
			elif col == 8:
				backtrack(grid, row + 1, 0)
			else:
				backtrack(grid, row, col + 1)
		backtrack(grid, 0, 0)
		for i in range(9):
			for j in range(9):
				grid[i][j] = new[i][j]
		if len(ans):
			return True
		return False

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')


class Solution:

	def SolveSudoku(self, grid):

		def valid(i, j, n, r):
			for x in range(9):
				if grid[i][x] == r or grid[x][j] == r:
					return False
			sx = i // 3 * 3
			sy = j // 3 * 3
			for x in range(sx, sx + 3):
				for y in range(sy, sy + 3):
					if grid[x][y] == r:
						return False
			return True

		def solve(i, j, n):
			if i == n:
				return True
			if j == n:
				return solve(i + 1, 0, n)
			if grid[i][j] != 0:
				return solve(i, j + 1, n)
			for r in range(1, 10):
				if valid(i, j, n, r):
					grid[i][j] = r
					success = solve(i, j + 1, n)
					if success:
						return True
			grid[i][j] = 0
			return False
		return solve(0, 0, 9)

	def printGrid(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')


class Solution:

	def isSafe(self, row, col, val, board):
		for i in range(9):
			if board[row][i] == val:
				return 0
			if board[i][col] == val:
				return 0
			x = 3 * (row // 3) + i // 3
			y = 3 * (col // 3) + i % 3
			if board[x][y] == val:
				return 0
		return 1

	def solve(self, board):
		for row in range(9):
			for col in range(9):
				if board[row][col] == 0:
					for val in range(1, 10):
						if self.isSafe(row, col, val, board):
							board[row][col] = val
							nxtVal = self.solve(board)
							if nxtVal:
								return 1
							else:
								board[row][col] = 0
					return 0
		return 1

	def SolveSudoku(self, grid):
		flag = self.solve(grid)
		return flag

	def printGrid(self, arr):
		for i in range(9):
			for j in range(9):
				print(arr[i][j], end=' ')