


"""simple docstring"""







from __future__ import annotations

a__    :							int            =					list[list[int]]

# assigning initial values to the grid
a__    :							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
a__    :							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        UpperCAmelCase__	(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       ):




					'''simple docstring'''


					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        UpperCAmelCase__	(lowerCAmelCase_       ):




					'''simple docstring'''


					for i in range(9       ):
										for j in range(9       ):
															if grid[i][j] == 0:
																				return i, j
					return None




def        UpperCAmelCase__	(lowerCAmelCase_       ):




					'''simple docstring'''


					if location := find_empty_location(lowerCAmelCase_       ):
										__SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE						       =    location
					else:
										# If the location is ``None``, then the grid is solved.
										return grid

					for digit in range(1  ,						10       ):
										if is_safe(lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_  ,						lowerCAmelCase_       ):
															__SCREAMING_SNAKE_CASE						       =    digit

															if sudoku(lowerCAmelCase_       ) is not None:
																				return grid

															__SCREAMING_SNAKE_CASE						       =    0

					return None




def        UpperCAmelCase__	(lowerCAmelCase_       ):




					'''simple docstring'''


					for row in grid:
										for cell in row:
															print(lowerCAmelCase_  ,						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''' + '''=''' * 2_0)
				print_solution(example_grid)
				print('''\nExample grid solution:''')
				a__    :							List[Any]            =					sudoku(example_grid)
				if solution is not None:
						print_solution(solution)
				else:
						print('''Cannot find a solution.''')




"""simple docstring"""







from __future__ import annotations




def        UpperCAmelCase__	(lowerCAmelCase_       ):




					'''simple docstring'''


					if not nums:
										return 0
					__SCREAMING_SNAKE_CASE						       =    nums[0]
					__SCREAMING_SNAKE_CASE						       =    0
					for num in nums[1:]:
										__SCREAMING_SNAKE_CASE       ,  __SCREAMING_SNAKE_CASE						       =    (
										    max_excluding + num,
										    max(lowerCAmelCase_  ,						lowerCAmelCase_       ),
										)
					return max(lowerCAmelCase_  ,						lowerCAmelCase_       )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
