
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 							__A(lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase )		->				bool:

		"""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 							__A(lowerCAmelCase )		->				tuple[int, int] | None:

		"""simple docstring"""






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


def 							__A(lowerCAmelCase )		->				Matrix | None:

		"""simple docstring"""






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

		for digit in range(1						,  1_0 ):
				if is_safe(lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase ):
						_UpperCamelCase						    =	digit

						if sudoku(lowerCAmelCase ) is not None:
								return grid

						_UpperCamelCase						    =	0

		return None


def 							__A(lowerCAmelCase )		->				None:

		"""simple docstring"""






		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.")





from __future__ import annotations


def 							__A(lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase						,  lowerCAmelCase						,  )		->				None:

		"""simple docstring"""






		_UpperCamelCase						    =	len(lowerCAmelCase )

		# If row is equal to the size of the board it means there are a queen in each row in
		# the current board (possible_board)
		if row == n:
				# We convert the variable possible_board that looks like this: [1, 3, 0, 2] to
				# this: ['. Q . . ', '. . . Q ', 'Q . . . ', '. . Q . ']
				boards.append([""". """ * i + """Q """ + """. """ * (n - 1 - i) for i in possible_board] )
				return

		# We iterate each column in the row to find all possible results in each row
		for col in range(lowerCAmelCase ):
				# We apply that we learned previously. First we check that in the current board
				# (possible_board) there are not other same value because if there is it means
				# that there are a collision in vertical. Then we apply the two formulas we
				# learned before:
				#
				# 45º: y - x = b or 45: row - col = b
				# 135º: y + x = b or row + col = b.
				#
				# And we verify if the results of this two formulas not exist in their variables
				# respectively.  (diagonal_right_collisions, diagonal_left_collisions)
				#
				# If any or these are True it means there is a collision so we continue to the
				# next value in the for loop.
				if (
				    col in possible_board
				    or row - col in diagonal_right_collisions
				    or row + col in diagonal_left_collisions
				):
						continue

				# If it is False we call dfs function again and we update the inputs
				depth_first_search(
				    [*possible_board, col]						,  [*diagonal_right_collisions, row - col]						,  [*diagonal_left_collisions, row + col]						,  lowerCAmelCase						,  lowerCAmelCase						,  )


def 							__A(lowerCAmelCase )		->				None:

		"""simple docstring"""






		_UpperCamelCase						    =	[]
		depth_first_search([]						,  []						,  []						,  lowerCAmelCase						,  lowerCAmelCase )

		# Print all the boards
		for board in boards:
				for column in board:
						print(lowerCAmelCase )
				print("""""" )

		print(len(lowerCAmelCase )						,  """solutions were found.""" )


if __name__ == "__main__":
		import doctest

		doctest.testmod()
		n_queens_solution(4)



