This problem follows the Constraint Backtracking pattern, commonly found in the Backtracking category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Place queens row by row. Track columns, diagonals, anti-diagonals. Backtrack if conflict.
Diagonals have constant (row-col), anti-diagonals have constant (row+col) — using sets for these gives O(1) conflict checking.
result = []
cols = set()
diag = set() # row - col
antiDiag = set() # row + col
def backtrack(row, board):
if row == n:
result.append([''.join(row) for row in board])
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in antiDiag:
continue
cols.add(col); diag.add(row-col); antiDiag.add(row+col)
board[row][col] = 'Q'
backtrack(row + 1, board)
board[row][col] = '.'
cols.remove(col); diag.remove(row-col); antiDiag.remove(row+col)
backtrack(0, [['.']*n for _ in range(n)])Practice N-Queens and similar Backtracking problems with flashcards. Build pattern recognition through active recall.
Practice this problem