
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		Optional[Any]:
			return (pointa[0] - pointa[0]) ** 2 + (pointa[1] - pointa[1]) ** 2
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_=0     )				->		str:
			return sorted(SCREAMING_SNAKE_CASE_       ,							key=lambda SCREAMING_SNAKE_CASE_     : x[column]     )
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_=float('inf'     )     )				->		Optional[Any]:

			for i in range(points_counts - 1     ):
						for j in range(i + 1       ,							SCREAMING_SNAKE_CASE_     ):
									lowerCAmelCase__      :      Optional[int]         =		euclidean_distance_sqr(points[i]       ,							points[j]     )
									if current_dis < min_dis:
												lowerCAmelCase__      :      Any         =		current_dis
			return min_dis
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_=float('inf'     )     )				->		Tuple:

			for i in range(min(6       ,							points_counts - 1     )       ,							SCREAMING_SNAKE_CASE_     ):
						for j in range(max(0       ,							i - 6     )       ,							SCREAMING_SNAKE_CASE_     ):
									lowerCAmelCase__      :      Dict         =		euclidean_distance_sqr(points[i]       ,							points[j]     )
									if current_dis < min_dis:
												lowerCAmelCase__      :      Optional[int]         =		current_dis
			return min_dis
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		Dict:

			# base case
			if points_counts <= 3:
						return dis_between_closest_pair(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )

			# recursion
			lowerCAmelCase__      :      Any         =		points_counts // 2
			lowerCAmelCase__      :      str         =		closest_pair_of_points_sqr(
			    SCREAMING_SNAKE_CASE_       ,							points_sorted_on_y[:mid]       ,							SCREAMING_SNAKE_CASE_     )
			lowerCAmelCase__      :      Optional[int]         =		closest_pair_of_points_sqr(
			    SCREAMING_SNAKE_CASE_       ,							points_sorted_on_y[mid:]       ,							points_counts - mid     )
			lowerCAmelCase__      :      int         =		min(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )
			lowerCAmelCase__      :      List[str]         =		[]
			for point in points_sorted_on_x:
						if abs(point[0] - points_sorted_on_x[mid][0]     ) < closest_pair_dis:
									cross_strip.append(SCREAMING_SNAKE_CASE_     )

			lowerCAmelCase__      :      Any         =		dis_between_closest_in_strip(
			    SCREAMING_SNAKE_CASE_       ,							len(SCREAMING_SNAKE_CASE_     )       ,							SCREAMING_SNAKE_CASE_     )
			return min(SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		Dict:
			lowerCAmelCase__      :      List[Any]         =		column_based_sort(SCREAMING_SNAKE_CASE_       ,							column=0     )
			lowerCAmelCase__      :      Dict         =		column_based_sort(SCREAMING_SNAKE_CASE_       ,							column=1     )
			return (
			    closest_pair_of_points_sqr(
			        SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )
			) ** 0.5


if __name__ == "__main__":
					lowerCamelCase__          =		[(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
					print("""Distance:""", closest_pair_of_points(points, len(points)))

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  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_       ,							SCREAMING_SNAKE_CASE_     )				->		bool:
			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  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		tuple[int, int] | None:
			for i in range(9     ):
						for j in range(9     ):
									if grid[i][j] == 0:
												return i, j
			return None
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		Matrix | None:
			if location := find_empty_location(SCREAMING_SNAKE_CASE_     ):
						lowerCAmelCase__      ,				lowerCAmelCase__      :      Any         =		location
			else:
						# If the location is ``None``, then the grid is solved.
						return grid

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

									if sudoku(SCREAMING_SNAKE_CASE_     ) is not None:
												return grid

									lowerCAmelCase__      :      List[Any]         =		0

			return None
def  lowerCAmelCase__			(  SCREAMING_SNAKE_CASE_     )				->		None:
			for row in grid:
						for cell in row:
									print(SCREAMING_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:""")
										lowerCamelCase__          =		sudoku(example_grid)
										if solution is not None:
															print_solution(solution)
										else:
															print("""Cannot find a solution.""")