Back to Recursion

N-Queens Problem

Watch backtracking recursion solve the classic N-Queens puzzle by placing queens on a chessboard.

Backtracking
Time: O(N!)
Space: O(N²)

Controls

0 solutions exist

Legend

Placed Queen
Safe Position
Unsafe Position
Under Attack

Current Step

Step 1 of 0

Click Start to begin the N-Queens visualization

Action: Start

4×4 Chessboard

Current Row: 0
Queens Placed: 0

Backtracking Algorithm

def solve_nqueens(n):
    def is_safe(board, row, col):
        # Check column and diagonals
        for i in range(row):
            if (board[i] == col or 
                abs(board[i] - col) == abs(i - row)):
                return False
        return True
    
    def backtrack(board, row):
        if row == n:  # Base case - solution found
            solutions.append(board[:])
            return
        
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col  # Place queen
                backtrack(board, row + 1)  # Recurse
                board[row] = -1  # Backtrack
    
    solutions = []
    board = [-1] * n
    backtrack(board, 0)
    return solutions

# Example: 4-Queens has 0 solutions

Algorithm Analysis

Time Complexity: O(N!)

In the worst case, we try all possible arrangements of N queens, which is approximately N! possibilities.

Space Complexity: O(N²)

We need space for the board (N×N) and the recursion stack depth is at most N.

Real-World Applications

  • • Constraint satisfaction problems
  • • Resource allocation optimization
  • • Scheduling conflicts resolution
  • • Game AI and puzzle solving
  • • Circuit board layout design
  • • Sudoku and crossword solvers