V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Sudoku Solver

Try legal digits in an empty cell, propagate row-column-box constraints, and backtrack from contradictions.

Core idea

Select an empty cell, try digits that do not appear in its row, column, or box, and recurse. A contradiction proves the latest choice must be undone.

Read the visualization

The active cell highlights every rejected digit and accepted placement. Backtracking removes a tentative value, while fixed clues remain visually distinct throughout the search.

2
3
4
3
4
1
2
2
4
2
3

Load the puzzle and identify the empty cells that require choices.

1function solveSudoku(grid: number[][], n: number, box: number): boolean {
2 const valid = (r: number, c: number, v: number): boolean => {
3 for (let i = 0; i < n; i++)
4 if (grid[r][i] === v || grid[i][c] === v) return false;
5 const br = Math.floor(r / box) * box, bc = Math.floor(c / box) * box;
6 for (let i = br; i < br + box; i++)
7 for (let j = bc; j < bc + box; j++)
8 if (grid[i][j] === v) return false;
9 return true;
10 };
11 for (let r = 0; r < n; r++)
12 for (let c = 0; c < n; c++)
13 if (grid[r][c] === 0) { // init to one empty cell
14 for (let v = 1; v <= n; v++) {
15 if (valid(r, c, v)) { // reject → reject; invalid → reject down one
16 grid[r][c] = v; // place
17 if (solveSudoku(grid, n, box)) return true;
18 grid[r][c] = 0; // backtrack not backtrack → backtrack, return backtrack
19 }
20 }
21 return false; // 1..n done not done → done
22 }
23 return true; // done empty cell → complete
24}
board4×4(2×2 box)
current cell-
filled empty cell0 / 5
1 / 22

Complexity and tradeoffs

Time: Worst O(9^m). Space: O(m). Constraint checks and good cell ordering drastically reduce the search below the m-empty-cell bound.

Invariant: Every placed digit satisfies all three local constraint sets, so only future cells can make a partial board impossible.

Where it fits

Sudoku is a compact constraint-satisfaction example. Bit masks, most-constrained-cell ordering, and exact cover dramatically reduce the practical search.