N-Queens Problem

The Chess Queen's Challenge: Placing Royalty Without Conflict

Imagine you're tasked with placing eight queens on a chessboard so that no queen can attack another. Queens are powerful pieces that can move any number of squares horizontally, vertically, or diagonally. This classic constraint satisfaction problem has challenged programmers for decades and remains a perfect example of backtracking in action.

The N-Queens problem demonstrates how backtracking can solve complex combinatorial puzzles by building solutions incrementally while respecting constraints.

Problem Statement

Place N queens on an N×N chessboard such that:

• No two queens share the same row
• No two queens share the same column
• No two queens share the same diagonal

Input: Integer N (board size)
Output: All possible configurations or one valid solution

The Backtracking Approach

Key Insight: One Queen Per Row

Since queens can't share rows, we can place exactly one queen per row. This reduces the problem from placing N queens on N×N board to choosing N valid column positions.

Algorithm Structure

def solve_n_queens(n):
    board = [['.' for _ in range(n)] for _ in range(n)]
    solutions = []
    
    def backtrack(row):
        if row == n:
            # All queens placed successfully
            solutions.append([''.join(row) for row in board])
            return
        
        for col in range(n):
            if is_safe(board, row, col, n):
                # Place queen
                board[row][col] = 'Q'
                
                # Recurse to next row
                backtrack(row + 1)
                
                # Backtrack: remove queen
                board[row][col] = '.'
    
    backtrack(0)
    return solutions

Safety Check Function

def is_safe(board, row, col, n):
    # Check same column
    for i in range(row):
        if board[i][col] == 'Q':
            return False
    
    # Check upper-left diagonal
    for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
        if board[i][j] == 'Q':
            return False
    
    # Check upper-right diagonal
    for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
        if board[i][j] == 'Q':
            return False
    
    return True

Visualizing the Solution

4-Queens Example

Solution 1:
. Q . .
. . . Q
Q . . .
. . Q .

Solution 2:
. . Q .
Q . . .
. . . Q
. Q . .

Each solution shows queens placed such that no two attack each other.

Time Complexity Analysis

Worst Case

• Branching Factor: N choices per row
• Depth: N rows
• Total: O(N!) in worst case

Average Case with Pruning

• Constraint Checking: Eliminates invalid positions early
• Much Better: Often finds solutions quickly due to aggressive pruning

Optimizations

• Bit Manipulation: Use bitmasks to track occupied columns/diagonals
• Pre-computed Attacks: Cache safe positions
• Symmetry Breaking: Avoid symmetric solutions

Bit Manipulation Optimization

def solve_n_queens_bit(n):
    def backtrack(row, cols, diagonals1, diagonals2):
        if row == n:
            return 1
        
        solutions = 0
        available = ((1 << n) - 1) & ~(cols | diagonals1 | diagonals2)
        
        while available:
            # Get lowest set bit
            col = available & -available
            available &= available - 1
            
            # Recurse with updated masks
            solutions += backtrack(
                row + 1,
                cols | col,
                (diagonals1 | col) << 1,
                (diagonals2 | col) >> 1
            )
        
        return solutions
    
    return backtrack(0, 0, 0, 0)

Finding All Solutions vs One Solution

Finding All Solutions

def solve_all_n_queens(n):
    board = [['.' for _ in range(n)] for _ in range(n)]
    solutions = []
    
    def backtrack(row):
        if row == n:
            solutions.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if is_safe(board, row, col, n):
                board[row][col] = 'Q'
                backtrack(row + 1)
                board[row][col] = '.'
    
    backtrack(0)
    return solutions

Finding One Solution

def solve_one_n_queens(n):
    board = [['.' for _ in range(n)] for _ in range(n)]
    
    def backtrack(row):
        if row == n:
            return True
        
        for col in range(n):
            if is_safe(board, row, col, n):
                board[row][col] = 'Q'
                if backtrack(row + 1):
                    return True
                board[row][col] = '.'
        
        return False
    
    backtrack(0)
    return board

Real-World Applications

VLSI Circuit Design

• Component Placement: Place components without interference
• Routing: Design circuit paths avoiding conflicts

Traffic Control Systems

• Light Scheduling: Coordinate traffic lights to avoid conflicts
• Air Traffic Control: Position aircraft safely

Resource Allocation

• Task Scheduling: Assign resources without conflicts
• Exam Scheduling: Schedule exams avoiding student conflicts

Common Mistakes and Solutions

1. Checking Wrong Directions

Mistake: Only checking rows above current position
Solution: Check all three directions (column, both diagonals)

2. Not Backtracking Properly

Mistake: Forgetting to reset board positions
Solution: Always undo changes after recursive calls

3. Inefficient Safety Checks

Mistake: Recalculating attacks from scratch
Solution: Use incremental updates or bit manipulation

4. Not Using Row Optimization

Mistake: Trying to place multiple queens per row
Solution: Place exactly one queen per row

Performance for Different N

Key Takeaways

1. One queen per row eliminates row conflicts and simplifies the problem
2. Constraint checking must verify columns and both diagonals
3. Backtracking allows exploring all valid configurations
4. Optimizations like bit manipulation can dramatically improve performance

The N-Queens problem showcases backtracking's power in solving constraint satisfaction problems. It teaches us that complex combinatorial problems can often be solved by breaking them down into smaller, manageable decisions while maintaining solution validity.