




from __future__ import annotations

lowerCamelCase			:			int								=       list[list[int]]

# assigning initial values to the grid
lowerCamelCase			:			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
lowerCamelCase			:			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__   (       lowercase		,lowercase		,lowercase		,lowercase	)    ->  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 		SCREAMING_SNAKE_CASE__   (       lowercase	)    ->  Optional[Any]:







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




def 		SCREAMING_SNAKE_CASE__   (       lowercase	)    ->  List[str]:







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

   for digit in range(1		,10	):
      if is_safe(_UpperCamelCase		,_UpperCamelCase		,_UpperCamelCase		,_UpperCamelCase	):
         snake_case :							Optional[Any]           =			digit

         if sudoku(_UpperCamelCase	) is not None:
            return grid

         snake_case :							Tuple           =			0

   return None




def 		SCREAMING_SNAKE_CASE__   (       lowercase	)    ->  str:







   for row in grid:
      for cell in row:
         print(_UpperCamelCase		,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:')
              lowerCamelCase			:			Optional[Any]								=       sudoku(example_grid)
              if solution is not None:
                     print_solution(solution)
              else:
                     print('Cannot find a solution.')









a			:			Any												=					[sum(int(c, 10) ** 2 for c in i.__str__()) for i in range(100000)]


def 		lowercase_	(  _UpperCamelCase	):


			'''simple docstring'''







			__lowercase			       = 0
			while number:
						# Increased Speed Slightly by checking every 5 digits together.
						sum_of_digits_squared += DIGITS_SQUARED[number % 10_00_00]
						number //= 10_00_00

			return sum_of_digits_squared


# There are 2 Chains made,
# One ends with 89 with the chain member 58 being the one which when declared first,
# there will be the least number of iterations for all the members to be checked.

# The other one ends with 1 and has only one element 1.

# So 58 and 1 are chosen to be declared at the starting.

# Changed dictionary to an array to quicken the solution
a			:			list[bool | None]												=					[None] * 10000000
a			:			int												=					True
a			:			Any												=					False


def 		lowercase_	(  _UpperCamelCase	):


			'''simple docstring'''







			if CHAINS[number - 1] is not None:
						return CHAINS[number - 1]  # type: ignore

			__lowercase			       = chain(next_number(_UpperCamelCase	)	)
			__lowercase			       = number_chain

			while number < 10_00_00_00:
						__lowercase			       = number_chain
						number *= 10

			return number_chain


def 		lowercase_	(  _UpperCamelCase = 10_00_00_00	):


			'''simple docstring'''







			for i in range(1							,      _UpperCamelCase	):
						if CHAINS[i] is None:
									chain(i + 1	)

			return CHAINS[:number].count(_UpperCamelCase	)


if __name__ == "__main__":
	import doctest

	doctest.testmod()
	print(f'''{solution() = }''')


