N-Queens

Intuition

Because exactly one queen belongs in each row, we can decide the columns row by row. For a queen at (row, col), the cells it attacks along diagonals all share a constant value of row + col on one diagonal and row - col on the other. By marking which columns and which diagonal values are already occupied, we can check any candidate square instantly. When we reach a row past the last one, every queen has been safely placed and we record the board.

Algorithm walkthrough

1. 1Fill an n by n board with '.' and prepare markers for columns and the two diagonal families.
2. 2Recurse on the current row; if the row index equals n, capture the completed board.
3. 3For each column in the row, skip it if the column or either diagonal is already occupied.
4. 4Place a queen, mark its column and diagonals, then recurse on the next row.
5. 5Remove the queen and clear the markers so the next column can be tried.

Implementation

class Solution:
    def solveNQueens(self, n: int) -> list[list[str]]:
        result = []
        cols = set()
        diag1 = set()   # row - col
        diag2 = set()   # row + col
        board = [["."] * n for _ in range(n)]

        def backtrack(row: int) -> None:
            if row == n:
                result.append(["".join(r) for r in board])
                return
            for col in range(n):
                if col in cols or (row - col) in diag1 or (row + col) in diag2:
                    continue
                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row][col] = "Q"
                backtrack(row + 1)
                board[row][col] = "."
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        backtrack(0)
        return result