
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					(    __lowerCamelCase     : Matrix				,					__lowerCamelCase     : int				,					__lowerCamelCase     : int				,					__lowerCamelCase     : int    ):
       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     : Matrix    ):
       for i in range(9    ):
              for j in range(9    ):
                     if grid[i][j] == 0:
                            return i, j
       return None


def 			UpperCamelCase					(    __lowerCamelCase     : Matrix    ):
       if location := find_empty_location(__lowerCamelCase    ):
              snake_case				,					snake_case       :   Union[str, Any]							=      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    ):
                     snake_case       :   List[Any]							=      digit

                     if sudoku(__lowerCamelCase    ) is not None:
                            return grid

                     snake_case       :   Union[str, Any]							=      0

       return None


def 			UpperCamelCase					(    __lowerCamelCase     : Matrix    ):
       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""" + """=""" * 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.""")









'''simple docstring'''




def 	a_					( lowerCamelCase	:     Optional[Any]				):
   return [
       {
           0: [1, 2],
           1: [0, 2],
           2: [0, 1, 3, 5],
           3: [2, 4],
           4: [3],
           5: [2, 6, 8],
           6: [5, 7],
           7: [6, 8],
           8: [5, 7],
       },
       {
           0: [6],
           1: [9],
           2: [4, 5],
           3: [4],
           4: [2, 3],
           5: [2],
           6: [0, 7],
           7: [6],
           8: [],
           9: [1],
       },
       {
           0: [4],
           1: [6],
           2: [],
           3: [5, 6, 7],
           4: [0, 6],
           5: [3, 8, 9],
           6: [1, 3, 4, 7],
           7: [3, 6, 8, 9],
           8: [5, 7],
           9: [5, 7],
       },
       {
           0: [1, 3],
           1: [0, 2, 4],
           2: [1, 3, 4],
           3: [0, 2, 4],
           4: [1, 2, 3],
       },
   ][index]





def 	a_					( lowerCamelCase	:     dict[int, list[int]]				):
   lowerCAmelCase     =			0
   lowerCAmelCase     =			len(lowerCamelCase				)  # No of vertices in graph
   lowerCAmelCase     =			[0] * n
   lowerCAmelCase     =			[False] * n

   def dfs(lowerCamelCase	:     Tuple	, lowerCamelCase	:     str	, lowerCamelCase	:     Dict	, lowerCamelCase	:     str				):
      lowerCAmelCase     =			True
      lowerCAmelCase     =			id_
      id_ += 1
      for to in graph[at]:
         if to == parent:
            pass
         elif not visited[to]:
            dfs(lowerCamelCase	, lowerCamelCase	, lowerCamelCase	, id_				)
            lowerCAmelCase     =			min(low[at]	, low[to]				)
            if id_ <= low[to]:
               bridges.append((at, to) if at < to else (to, at)				)
         else:
            # This edge is a back edge and cannot be a bridge
            lowerCAmelCase     =			min(low[at]	, low[to]				)

   lowerCAmelCase     =			[]
   for i in range(lowerCamelCase				):
      if not visited[i]:
         dfs(lowerCamelCase	, -1	, lowerCamelCase	, id_				)
   return bridges


if __name__ == "__main__":
       import doctest

       doctest.testmod()





