Medium Backtrack+Prune Backtracking
In plain English: Place 4 queens on a 4x4 chessboard so none can attack another (no shared row, column, or diagonal).
Place one queen per row. Track occupied columns and diagonals with sets — prune immediately when a column or diagonal conflicts.
Prompt
Place 4 queens on a 4x4 board so that no two queens threaten each other. Return all solutions.
Try to write it from scratch before scrolling down.
Solution
def solve_n_queens(n=4):
result = []
def backtrack(row, cols, diag1, diag2, board):
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 diag1 or (row + col) in diag2:
continue # prune: conflict
board[row][col] = 'Q'
backtrack(row + 1, cols | {col}, diag1 | {row - col},
diag2 | {row + col}, board)
board[row][col] = '.'
backtrack(0, set(), set(), set(), [['.']*n for _ in range(n)])
return result
# Test: len(solve_n_queens(4)) == 2