from typing import List
 
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        """
        Solve the N-Queens problem:
        Place n queens on an n x n chessboard so that no two queens attack each other.
        Returns all possible board configurations.
        """
        results = []
        queens = [-1] * n   # queens[row] = column index of queen in that row
        columns = [True] * n  # track available columns
 
        def is_diagonal_conflict(row: int, col: int) -> bool:
            """Check if placing a queen at (row, col) conflicts diagonally."""
            for prev_row in range(row):
                prev_col = queens[prev_row]
                if abs(row - prev_row) == abs(col - prev_col):
                    return True
            return False
 
        def backtrack(row: int) -> None:
            """Try to place queens row by row."""
            if row == n:
                # Construct a valid board representation
                board = []
                for r in range(n):
                    row_str = ['.'] * n
                    row_str[queens[r]] = 'Q'
                    board.append("".join(row_str))
                results.append(board)
                return
 
            for col in range(n):
                if columns[col] and not is_diagonal_conflict(row, col):
                    # Place queen
                    queens[row] = col
                    columns[col] = False
 
                    # Recurse to next row
                    backtrack(row + 1)
 
                    # Backtrack (remove queen)
                    columns[col] = True
 
        backtrack(0)
        return results
 

ZnJvbSB0eXBpbmcgaW1wb3J0IExpc3QKCmNsYXNzIFNvbHV0aW9uOgogICAgZGVmIHNvbHZlTlF1ZWVucyhzZWxmLCBuOiBpbnQpIC0+IExpc3RbTGlzdFtzdHJdXToKICAgICAgICAiIiIKICAgICAgICBTb2x2ZSB0aGUgTi1RdWVlbnMgcHJvYmxlbToKICAgICAgICBQbGFjZSBuIHF1ZWVucyBvbiBhbiBuIHggbiBjaGVzc2JvYXJkIHNvIHRoYXQgbm8gdHdvIHF1ZWVucyBhdHRhY2sgZWFjaCBvdGhlci4KICAgICAgICBSZXR1cm5zIGFsbCBwb3NzaWJsZSBib2FyZCBjb25maWd1cmF0aW9ucy4KICAgICAgICAiIiIKICAgICAgICByZXN1bHRzID0gW10KICAgICAgICBxdWVlbnMgPSBbLTFdICogbiAgICMgcXVlZW5zW3Jvd10gPSBjb2x1bW4gaW5kZXggb2YgcXVlZW4gaW4gdGhhdCByb3cKICAgICAgICBjb2x1bW5zID0gW1RydWVdICogbiAgIyB0cmFjayBhdmFpbGFibGUgY29sdW1ucwoKICAgICAgICBkZWYgaXNfZGlhZ29uYWxfY29uZmxpY3Qocm93OiBpbnQsIGNvbDogaW50KSAtPiBib29sOgogICAgICAgICAgICAiIiJDaGVjayBpZiBwbGFjaW5nIGEgcXVlZW4gYXQgKHJvdywgY29sKSBjb25mbGljdHMgZGlhZ29uYWxseS4iIiIKICAgICAgICAgICAgZm9yIHByZXZfcm93IGluIHJhbmdlKHJvdyk6CiAgICAgICAgICAgICAgICBwcmV2X2NvbCA9IHF1ZWVuc1twcmV2X3Jvd10KICAgICAgICAgICAgICAgIGlmIGFicyhyb3cgLSBwcmV2X3JvdykgPT0gYWJzKGNvbCAtIHByZXZfY29sKToKICAgICAgICAgICAgICAgICAgICByZXR1cm4gVHJ1ZQogICAgICAgICAgICByZXR1cm4gRmFsc2UKCiAgICAgICAgZGVmIGJhY2t0cmFjayhyb3c6IGludCkgLT4gTm9uZToKICAgICAgICAgICAgIiIiVHJ5IHRvIHBsYWNlIHF1ZWVucyByb3cgYnkgcm93LiIiIgogICAgICAgICAgICBpZiByb3cgPT0gbjoKICAgICAgICAgICAgICAgICMgQ29uc3RydWN0IGEgdmFsaWQgYm9hcmQgcmVwcmVzZW50YXRpb24KICAgICAgICAgICAgICAgIGJvYXJkID0gW10KICAgICAgICAgICAgICAgIGZvciByIGluIHJhbmdlKG4pOgogICAgICAgICAgICAgICAgICAgIHJvd19zdHIgPSBbJy4nXSAqIG4KICAgICAgICAgICAgICAgICAgICByb3dfc3RyW3F1ZWVuc1tyXV0gPSAnUScKICAgICAgICAgICAgICAgICAgICBib2FyZC5hcHBlbmQoIiIuam9pbihyb3dfc3RyKSkKICAgICAgICAgICAgICAgIHJlc3VsdHMuYXBwZW5kKGJvYXJkKQogICAgICAgICAgICAgICAgcmV0dXJuCgogICAgICAgICAgICBmb3IgY29sIGluIHJhbmdlKG4pOgogICAgICAgICAgICAgICAgaWYgY29sdW1uc1tjb2xdIGFuZCBub3QgaXNfZGlhZ29uYWxfY29uZmxpY3Qocm93LCBjb2wpOgogICAgICAgICAgICAgICAgICAgICMgUGxhY2UgcXVlZW4KICAgICAgICAgICAgICAgICAgICBxdWVlbnNbcm93XSA9IGNvbAogICAgICAgICAgICAgICAgICAgIGNvbHVtbnNbY29sXSA9IEZhbHNlCgogICAgICAgICAgICAgICAgICAgICMgUmVjdXJzZSB0byBuZXh0IHJvdwogICAgICAgICAgICAgICAgICAgIGJhY2t0cmFjayhyb3cgKyAxKQoKICAgICAgICAgICAgICAgICAgICAjIEJhY2t0cmFjayAocmVtb3ZlIHF1ZWVuKQogICAgICAgICAgICAgICAgICAgIGNvbHVtbnNbY29sXSA9IFRydWUKCiAgICAgICAgYmFja3RyYWNrKDApCiAgICAgICAgcmV0dXJuIHJlc3VsdHMK