N-Queens Problem
The N-Queens Problem asks: place N chess queens on an N×N chessboard so that no two queens threaten each other. This means no two queens can be on the same row, column, or diagonal. It's a classic constraint satisfaction problem that demonstrates backtracking, pruning, and systematic exploration of solution spaces. The problem has applications in parallel processing, resource allocation, and algorithm design education.
Visualization
Interactive visualization for N-Queens Problem
N-Queens Problem
• Classic backtracking problem
• Place N queens on N×N board
• No two queens attack each other
Interactive visualization with step-by-step execution
Implementation
1function solveNQueens(n: number): string[][] {
2 const result: string[][] = [];
3 const board: string[] = Array(n).fill('.'.repeat(n));
4
5 const isSafe = (row: number, col: number): boolean => {
6 // Check column
7 for (let i = 0; i < row; i++) {
8 if (board[i][col] === 'Q') return false;
9 }
10
11 // Check diagonal
12 for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
13 if (board[i][j] === 'Q') return false;
14 }
15
16 // Check anti-diagonal
17 for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
18 if (board[i][j] === 'Q') return false;
19 }
20
21 return true;
22 };
23
24 const backtrack = (row: number): void => {
25 if (row === n) {
26 result.push([...board]);
27 return;
28 }
29
30 for (let col = 0; col < n; col++) {
31 if (isSafe(row, col)) {
32 const oldRow = board[row];
33 board[row] = '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1);
34 backtrack(row + 1);
35 board[row] = oldRow;
36 }
37 }
38 };
39
40 backtrack(0);
41 return result;
42}Deep Dive
Theoretical Foundation
N-Queens uses backtracking to explore the solution space systematically. The algorithm places queens column by column, checking constraints at each step. For each column, it tries placing a queen in each row, checking if it's safe (not attacked by previously placed queens). If safe, it recursively tries to place queens in remaining columns. If unsuccessful, it backtracks and tries the next position. The key insight is pruning: we abandon a partial solution as soon as we detect a constraint violation, avoiding exponential exploration of invalid paths. Time complexity is roughly O(N!) but pruning reduces it significantly in practice. Solutions exist for all N≥4 (and N=1). For N=8, there are 92 solutions.
Complexity
Time
O(N!)
O(N!)
O(N!)
Space
O(N²)
Applications
Industry Use
Parallel processing - task allocation without conflicts
Network frequency assignment (avoiding interference)
Exam scheduling with constraint satisfaction
VLSI design - placing components without conflicts
Cryptography - generating permutations
Resource allocation in distributed systems
Teaching constraint satisfaction and backtracking
Puzzle generation for educational games
Use Cases
Related Algorithms
Sudoku Solver
Sudoku Solver uses backtracking to fill a 9×9 grid with digits 1-9, ensuring each row, column, and 3×3 box contains all digits exactly once. This classic constraint satisfaction problem demonstrates systematic exploration with constraint checking. The algorithm fills empty cells one by one, backtracking when constraints are violated, making it a perfect example of pruning in search algorithms.
Combination Sum
Find all unique combinations in array where chosen numbers sum to target. Numbers can be reused. Classic backtracking problem with pruning optimization.
Generate Valid Parentheses
Generate all combinations of n pairs of well-formed parentheses. Uses backtracking with constraint that closing parentheses never exceed opening ones.
Word Search in Grid
Given 2D board and word, find if word exists in grid. Word must be constructed from letters of sequentially adjacent cells (horizontally or vertically). Uses backtracking with visited tracking.