N-Queens Problem: Interactive Backtracking Algorithm Visualization

Description

The N-Queens problem is a classic chess puzzle where you need to place N queens on an N×N chessboard such that no two queens threaten each other. This means no two queens share the same row, column, or diagonal.

How It Works

Start with an empty N×N board
Place queens one by one in different columns, starting from the leftmost column
When placing a queen, check if it's safe from attack by already placed queens
If placing the queen leads to a solution, record it
If placing the queen doesn't lead to a solution:
- Remove the queen (backtrack)
- Try the next row in the same column
If all rows are tried and no solution is found, return false

Visualization

Board Size:

Speed:

Select board size and click Start to begin visualization

Solutions found: 0

Implementation


class NQueens:
    def solve(self, n: int) -> list[list[str]]:
        """
        Solve N-Queens problem and return all solutions.
        
        Args:
            n: Size of the board (N x N)
            
        Returns:
            List of valid board configurations
        """
        def create_board() -> list[str]:
            return ['.' * n for _ in range(n)]
        
        def is_safe(row: int, col: int) -> bool:
            # Check row on left side
            for j in range(col):
                if board[row][j] == 'Q':
                    return False
            
            # Check upper diagonal
            for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            
            # Check lower diagonal
            for i, j in zip(range(row+1, n), range(col-1, -1, -1)):
                if board[i][j] == 'Q':
                    return False
            
            return True
        
        def backtrack(col: int):
            if col == n:
                solutions.append([''.join(row) for row in board])
                return
            
            for row in range(n):
                if is_safe(row, col):
                    board[row] = board[row][:col] + 'Q' + board[row][col+1:]
                    backtrack(col + 1)
                    board[row] = board[row][:col] + '.' + board[row][col+1:]
        
        board = create_board()
        solutions = []
        backtrack(0)
        return solutions

# Example usage
if __name__ == "__main__":
    solver = NQueens()
    n = 4  # Try 4x4 board
    solutions = solver.solve(n)
    
    print(f"Found {len(solutions)} solutions for {n}x{n} board:")
    for i, solution in enumerate(solutions, 1):
        print(f"\nSolution {i}:")
        for row in solution:
            print(row)


#include <iostream>
#include <vector>
#include <string>

class NQueens {
private:
    bool isSafe(const std::vector<std::string>& board, int row, int col, int n) {
        // Check row on left side
        for (int j = 0; j < col; j++) {
            if (board[row][j] == 'Q') return false;
        }
        
        // Check upper diagonal
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        
        // Check lower diagonal
        for (int i = row, j = col; i < n && j >= 0; i++, j--) {
            if (board[i][j] == 'Q') return false;
        }
        
        return true;
    }
    
    void backtrack(std::vector<std::vector<std::string>>& solutions,
                  std::vector<std::string>& board, int col, int n) {
        if (col == n) {
            solutions.push_back(board);
            return;
        }
        
        for (int row = 0; row < n; row++) {
            if (isSafe(board, row, col, n)) {
                board[row][col] = 'Q';
                backtrack(solutions, board, col + 1, n);
                board[row][col] = '.';
            }
        }
    }

public:
    std::vector<std::vector<std::string>> solve(int n) {
        std::vector<std::vector<std::string>> solutions;
        std::vector<std::string> board(n, std::string(n, '.'));
        
        backtrack(solutions, board, 0, n);
        return solutions;
    }
};

int main() {
    NQueens solver;
    int n = 4;  // Try 4x4 board
    
    auto solutions = solver.solve(n);
    
    std::cout << "Found " << solutions.size() << " solutions for " 
              << n << "x" << n << " board:\n";
              
    for (size_t i = 0; i < solutions.size(); i++) {
        std::cout << "\nSolution " << i + 1 << ":\n";
        for (const auto& row : solutions[i]) {
            std::cout << row << "\n";
        }
    }
    
    return 0;
}


public class NQueens
{
    private bool IsSafe(char[][] board, int row, int col, int n)
    {
        // Check row on left side
        for (int j = 0; j < col; j++)
            if (board[row][j] == 'Q') return false;
        
        // Check upper diagonal
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
            if (board[i][j] == 'Q') return false;
        
        // Check lower diagonal
        for (int i = row, j = col; i < n && j >= 0; i++, j--)
            if (board[i][j] == 'Q') return false;
        
        return true;
    }
    
    private void Backtrack(IList<IList<string>> solutions, char[][] board, int col, int n)
    {
        if (col == n)
        {
            solutions.Add(board.Select(row => new string(row)).ToList());
            return;
        }
        
        for (int row = 0; row < n; row++)
        {
            if (IsSafe(board, row, col, n))
            {
                board[row][col] = 'Q';
                Backtrack(solutions, board, col + 1, n);
                board[row][col] = '.';
            }
        }
    }
    
    public IList<IList<string>> Solve(int n)
    {
        var solutions = new List<IList<string>>();
        var board = new char[n][];
        
        for (int i = 0; i < n; i++)
            board[i] = new string('.', n).ToCharArray();
        
        Backtrack(solutions, board, 0, n);
        return solutions;
    }
    
    public static void Main()
    {
        var solver = new NQueens();
        int n = 4;  // Try 4x4 board
        
        var solutions = solver.Solve(n);
        
        Console.WriteLine($"Found {solutions.Count} solutions for {n}x{n} board:");
        
        for (int i = 0; i < solutions.Count; i++)
        {
            Console.WriteLine($"\nSolution {i + 1}:");
            foreach (var row in solutions[i])
                Console.WriteLine(row);
        }
    }
}

Complexity Analysis

Time Complexity

O(N!) where:

N is the size of the board
For each column, we try N rows
The branching factor reduces as we place queens

Space Complexity

O(N) where:

N is the size of the board
We need O(N) space to store the queen positions
Additional O(N) space for recursion stack

Advantages and Disadvantages

Advantages

Guaranteed to find all solutions
Memory efficient
Easy to modify for variations
Can be optimized with symmetry
Simple to implement

Disadvantages

Exponential time complexity
Not practical for large N
Many dead ends in search space
Performance depends on board size
Limited practical applications

Applications

Constraint satisfaction problems
Resource allocation problems
Circuit board testing
Parallel processing task scheduling
Game AI and puzzle solving

Quick Info

N-Queens Problem