Core Insight Build one partial answer at a time and undo each choice so sibling branches start clean.
Common Pitfall Copy a completed path before appending it to results; later mutations must not alter it.
Description
Place n queens on an n×n chessboard with no two attacking.
Constraints
- Time Complexity:
O(n!) - Space Complexity:
O(n)
Tags
arraybacktracking
Implementation Plan Translate the invariant into these small, testable moves.
- Choose a candidate.
- Record the choice.
- Explore the next decision.
- Undo the choice before trying the next candidate.
def solveNQueens(n):
col = set()
posDiag = set()
negDiag = set()
res = []
board = [["."] * n for i in range(n)]
def backtrack(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if c in col or (r + c) in posDiag or (r - c) in negDiag:
continue
col.add(c)
posDiag.add(r + c)
negDiag.add(r - c)
board[r][c] = "Q"
backtrack(r + 1)
col.remove(c)
posDiag.remove(r + c)
negDiag.remove(r - c)
board[r][c] = "."
backtrack(0)
return res