Interactive Lab · DSA & Algorithms

Try a choice, hit a wall, back up and try again, backtracking, with queens

A huge chunk of hard interview questions, sudoku, word search, permutations, the classic N-queensare all one technique: backtracking. It's brute force with a brain: place one piece at a time, and the instant the board can't possibly work out, undo the last move and try the next option instead of blindly exploring a doomed branch. Here we place a queen in every column so that no two share a row or a diagonal. Watch a queen go down, get attacked, back up, and eventually lock into a safe arrangement. Scrub every try, conflict, and backtrack.

🎬 Watch the 100-second explainer, then step through the search yourself below ↓

▶ The playground, one queen per column, top-to-bottom, undo on a dead end

Queens go in column by column. Each step tries the next row: if the cell is safe the queen stays and we move to the next column; if it's attacked (a red line shows the attacker, same row or diagonal) we try the next row; if a whole column has no safe row, we backtrackpull the previous queen and move it on.

step 0 / 0

🧭 Where this fits

Backtracking is the engine inside SAT solvers (which verify chips and find software bugs), SQL query planners exploring join orders, regex engines, sudoku apps, and dependency resolvers (pip, cargo). The prune-the-doomed-branch move you just watched is the difference between 'runs forever' and 'solves in milliseconds' across all of them.

The code that's actually running, safe? place : try the next; dead end? undo

🔮 Predict, then test

Drag to the end: the four queens settle into rows 1, 3, 0, 2none can attack another. Predict: before it finds that, the search hits four dead ends and backs up (watch the amber ↩ steps). The magic is what backtracking skips: the moment a column has no safe row, it abandons that entire branch instead of filling the rest of the board pointlessly. If brute force would try every one of the Nᶜ board fillings, why does pruning a branch the instant it's doomed save so enormously much, and where else (sudoku, a maze, generating permutations) is this the exact same move?

The takeaway

Your new mental model of backtracking

Choose → explore → un-choose. Make one move, recurse on the smaller problem, and if it fails, undo the move and try the next option. That single "undo" is the whole idea.
Prune early, save everything. The power isn't in trying combinations, it's in not trying them. Kill a branch the instant it's invalid and you skip every arrangement underneath it, turning an impossible Nᶜ into something tractable.
The check is the constraint. Here "safe" = no shared row or diagonal; in sudoku it's row/col/box; in a maze it's "in bounds and not a wall." Same skeleton, different is_valid.
It's DFS with a state you mutate and restore. You dive down one path (place a queen), and on the way back up you clean up (remove it) so the next sibling starts fresh. Place, recurse, pop.
You didn't memorize "backtracking"you watched a queen back out of a dead-end column and the search re-route to the answer.

← Recursion Placement prep →Try: BFS vs DFS