

from __future__ import annotations

lowerCamelCase           =					list[list[int]]

# assigning initial values to the grid
lowerCamelCase           =					[
    [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
lowerCamelCase           =					[
    [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__				(			_A      : Matrix	,      _A      : int	,      _A      : int	,      _A      : int							):





  '''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__				(			_A      : Matrix							):





  '''simple docstring'''







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




def 			UpperCAmelCase__				(			_A      : Matrix							):





  '''simple docstring'''







  if location := find_empty_location(_A							):
    a__,      a__  =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__  =digit

      if sudoku(_A							) is not None:
        return grid

      a__  =0

  return None




def 			UpperCAmelCase__				(			_A      : Matrix							):





  '''simple docstring'''







  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:''')
              lowerCamelCase           =					sudoku(example_grid)
              if solution is not None:
                     print_solution(solution)
              else:
                     print('''Cannot find a solution.''')



def 			UpperCAmelCase__				(			):





  '''simple docstring'''







  return [
      a * b * (10_00 - a - b)
      for a in range(1	,      9_99							)
      for b in range(_A	,      9_99							)
      if (a * a + b * b == (10_00 - a - b) ** 2)
  ][0]


if __name__ == "__main__":
       print(f"""{solution() = }""")
