This is LeetCode #51: N-Queens — the ultimate backtracking challenge! 👑
💡 Think of it like this: Place N queens on an N×N chessboard so no two queens can attack each other. Queens can attack in any direction — horizontal, vertical, and both diagonals. For a 4×4 board, how many valid arrangements exist?
The Backtracking Approach: Place queens one row at a time. For each row, try each column. If it's safe (no conflicts with queens above), place it and move to the next row.
How to check if a position is safe:
setr - c (constant for each diagonal) → Use a setr + c → Use a set💭 Now it's your turn! Using the approach above, implement your solution in the editor. You've got this! 💪
Why 3 sets work: For any diagonal going ↘, all cells have the same r-c. For any diagonal going ↙, all cells have the same r+c. Checking membership in a set is O(1)!
Complexity: Time O(n!) — much better than O(n^n) brute force. Space O(n) for the sets and recursion stack.
def solveNQueens(n):
cols = set()
diag = set() # r - c identifies each diagonal
anti_diag = set() # r + c identifies each anti-diagonal
count = 0
def backtrack(row):
nonlocal count
if row == n: # All queens placed!
count += 1
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti_diag:
continue # Not safe, skip
cols.add(col) # Place queen
diag.add(row-col)
anti_diag.add(row+col)
backtrack(row + 1) # Try next row
cols.remove(col) # Backtrack!
diag.remove(row-col)
anti_diag.remove(row+col)
backtrack(0)
return count
solveNQueens(4)
2