The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle.
1 <= n <= 9
Place queens row by row. Track columns and diagonals under attack using sets. Backtrack if no valid position in current row.
def solveNQueens(n):
result = []
cols = set()
pos_diag = set()
neg_diag = set()
board = [["."]*n for _ in range(n)]
def backtrack(row):
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 pos_diag or (row-col) in neg_diag:
continue
cols.add(col)
pos_diag.add(row+col)
neg_diag.add(row-col)
board[row][col] = "Q"
backtrack(row + 1)
cols.remove(col)
pos_diag.remove(row+col)
neg_diag.remove(row-col)
board[row][col] = "."
backtrack(0)
return result