class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def createBoard(state):
            # Generates the board configuration as a list of strings from the state list
            board = []
            for row in state:
                board.append("".join("Q" if c == row else "." for c in range(n)))
            return board

        def isSafe(row, col, state):
            # Checks if it's safe to place a queen at the given row and col
            # by checking against all previously placed queens
            for r in range(row):
                if (
                    state[r] == col
                    or state[r] - r == col - row
                    or state[r] + r == col + row
                ):
                    return False
            return True

        def backtrack(row, state):
            # Tries to place a queen in each row, backtracks if not possible
            if row == n:
                solutions.append(createBoard(state))
                return
            for col in range(n):
                if isSafe(row, col, state):
                    state[row] = col
                    backtrack(row + 1, state)
                    # Backtracking is implicit as we overwrite the state[row] in each iteration

        solutions = []
        backtrack(0, [0] * n)  # Initialize the state with 0s, which will be updated
        return solutions