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

N-Queens

Constraint search through place, prune, and backtrack

Place one queen in every column

The N-Queens problem asks for N queens on an N x N board with no two sharing a row, column, or diagonal. Placing exactly one queen per column removes the column constraint and turns each recursive level into a choice of row.

Reject conflicts before recursing

Try rows from top to bottom in the current column. A square is safe when no earlier queen shares its row or diagonal. Place a queen and recurse when safe; if later columns become impossible, remove that queen and continue with the next row.

Amber marks the square under consideration, red identifies queens that attack a rejected square, and placed queens remain on the board. The trace stops after finding one solution for the 4 by 4 instance.

Start with an empty board and place one queen in each column from left to right.

1function solveNQueens(n: number): number[] {
2 const queens: number[] = Array(n).fill(-1);
3 const safe = (row: number, col: number): boolean => {
4 for (let c = 0; c < col; c++)
5 if (queens[c] === row ||
6 Math.abs(queens[c] - row) === Math.abs(c - col))
7 return false;
8 return true;
9 };
10 const solve = (col: number): boolean => {
11 if (col === n) return true;
12 for (let row = 0; row < n; row++) {
13 if (safe(row, col)) {
14 queens[col] = row;
15 if (solve(col + 1)) return true;
16 queens[col] = -1;
17 }
18 }
19 return false;
20 };
21 solve(0);
22 return queens;
23}
Board4×4
Placed queens-
1 / 32

Search cost depends on pruning

The worst-case search is commonly bounded by O(N!) after enforcing one queen per row and column, with O(N) recursion depth. Constant-time row and diagonal sets make conflict checks faster for larger boards.

Backtracking maintains one partial assignment, rejects impossible extensions early, and restores the previous state before trying another choice.

See the same depth-first choose-and-undo pattern without constraints in Subsets.