Backtracking intro · logic building guide

Backtracking — Think Like a Solver

Try → Check → Go deeper → Undo

Backtracking = DFS on a decision tree with undo.

Start

🟢

State

Where am I in the problem?

row · vertex · position

🔵

Choices

What can I try now?

column · color · next node

🟡

Constraint

Is this choice valid?

isSafe / valid()

🔴

Backtrack

Undo the last choice and try the next.

unchoose / remove

Mental formula

State

Choices

Check

Choose

Recurse

Undo

Universal pseudocode

solve(state):
    if solution found:
        output solution
        return
    for each choice:
        if not valid(choice):
            continue
        make choice
        solve(next state)
        undo choice   // restore state for next choice

Line meaning

solve(state) — start from current partial solution.

current logic step

valid path / solution

dead end / invalid choice

State space tree

Same look, better logic: DFS goes down one branch, fails or succeeds, then comes back.

current

valid/solution

dead end

explored

backtracked

DFS story

Step type

Start

Current path

Start

Partial solution

[]

Start at the root. Pick one choice and keep going deeper. If a branch fails, undo and return to the previous choice.

Root = empty/initial state

Child = one new choice added

Dead end = constraint fails

Success = full valid solution

Same pattern in DAA problems

Problem	State	Choice	Constraint
N-Queens	current row	column	queen must be safe
Graph Coloring	current vertex	color	adjacent vertices cannot match
Hamiltonian Cycle	path position	next vertex	edge must exist, vertex not repeated

When should I use backtracking?

✔ many possible arrangements

✔ decisions made step by step

✔ constraints must be satisfied

✔ wrong partial choices can be rejected early

One-line memory hack

Choose → Check → Recurse → Undo

If students remember only one thing from this page, it should be this line.

State → Choices → Check → Choose → Recurse → Undo