

from __future__ import annotations

UpperCAmelCase_							:					Any		 =   list[list[int]]

# assigning initial values to the grid
UpperCAmelCase_							:					Matrix		 =   [
    [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],
]

# a grid with no solution
UpperCAmelCase_							:					Matrix		 =   [
    [5, 0, 6, 5, 0, 8, 4, 0, 3],
    [5, 2, 0, 0, 0, 0, 0, 0, 2],
    [1, 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],
]
def 							__SCREAMING_SNAKE_CASE     (   a__    :   Matrix			,a__    :   int			,a__    :   int			,a__    :   int       )					->				bool:
	for i in range(9       ):
		if grid[row][i] == n or grid[i][column] == n:
			return False

	for i in range(3       ):
		for j in range(3       ):
			if grid[(row - row % 3) + i][(column - column % 3) + j] == n:
				return False

	return True
def 							__SCREAMING_SNAKE_CASE     (   a__    :   Matrix       )					->				tuple[int, int] | None:
	for i in range(9       ):
		for j in range(9       ):
			if grid[i][j] == 0:
				return i, j
	return None
def 							__SCREAMING_SNAKE_CASE     (   a__    :   Matrix       )					->				Matrix | None:
	if location := find_empty_location(a__       ):
		__A    ,				__A :			Optional[int]		    =			location
	else:
		# If the location is ``None``, then the grid is solved.
		return grid

	for digit in range(1			,10       ):
		if is_safe(a__			,a__			,a__			,a__       ):
			__A :			List[str]		    =			digit

			if sudoku(a__       ) is not None:
				return grid

			__A :			Tuple		    =			0

	return None
def 							__SCREAMING_SNAKE_CASE     (   a__    :   Matrix       )					->				None:
	for row in grid:
		for cell in row:
			print(a__			,end=""" """       )
		print()


if __name__ == "__main__":
			# make a copy of grid so that you can compare with the unmodified grid
			for example_grid in (initial_grid, no_solution):
						print('''\nExample grid:\n''' + '''=''' * 20)
						print_solution(example_grid)
						print('''\nExample grid solution:''')
						UpperCAmelCase_							:					Optional[int]		 =   sudoku(example_grid)
						if solution is not None:
									print_solution(solution)
						else:
									print('''Cannot find a solution.''')








from __future__ import annotations
def 							__SCREAMING_SNAKE_CASE     (   a__    :   List[str]			,a__    :   Dict			,a__    :   Union[str, Any]			,a__    :   Any       )					->				Optional[int]:  # noqa: E741
	while r - l > 1:
		__A :			Any		    =			(l + r) // 2
		if v[m] >= key:
			__A :			Optional[int]		    =			m
		else:
			__A :			List[Any]		    =			m  # noqa: E741
	return r
def 							__SCREAMING_SNAKE_CASE     (   a__    :   list[int]       )					->				int:
	if len(a__       ) == 0:
		return 0

	__A :			str		    =			[0] * len(a__       )
	__A :			List[str]		    =			1

	__A :			List[Any]		    =			v[0]

	for i in range(1			,len(a__       )       ):
		if v[i] < tail[0]:
			__A :			int		    =			v[i]
		elif v[i] > tail[length - 1]:
			__A :			Union[str, Any]		    =			v[i]
			length += 1
		else:
			__A :			Any		    =			v[i]

	return length


if __name__ == "__main__":
			import doctest

			doctest.testmod()





