






from __future__ import annotations

__UpperCAmelCase								=						list[list[int]]

# assigning initial values to the grid
__UpperCAmelCase								=						[
    [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								=						[
    [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      lowercase__      (     __snake_case    :							Matrix     ,       __snake_case    :							int     ,       __snake_case    :							int     ,       __snake_case    :							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      lowercase__      (     __snake_case    :							Matrix  ):


					'''simple docstring'''


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




def      lowercase__      (     __snake_case    :							Matrix  ):


					'''simple docstring'''


					if location := find_empty_location(__snake_case  ):
										UpperCAmelCase_       ,  UpperCAmelCase_    :      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(__snake_case     ,       __snake_case     ,       __snake_case     ,       __snake_case  ):
															UpperCAmelCase_    :      Any            =						digit

															if sudoku(__snake_case  ) is not None:
																				return grid

															UpperCAmelCase_    :      Tuple            =						0

					return None




def      lowercase__      (     __snake_case    :							Matrix  ):


					'''simple docstring'''


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














import os

# Precomputes a list of the 100 first triangular numbers
__UpperCAmelCase								=						[int(0.5 * n * (n + 1)) for n in range(1, 101)]




def      lowercase__      (     ):


					'''simple docstring'''


					UpperCAmelCase_    :      Any            =						os.path.dirname(os.path.realpath(__snake_case  )  )
					UpperCAmelCase_    :      Optional[Any]            =						os.path.join(__snake_case     ,       'words.txt'  )

					UpperCAmelCase_    :      Union[str, Any]            =						''
					with open(__snake_case  ) as f:
										UpperCAmelCase_    :      List[Any]            =						f.readline()

					UpperCAmelCase_    :      Optional[int]            =						[word.strip('"'  ) for word in words.strip('\r\n'  ).split(','  )]
					UpperCAmelCase_    :      Optional[int]            =						[
					    word
					    for word in [sum(ord(__snake_case  ) - 64 for x in word  ) for word in words]
					    if word in TRIANGULAR_NUMBERS
					]
					return len(__snake_case  )


if __name__ == "__main__":
		print(solution())






