algorithms.live
    DSA
    advanced

    Backtracking (N-Queens)

    Software Engineer path · lesson 40 of 99
    time O(N!)
    space O(N²)
    Board size n

    n = 3 has no solution: watch the search prove it.

    Stop at
    0123401234
    TryingJust placedQueenAttack

    Place 5 queens on a 5×5 board, one per row, so none attack each other.

    Code (running line highlighted)
    1. 1place(row):
    2. 2 if row == n: record a solution
    3. 3 for col in 0..n-1:
    4. 4 if no queen shares col or a diagonal with (row, col):
    5. 5 put a queen at (row, col); place(row + 1)
    6. 6 remove it # backtrack
    Placements tried
    0 / 15
    Backtracks
    0 / 0
    Invariant: Queens in rows above the current one never attack each other.

    Solutions found: 0

    Tap any element in the diagram to inspect its state at this step.

    1 / 18

    Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.

    N-Queens

    Sequence

    Order the steps of the backtracking search.

    Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.

    1. 1Drop a step here
    2. 2Drop a step here
    3. 3Drop a step here
    4. 4Drop a step here
    5. 5Drop a step here
    5 pieces left to place

    Test your knowledge

    20 questions
    Question 1 of 20
    Score: 0

    What distinguishes Backtracking from Brute Force?

    Write the code

    Runs your solution

    Permutations

    Given an array `nums` of distinct integers, return all the possible permutations.

    Example Cases

    Input:[1,2,3]
    Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    Input:[0,1]
    Output:[[0,1],[1,0]]
    javascript
    function permute(nums) {
  // Your code here
}

    The short version

    Think of trying to solve a Sudoku puzzle. You fill in a number. If it works, you move to the next square. If you get stuck later, you erase your last move and try a different number.

    In more depth

    Try and Undo

    Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally.

    The Strategy:

    1.Choose: Make a choice (add a number).
    2.Explore: Recurse to the next step.
    3.Un-Choose (Backtrack): Undo the choice (remove the number) and try the next option.

    Pruning:

    Crucially, if a partial solution cannot possibly be completed to a valid solution, we abandon it immediately (prune the tree), saving huge amounts of time compared to pure Brute Force.

    When to reach for this

    • Find **ALL** solutions (Permutations, Combinations, Subsets)
    • Solving puzzles (Sudoku, N-Queens)
    • Constraint satisfaction problems

    Interview Questions

    LinkedIn
    Netflix
    Amazon
    Uber
    Two Sigma
    Microsoft
    Airbnb
    Bloomberg
    Google
    Facebook
    Palantir

    References & Further Reading

    N Queens Problem using BacktrackingYouTube · Abdul Bari
    video
    BacktrackingWikipedia
    article
    Eight queens puzzleWikipedia
    article
    All Data Structures & Algorithms topics

    Love this visualization?

    Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.

    100% free • No credit card required