About N-Queens
Place N queens on an N×N chessboard so no queen threatens another. Backtracking fills columns one by one — if no safe row exists, it backtracks to the previous column.
4×4 solutions
2
5×5 solutions
10
6×6 solutions
4
8×8 solutions
92
What is Backtracking?
Try a choice, if stuck, undo it and try another. Like solving a Sudoku — go forward until stuck, then backtrack.
n_queens.py
def n_queens(n):
solutions = []
def is_safe(queens, row, col):
for r, c in queens:
if r==row or c==col: return False
if abs(r-row)==abs(c-col): return False
return True
def solve(col, queens=[]):
if col == n:
solutions.append(queens[:])
return
for row in range(n):
if is_safe(queens, row, col):
queens.append((row, col)) # place
solve(col + 1, queens) # recurse
queens.pop() # backtrack ←
solve(0)
return solutions