N Queens
- 2 min read
- LC-Hard
- Backtracking
3 years ago
Solution
- We know that only one queen can be placed on each row- so that's the basic of our backtracking. We go row by row
- A queen is in a valid position only if the following conditions are met:
- It is the only one on the column
- It is the only one on the positive diagonal
- It is the only one on the negative diagonal
- We keep 3 sets for each of the following conditions above. While we backtrack, we add the position of the current queen on to each of these sets, and only continue if the next queen isn't on an invalid square (i.e. a square which doesn't intersect with any of the three sets above)
- How do you refer to the positive and negative diagonal?
- You use (r + c) for the positive diag, since for any positive diag, r + c gives the same value
- You use (r - c) for the negative diag, since for any negative diag, r - c gives the same value
- We don't need a set for the rows because our backtrack function goes row by row and takes care of that condition
- One we finish backtracking, to explore other options, we remove everything from the set we just added (look at the code below)
| Time | Space | Explanation |
|---|---|---|
O() | O() |
def solveNQueens(self, n: int) -> List[List[str]]:
col, pos_diag, neg_diag = set(), set(), set()
board = [['.'] * n for _ in range(n)]
ans = []
def backtrack(r):
if r == n:
copy = [''.join(row) for row in board]
ans.append(copy)
return
for c in range(n):
if c in col or (r + c) in pos_diag or (r - c) in neg_diag:
continue
col.add(c)
pos_diag.add(r + c)
neg_diag.add(r - c)
board[r][c] = 'Q'
backtrack(r + 1)
col.remove(c)
pos_diag.remove(r + c)
neg_diag.remove(r - c)
board[r][c] = '.'
backtrack(0)
return ans