






from importlib import import_module

from .logging import get_logger


lowerCamelCase__       		=  get_logger(__name__)




class       snake_case__ :

       '''simple docstring'''



       def __init__(				self      ,    a__      ,    a__=None     )			->   Optional[Any]:






            '''simple docstring'''





            __snake_case      :Optional[Any] 							=    attrs or []
            if module is not None:
                 for key in module.__dict__:
                      if key in attrs or not key.startswith("""__"""     ):
                           setattr(self      ,    _lowerCAmelCase      ,    getattr(_lowerCAmelCase      ,    _lowerCAmelCase     )     )
            __snake_case      :int 							=    module._original_module if isinstance(_lowerCAmelCase      ,    _PatchedModuleObj     ) else module




class       snake_case__ :

       '''simple docstring'''
       lowerCamelCase				:					Optional[Any]								=			[]



       def __init__(				self      ,    a__      ,    a__      ,    a__      ,    a__=None     )			->   Union[str, Any]:






            '''simple docstring'''





            __snake_case      :Union[str, Any] 							=    obj
            __snake_case      :List[Any] 							=    target
            __snake_case      :List[Any] 							=    new
            __snake_case      :Any 							=    target.split("""."""     )[0]
            __snake_case      :int 							=    {}
            __snake_case      :List[str] 							=    attrs or []



       def __enter__(				self     )			->   Tuple:






            '''simple docstring'''





            __snake_case      :Any 							=    self.target.split("""."""     )

            # Patch modules:
            # it's used to patch attributes of submodules like "os.path.join";
            # in this case we need to patch "os" and "os.path"

            for i in range(len(_lowerCAmelCase     )     ):
                 try:
                      __snake_case      :Optional[int] 							=    import_module(""".""".join(submodules[: i + 1]     )     )
                 except ModuleNotFoundError:
                      continue
                 # We iterate over all the globals in self.obj in case we find "os" or "os.path"
                 for attr in self.obj.__dir__():
                      __snake_case      :str 							=    getattr(self.obj      ,    _lowerCAmelCase     )
                      # We don't check for the name of the global, but rather if its value *is* "os" or "os.path".
                      # This allows to patch renamed modules like "from os import path as ospath".
                      if obj_attr is submodule or (
                          (isinstance(_lowerCAmelCase      ,    _PatchedModuleObj     ) and obj_attr._original_module is submodule)
                      ):
                           __snake_case      :int 							=    obj_attr
                           # patch at top level
                           setattr(self.obj      ,    _lowerCAmelCase      ,    _PatchedModuleObj(_lowerCAmelCase      ,    attrs=self.attrs     )     )
                           __snake_case      :Tuple 							=    getattr(self.obj      ,    _lowerCAmelCase     )
                           # construct lower levels patches
                           for key in submodules[i + 1 :]:
                                setattr(_lowerCAmelCase      ,    _lowerCAmelCase      ,    _PatchedModuleObj(getattr(_lowerCAmelCase      ,    _lowerCAmelCase      ,    _lowerCAmelCase     )      ,    attrs=self.attrs     )     )
                                __snake_case      :List[str] 							=    getattr(_lowerCAmelCase      ,    _lowerCAmelCase     )
                           # finally set the target attribute
                           setattr(_lowerCAmelCase      ,    _lowerCAmelCase      ,    self.new     )

        # Patch attribute itself:
        # it's used for builtins like "open",
        # and also to patch "os.path.join" we may also need to patch "join"
        # itself if it was imported as "from os.path import join".

            if submodules:  # if it's an attribute of a submodule like "os.path.join"
                 try:
                      __snake_case      :Any 							=    getattr(import_module(""".""".join(_lowerCAmelCase     )     )      ,    _lowerCAmelCase     )
                 except (AttributeError, ModuleNotFoundError):
                      return
                 # We iterate over all the globals in self.obj in case we find "os.path.join"
                 for attr in self.obj.__dir__():
                      # We don't check for the name of the global, but rather if its value *is* "os.path.join".
                      # This allows to patch renamed attributes like "from os.path import join as pjoin".
                      if getattr(self.obj      ,    _lowerCAmelCase     ) is attr_value:
                           __snake_case      :Optional[Any] 							=    getattr(self.obj      ,    _lowerCAmelCase     )
                           setattr(self.obj      ,    _lowerCAmelCase      ,    self.new     )
            elif target_attr in globals()["__builtins__"]:  # if it'a s builtin like "open"
                 __snake_case      :Optional[Any] 							=    globals()['''__builtins__'''][target_attr]
                 setattr(self.obj      ,    _lowerCAmelCase      ,    self.new     )
            else:
                 raise RuntimeError(F'''Tried to patch attribute {target_attr} instead of a submodule.'''     )



       def __exit__(				self      ,    *a__     )			->   Union[str, Any]:






            '''simple docstring'''





            for attr in list(self.original     ):
                 setattr(self.obj      ,    _lowerCAmelCase      ,    self.original.pop(_lowerCAmelCase     )     )



       def        __lowercase    (				self     )			->   List[str]:






            '''simple docstring'''





            self.__enter__()
            self._active_patches.append(self     )



       def        __lowercase    (				self     )			->   List[Any]:






            '''simple docstring'''





            try:
                 self._active_patches.remove(self     )
            except ValueError:
                 # If the patch hasn't been started this will fail
                 return None

            return self.__exit__()









from __future__ import annotations






def 		lowerCAmelCase  (	UpperCamelCase__   :   list[int]       ,			UpperCamelCase__   :   list[int]       ,			UpperCamelCase__   :   list[int]       ,			UpperCamelCase__   :   list[list[str]]       ,			UpperCamelCase__   :   int       ,			)      ->    None:

						"""simple docstring"""





						__SCREAMING_SNAKE_CASE:				Any           =   len(UpperCamelCase__					)

						# 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(UpperCamelCase__					):
												# 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]       ,			UpperCamelCase__       ,			UpperCamelCase__       ,			)






def 		lowerCAmelCase  (	UpperCamelCase__   :   int					)      ->    None:

						"""simple docstring"""





						__SCREAMING_SNAKE_CASE:				list[list[str]]           =   []
						depth_first_search([]       ,			[]       ,			[]       ,			UpperCamelCase__       ,			UpperCamelCase__					)

						# Print all the boards
						for board in boards:
												for column in board:
																		print(UpperCamelCase__					)
												print(''''''					)

						print(len(UpperCamelCase__					)       ,			'''solutions were found.'''					)


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							n_queens_solution(4)



