DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Solve the classic N-Queens problem using backtracking — learn constraint checking, state-space exploration, and trace through a complete 4-Queens walkthrough.
Problem Statement
Place N queens on an N×N chessboard such that no two queens attack each other. A queen attacks along its row, column, and both diagonals. For N=8, there are 92 distinct solutions — finding even one requires careful systematic search.
Building Intuition
Think of it this way: since no two queens can share a row, we must place exactly one queen per row. Our job is to decide *which column* each row's queen goes into. This transforms the problem from "place N queens anywhere on N² squares" into "assign a column to each of N rows," immediately reducing the search space from C(N²,N) to N^N, and with column-uniqueness to N!.
But N! is still large for N=8 (40,320). Backtracking prunes branches early — if placing a queen in row 3 immediately conflicts with a queen in row 1, we skip all configurations that extend from that partial placement.
Constraint Checking
Before placing a queen at position (row, col), we check three things against all previously placed queens at positions (r, c):
- Same column:
col == c— violated if any earlier queen is in the same column - Same main diagonal:
row - col == r - c— cells on the same\diagonal share the same (row - col) value - Same anti-diagonal:
row + col == r + c— cells on the same/diagonal share the same (row + col) value
We maintain three sets — columns, diag1, and diag2 — for O(1) conflict detection.
4-Queens Complete Walkthrough
Let us trace the algorithm on a 4×4 board (rows and columns numbered 0-3):
| Row 0: Try col 0 | Place Q at (0,0). cols={0}, d1={0}, d2={0} |
| Row 1: Try col 0 | CONFLICT (same col). Skip. |
| Try col 1 | CONFLICT (same diag: 1-1=0=0-0). Skip. |
| Try col 2 | OK. Place Q at (1,2). cols={0,2}, d1={0,-1}, d2={0,3} |
| Row 2: Try col 0 | CONFLICT (diag2: 2+0=2... no. diag1: 2-0=2... no. col 0 used). CONFLICT col. |
| Try col 1 | CONFLICT (diag2: 2+1=3, 3∈d2). Skip. |
| Try col 2 | CONFLICT (same col). Skip. |
| Try col 3 | CONFLICT (diag1: 2-3=-1, -1∈d1). Skip. |
| DEAD END | Backtrack, remove (1,2) |
| Try col 3 | OK. Place Q at (1,3). cols={0,3}, d1={0,-2}, d2={0,4} |
| Row 2: Try col 0 | CONFLICT (col 0 used). Skip. |
| Try col 1 | Check: col 1 free, d1=2-1=1 free, d2=2+1=3 free → OK! Place (2,1) |
| Row 3: Try col 0 | d1=3-0=3 free, d2=3+0=3... CONFLICT (3∈d2 from (1,3)? No, d2={0,4,3}). CONFLICT d2. |
| Try col 1 | CONFLICT (col 1). Skip. |
| Try col 2 | d1=3-2=1∈d1? d1={0,-2,1}. YES, CONFLICT. Skip. |
| Try col 3 | CONFLICT (col 3). Skip. |
| DEAD END | Backtrack |
| Try col 2 | d1=2-2=0∈d1? YES, CONFLICT. Skip. |
| Try col 3 | CONFLICT (col 3). Skip. |
| DEAD END | Backtrack, remove (1,3) |
| All columns exhausted for row 1 | Backtrack, remove (0,0) |
| Row 0: Try col 1 | Place Q at (0,1). cols={1}, d1={-1}, d2={1} |
| Row 1: Try col 0 | d1=1-0=1 free, d2=1+0=1 CONFLICT. Skip. |
| Try col 1 | CONFLICT col. Skip. |
| Try col 2 | d1=1-2=-1 CONFLICT. Skip. |
| Try col 3 | d1=1-3=-2 free, d2=1+3=4 free, col 3 free → OK! Place (1,3) |
| Row 2: Try col 0 | d1=2-0=2 free, d2=2+0=2 free, col 0 free → OK! Place (2,0) |
| Row 3: Try col 2 | d1=3-2=1 free, d2=3+2=5 free, col 2 free → OK! Place (3,2) |
| ✓ SOLUTION FOUND | [1, 3, 0, 2] |
The solution [1, 3, 0, 2] means: row 0 → col 1, row 1 → col 3, row 2 → col 0, row 3 → col 2.
Example
. Q . .
. . . Q
Q . . .
. . Q .
Python Implementation
Example
def solve_n_queens(n):
solutions = []
def backtrack(row, columns, diag1, diag2, placement):
if row == n:
solutions.append(placement[:])
return
for col in range(n):
if col in columns or (row - col) in diag1 or (row + col) in diag2:
continue # constraint violated, prune
# Make choice
placement.append(col)
columns.add(col)
diag1.add(row - col)
diag2.add(row + col)
# Recurse to next row
backtrack(row + 1, columns, diag1, diag2, placement)
# Undo choice (backtrack)
placement.pop()
columns.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0, set(), set(), set(), [])
return solutions
# Print all solutions for 4-Queens
for sol in solve_n_queens(4):
print(sol)
for row in range(4):
line = ['.'] * 4
line[sol[row]] = 'Q'
print(' '.join(line))
print()
C++ Implementation
Example
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;
class NQueens {
int n;
vector<vector<int>> solutions;
unordered_set<int> cols, diag1, diag2;
public:
vector<vector<int>> solve(int size) {
n = size;
vector<int> placement;
backtrack(0, placement);
return solutions;
}
private:
void backtrack(int row, vector<int>& placement) {
if (row == n) {
solutions.push_back(placement);
return;
}
for (int col = 0; col < n; col++) {
if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col))
continue;
cols.insert(col);
diag1.insert(row - col);
diag2.insert(row + col);
placement.push_back(col);
backtrack(row + 1, placement);
placement.pop_back();
cols.erase(col);
diag1.erase(row - col);
diag2.erase(row + col);
}
}
};
int main() {
NQueens solver;
auto solutions = solver.solve(8);
cout << "Total 8-Queens solutions: " << solutions.size() << endl; // 92
}
Complexity Analysis
| Metric | Value | Explanation |
|---|---|---|
| Time complexity | O(N!) | At most N choices for row 0, N-1 for row 1, etc. Pruning reduces this significantly. |
| Space complexity | O(N) | Recursion depth is N; three sets store at most N entries each |
| Solutions for N=8 | 92 | Nodes explored ≈ 15,000 (vs 40,320 without diagonal pruning) |
Optimization: Bitmask Approach
For competitive programming, bitmasking avoids hash set overhead:
python example
def n_queens_bitmask(n):
count = 0
def solve(row, cols, d1, d2):
nonlocal count
if row == n:
count += 1
return
available = ((1 << n) - 1) & ~(cols | d1 | d2)
while available:
pos = available & (-available) # lowest set bit
available ^= pos
solve(row + 1, cols | pos, (d1 | pos) << 1, (d2 | pos) >> 1)
solve(0, 0, 0, 0)
return count
print(n_queens_bitmask(12)) # 14200, runs very fastReal-World Applications
- VLSI design: Placing components without interference follows similar constraint logic
- Parallel computing: Task scheduling where processes cannot share certain resources
- Telecommunications: Frequency assignment to avoid interference
- Testing and QA: Generating non-conflicting test configurations
Key Takeaways
The N-Queens problem beautifully illustrates how backtracking transforms an exponential brute-force search into a manageable computation. The keys are: reduce each decision to one row at a time, check constraints in O(1) using sets or bitmasks, and backtrack immediately upon conflict. This pattern of "constrained placement with undo" appears in dozens of interview problems.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for N-Queens Problem.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, backtracking, queens, problem
Related Data Structures & Algorithms Topics
Continue learning this concept
BacktrackingBacktracking FundamentalsMaster the backtracking algorithmic paradigm — understand state-space trees, pruning strategies, and how backtracking systematically explores solution spaces.BacktrackingBacktracking Practice ProblemsMaster essential backtracking interview problems — Word Search, Permutations, Combination Sum, and Palindrome Partitioning with detailed approaches and code.BacktrackingRat in a MazeSolve the Rat in a Maze problem using backtracking — navigate a grid, mark visited cells, backtrack on dead ends, and find all possible paths.BacktrackingSubset GenerationGenerate all subsets (power set) using backtracking and bit manipulation — understand the include/exclude pattern and enumerate 2^n possibilities efficiently.BacktrackingSudoku SolverBuild a complete Sudoku solver using backtracking with constraint propagation — validate placements across rows, columns, and 3×3 boxes, and backtrack on conflicts.Dynamic Programming0/1 Knapsack ProblemMaster the classic 0/1 Knapsack problem with 2D DP table construction, include/exclude decisions, solution traceback, and space optimization.