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
Build a complete Sudoku solver using backtracking with constraint propagation — validate placements across rows, columns, and 3×3 boxes, and backtrack on conflicts.
Problem Statement
Fill a 9×9 grid so that each row, each column, and each of the nine 3×3 sub-boxes contains all digits from 1 to 9 exactly once. Given a partially filled board (with zeros representing empty cells), find a valid completion.
Why Backtracking Works Here
Sudoku is a classic constraint satisfaction problem. At each empty cell, we try digits 1-9. Before placing a digit, we check whether it violates any constraint. If all digits 1-9 are invalid for a cell, we have reached a dead end and must backtrack to the previous cell and try its next candidate.
The key insight: constraints are checkable in O(1) per placement if we maintain sets of used digits for each row, column, and box. This fast validation combined with early backtracking makes the solver efficient despite the theoretical exponential search space.
Constraint Validation
A digit d is safe to place at position (row, col) if:
dis not already inrow→ checkrow_sets[row]dis not already incol→ checkcol_sets[col]dis not already in the 3×3 box → checkbox_sets[box_index]
The box index is computed as: box_index = (row // 3) * 3 + (col // 3)
Example
Box indices for a 9×9 grid:
0 0 0 | 1 1 1 | 2 2 2
0 0 0 | 1 1 1 | 2 2 2
0 0 0 | 1 1 1 | 2 2 2
------+-------+------
3 3 3 | 4 4 4 | 5 5 5
3 3 3 | 4 4 4 | 5 5 5
3 3 3 | 4 4 4 | 5 5 5
------+-------+------
6 6 6 | 7 7 7 | 8 8 8
6 6 6 | 7 7 7 | 8 8 8
6 6 6 | 7 7 7 | 8 8 8
Algorithm Steps
- Find the next empty cell (scanning left-to-right, top-to-bottom).
- If no empty cell exists, the puzzle is solved — return True.
- For digits 1 through 9:
a. Check if the digit is valid (not in same row, column, or box). b. If valid, place the digit and recurse to solve the rest. c. If recursion succeeds, propagate success upward. d. If recursion fails, remove the digit (backtrack) and try the next.
- If no digit works, return False (triggers backtracking in the caller).
Python Implementation
Example
def solve_sudoku(board):
def is_valid(row, col, digit):
# Check row
if digit in board[row]:
return False
# Check column
for r in range(9):
if board[r][col] == digit:
return False
# Check 3x3 box
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
if board[r][c] == digit:
return False
return True
def solve():
for row in range(9):
for col in range(9):
if board[row][col] == 0: # empty cell
for digit in range(1, 10):
if is_valid(row, col, digit):
board[row][col] = digit
if solve():
return True
board[row][col] = 0 # backtrack
return False # no valid digit, trigger backtrack
return True # all cells filled
solve()
return board
# Example puzzle (0 = empty)
puzzle = [
[5,3,0, 0,7,0, 0,0,0],
[6,0,0, 1,9,5, 0,0,0],
[0,9,8, 0,0,0, 0,6,0],
[8,0,0, 0,6,0, 0,0,3],
[4,0,0, 8,0,3, 0,0,1],
[7,0,0, 0,2,0, 0,0,6],
[0,6,0, 0,0,0, 2,8,0],
[0,0,0, 4,1,9, 0,0,5],
[0,0,0, 0,8,0, 0,7,9]
]
solve_sudoku(puzzle)
for row in puzzle:
print(row)
Optimized Version with Sets
The naive is_valid scans the row, column, and box on each call (O(9) each). Using precomputed sets reduces validation to O(1):
Example
def solve_sudoku_optimized(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empty_cells = []
# Initialize constraint sets from given digits
for r in range(9):
for c in range(9):
if board[r][c] != 0:
d = board[r][c]
rows[r].add(d)
cols[c].add(d)
boxes[(r // 3) * 3 + c // 3].add(d)
else:
empty_cells.append((r, c))
def backtrack(idx):
if idx == len(empty_cells):
return True
r, c = empty_cells[idx]
box_id = (r // 3) * 3 + c // 3
for d in range(1, 10):
if d not in rows[r] and d not in cols[c] and d not in boxes[box_id]:
board[r][c] = d
rows[r].add(d)
cols[c].add(d)
boxes[box_id].add(d)
if backtrack(idx + 1):
return True
board[r][c] = 0
rows[r].remove(d)
cols[c].remove(d)
boxes[box_id].remove(d)
return False
backtrack(0)
return board
C++ Implementation
Example
#include <vector>
#include <iostream>
using namespace std;
class SudokuSolver {
vector<vector<int>> board;
bool row_has[9][10] = {}; // row_has[r][d] = true if digit d in row r
bool col_has[9][10] = {};
bool box_has[9][10] = {};
int box_id(int r, int c) { return (r / 3) * 3 + c / 3; }
bool solve(int pos) {
// Find next empty cell starting from pos
while (pos < 81 && board[pos / 9][pos % 9] != 0) pos++;
if (pos == 81) return true;
int r = pos / 9, c = pos % 9;
for (int d = 1; d <= 9; d++) {
if (!row_has[r][d] && !col_has[c][d] && !box_has[box_id(r,c)][d]) {
board[r][c] = d;
row_has[r][d] = col_has[c][d] = box_has[box_id(r,c)][d] = true;
if (solve(pos + 1)) return true;
board[r][c] = 0;
row_has[r][d] = col_has[c][d] = box_has[box_id(r,c)][d] = false;
}
}
return false;
}
public:
void solve(vector<vector<int>>& input) {
board = input;
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++)
if (board[r][c] != 0) {
int d = board[r][c];
row_has[r][d] = col_has[c][d] = box_has[box_id(r,c)][d] = true;
}
solve(0);
input = board;
}
};
Constraint Propagation (Advanced)
Before brute-force backtracking, reduce the search space:
- Naked singles: If a cell has only one possible digit, place it immediately.
- Hidden singles: If a digit can go in only one place in a row/col/box, place it.
- Elimination: When placing a digit, eliminate it from peers' candidate lists.
This is the technique used by Peter Norvig's famous Sudoku solver. It solves most "easy" and "medium" puzzles without any backtracking at all, leaving backtracking only for the hardest cases.
Complexity Analysis
| Metric | Value | Explanation |
|---|---|---|
| Worst-case time | O(9^E) | E = number of empty cells (max 81). Each cell tries up to 9 digits. |
| Practical time | ~10,000 nodes | With constraint sets, most puzzles solve in milliseconds |
| Space | O(81) = O(1) | Fixed grid size, recursion depth ≤ 81 |
The 9^81 theoretical worst case never occurs in valid Sudoku puzzles because constraints prune the tree aggressively.
Real-World Applications
- Puzzle apps: The algorithm behind Sudoku solvers in mobile apps
- Constraint solvers: Same technique applies to scheduling, timetabling, and resource allocation
- SAT solvers: Sudoku reduces to Boolean satisfiability — industrial SAT solvers use similar backtrack-with-propagation
- Verification: Checking uniqueness of puzzles (a valid puzzle has exactly one solution)
Key Takeaways
Sudoku solving demonstrates backtracking at its most structured: fixed-size search space, easily-checkable constraints, and massive pruning potential. The pattern — find empty cell, try candidates, validate, recurse, undo — transfers directly to any constraint satisfaction problem. Precomputing constraint sets (rows/cols/boxes) transforms validation from O(N) to O(1), which makes a significant practical difference.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Sudoku Solver.
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, sudoku, solver
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.BacktrackingN-Queens ProblemSolve the classic N-Queens problem using backtracking — learn constraint checking, state-space exploration, and trace through a complete 4-Queens walkthrough.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.RecursionBacktracking with RecursionLearn backtracking techniques combined with recursion for constraint problems.