3.7.16
Backtracking systematic brute force hai jo jaldi give up kar deta hai . Tum ek solution ko ek
decision at a time build karte ho. Har step pe tum poochte ho: "Kya yeh partial choice kabhi bhi
ek valid full solution tak pahunch sakti hai?" Agar nahi , tum us puri branch ko abandon
(prune) kar dete ho aur apna last choice undo karte ho (backtrack ). Agar shayad, tum aur
gehre jaate ho.
YEH KYUN KAAM KARTA HAI: saare decision sequences ka set ek tree banata hai. Ek buri
partial choice us ke neeche ke har leaf ko kharab kar deti hai, isliye us subtree ki root ko
katna ek baar mein exponentially bahut saare dead-ends ko khatam kar deta hai. Yahi poora fayda
hai.
Definition State-space treeEk tree jahan:
root = empty partial solution,har edge = ek decision (jaise "queen ko column 3 mein rakho", "item 4 include karo"),
har node = ab tak bani partial solution,
leaves = complete solutions (ya dead-ends).
Search is tree ko Depth-First order mein explore karta hai.
Definition Key vocabulary
Candidate : ek node pe partial solution.Feasible / promising node : woh jo valid full solution tak extend ho sakta hai.Pruning : ek non-promising node ko expand karne se mana karna (uska subtree kaatna).Backtrack : last decision undo karo aur agla sibling try karo.
PRUNING ke liye KYA chahiye: ek fast bounding / feasibility test isValid(state) jo
false return kare jab bhi partial solution already ek constraint violate kar chuki ho.
Hum saare solutions chahte hain. "Solution kya hai?" se shuru karo — choices ka ek sequence
c 1 , c 2 , … , c n recurse karte
hain:
def backtrack (state): if is_complete(state): record(state) return for choice in candidates(state): if is_valid(state, choice): # <-- PRUNE here, before going deeper state.add(choice) # make the move backtrack(state) # explore state.remove(choice) # UNDO = backtrack
Intuition "make / explore / undo" rhythmEk hi state object poore tree ke liye reuse hota hai. KAISE hum isse correct rakhte
hain: har add ko recursion ke baad ek remove se match karna zaroori hai, taaki jab control
parent ke paas wapas aaye to state bilkul waisi hi ho jaise thi. Undo bhoolna = siblings ko
corrupt karna.
4 × 4 ek queen per row decide
karte hain, uska column choose karte hue.
State = list col[] jahan col[r] = row r mein queen ka column.
Validity test — row r, column c mein rakha jaane ke waqt, saare pehle ke rows i<r
check karo:
same column? c = col [ i ]
same diagonal? ∣ r − i ∣ = ∣ c − col [ i ] ∣
Worked example Prune trace karnaRow 0: col 0 pe rakho → [0].
Row 1: col 0 ✗ (same col), col 1 ✗ (diagonal, ∣1 − 0∣ = ∣1 − 0∣ [0,2].
Yeh step kyun? Humne col 0 aur col 1 ko turant reject kiya — humne poore subtrees kabhi
explore hi nahi kiye jahan row-1-queen wahan baithe. Yahi depth 1 pe ~aadhe tree ki pruning
hai.
Row 2: col 0 ✗(col), 1✗(diag from 2), 2✗(col), 3✗(diag) → dead end, backtrack .
Row 1 pe wapas jao, col 3 try karo → [0,3]. Jaari rakho… eventually [1,3,0,2] ek full
solution hai.
Brute force = 4 4 = 256
[2, 4, 6, 8] ka ek subset choose karo jo 6 sum kare. Har element ke liye decision: include
ya exclude .
Worked example Bound se pruningState running_sum carry karta hai.
Prune rule: agar running_sum > target, ruko — aur add karne se yeh sirf badhega.
2 include karo (sum 2). 4 include karo (sum 6) ✓ → {2,4} record karo.
Yeh step kyun? {2,4} ke 6 hit karne ke baad, hum baad ke elements ko exclude karna
abhi bhi explore karte hain, lekin koi bhi branch jo sum ko 6 se aage push kare, use instantly
kaat diya jaata hai.Branch "2 include, 4 include, 6 include" → sum 12 > 6 → aur recurse karne se pehle prune.
sum > target check ek O ( 2 n )
Backtracking = decision tree pe DFS + ek early isValid test . In do lines ko master
karo aur tum N-Queens, Sudoku, permutations, subsets, graph coloring, word search likh sakte
ho. Problem-to-problem sirf candidates() aur is_valid() badalta hai.
Complexity (forecast-then-verify): pruning ke bina, tree mein b d b d worst case improve nahi kar sakti (ek adversarial input
kuch bhi prune na kare) lekin average case ko dramatically slash karti hai. Isliye Big-O
O ( b d )
Common mistake "Main validity leaf pe check karunga, har step pe nahi."Kyun sahi lagta hai: "Mujhe sirf yeh dekhna hai ki complete solution valid hai ya nahi,
isliye sirf end pe test karo." Logically yeh sahi hai — same answers. Kyun yeh practice mein
galat hai: tum poora b d Fix:
test utni jaldi karo jitni jaldi violation detectable ho — us sabse uche node pe prune karo
jahan constraint already fail ho rahi ho.
Common mistake "Main move undo karna bhool gaya."Kyun sahi lagta hai: recursion "return" karti hai, to surely woh clean up kar leti hai?
Nahi — tumne ek shared state mutate ki. Fix: har state.add(x) ke baad recursive
call ke baad state.remove(x) bracketed hona chahiye. Symmetry non-negotiable hai.
Common mistake "Pruning worst-case Big-O improve karti hai."Kyun sahi lagta hai: real inputs pe yeh clearly faster hai. Fix: worst case ek input
kuch bhi prune nahi karta → phir bhi O ( b d ) average/typical case mein help
karti hai, asymptotic bound mein nahi.
Common mistake Backtracking ko plain DFS se confuse karna.Kyun sahi lagta hai: dono DFS hain. Fix: backtracking add karta hai prune + explicit
undo ek mutable state ko branches mein reuse karne ke liye; yeh ek implicit solution tree pe
DFS hai.
Recall Feynman: ek 12-saal ke bacche ko explain karoSocho ek darwaazon ka maze hai. Tum aage chalte ho ek ek darwaza kholte hue. Jis pal ek
hallway ek deewar se takraati hai, tum aur bhatkate nahi — tum wapas last darwaze tak
chalte ho aur ek alag ko try karte ho. Smart baat: agar tum ek sign dekhte ho jisme likha hai
"is poore wing mein koi exit nahi", tum poora wing skip kar dete ho har kamra check karne ke
bajaay. Woh sign-reading pruning hai; wapas chalna backtracking hai.
Mnemonic Rhythm yaad rakho"CHOOSE → EXPLORE → UN-CHOOSE, aur un-PROMISING ko PRUNE karo."
Ya: D-V-U = D ecide, V alidate(prune), U ndo.
State-space tree kya hota hai? Ek tree jiska root empty partial solution hai, edges individual decisions hain, nodes partial solutions hain, aur leaves complete solutions ya dead-ends hain; DFS ke zariye explore kiya jaata hai.
Backtracking mein "pruning" ka kya matlab hai? Ek non-promising node ko expand karne se mana karna — uska poora subtree kaatna — kyunki partial solution already ek constraint violate kar chuki hai.
is_valid ko recurse karne se PEHLE kyun check karna chahiye, leaf pe nahi?Taaki invalid partial choices ke poore subtrees kabhi generate hi na hon, brute force ko early-abandon search mein badal kar.
Backtracking loop body kaunse teen operations se banta hai? Move banao (add), recurse karo (explore), move undo karo (remove/backtrack).
"Undo" step essential kyun hai? Ek hi mutable state saari branches mein shared hai; undo ke bina, sibling/parent states corrupt ho jaati hain.
Kya pruning worst-case Big-O improve karti hai? Nahi — ek adversarial input kuch bhi prune nahi kar sakta, O(b^d) rehta hai. Yeh sirf average/typical runtime improve karti hai.
N-Queens: row r, col c pe queen rakhne ka validity test kya hai? Har pehle ke row i<r ke liye: c != col[i] (column) AUR |r-i| != |c-col[i]| (diagonal).
Plain DFS aur backtracking mein kya fark hai? Backtracking ek implicit solution tree pe DFS hai jisme early feasibility prune aur explicit state undo add hota hai ek state reuse karne ke liye.
"Promising/feasible" node kya hota hai? Ek partial solution jo ab bhi ek valid complete solution mein extend ho sakti hai.
Subset-sum mein ek accha pruning rule kya hai? Agar running_sum > target, expand karna band karo — aur elements add karne se sum sirf badhega.
Recursion — backtracking recursion hai state mutation + undo ke saath.Depth-First-Search — state-space tree ka traversal order.Branch-and-Bound — backtracking + optimization ke liye prune karne ka numeric bound.Dynamic-Programming — jab subtrees overlap karein, re-explore karne ki bajay memoize karo.N-Queens · Sudoku-Solver · Permutations-and-Combinations — canonical applications.Time-Complexity — kyun pruning average case mein help karti hai worst case mein nahi.
Complete solution or dead-end
