DSAverse
Backtracking
Loading Backtracking...
N-Queens Board
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Backtracking
Loading Backtracking...
N-Queens Board
Explore every possibility — but prune dead ends early. Backtracking is a systematic trial-and-error approach that finds solutions by building candidates incrementally.
The core backtracking loop: make a choice, recurse into it, then undo the choice if it leads to a dead end.
Early constraint checks avoid exploring entire subtrees that cannot lead to valid solutions — the difference between feasibility and infeasibility.
Backtracking guarantees finding all valid solutions (or proving none exist), making it ideal for constraint satisfaction problems.
Watch the algorithm explore, backtrack, and find solutions in real time
Place N queens on an N×N chessboard so no two attack each other. Backtracking places queens row by row, pruning columns and diagonals that would cause conflicts.
O(n!)O(n²)Find a word in a 2D character grid by exploring all four directions from each cell. Backtracking un-marks visited cells when a path fails, enabling complete search.
O(m×n×4^L)O(L)Navigate a rat from the top-left to bottom-right of a binary maze grid. Backtracking explores all paths, marking cells visited and unmarking them when a dead end is hit.
O(2^(n²))O(n²)The foundation of constraint satisfaction, puzzles, and combinatorial search
Sudoku, crossword generation, scheduling, and register allocation all reduce to backtracking over constrained variables.
Minimax search, chess engine move generation, and puzzle solvers are all forms of backtracking with constraint pruning.
Generating permutations, subsets, and combinations systematically is the cleanest application of the choose-explore-unchoose pattern.