Worked examples — Backtracking — state-space tree, pruning

3.7.16 · D3 · Coding › Algorithm Paradigms › Backtracking — state-space tree, pruning

Yeh page Backtracking — state-space tree, pruning ka exhaustive drill room hai. Parent note ne tumhe rhythm di thi (CHOOSE → EXPLORE → UN-CHOOSE) aur pruning ka idea diya tha. Yahan hum har tarah ke case cover karte hain jo ek backtracking problem exam ya interview mein throw kar sakti hai, taaki koi bhi scenario tumhe surprise na kare.

---

Scenario matrix

Har backtracking problem in cells mein se ek (ya zyada) mein rehti hai. Last column us worked example ka naam deta hai jo use cover karta hai.

Cell	Case class	Kya tricky banata hai	Covered by
A	Solution exists, backtracks ke baad mila	dead-ends aate hain success se pehle	Ex 1 (N-Queens n=4)
B	Koi solution nahi	tree fully explored, kuch record nahi	Ex 2 (N-Queens n=3)
C	Degenerate: empty input	base case immediately fire karta hai	Ex 3 (subsets of [])
D	Degenerate: target impossible	prune sab kuch kill kar deta hai	Ex 4 (subset-sum target 100)
E	SAARE solutions count karo	pehle pe mat ruko; counter chalate raho	Ex 5 (all subsets sum=6)
F	Pruning kuch nahi karta (worst case)	adversarial input, full $b^d$	Ex 6 (permutations, no constraint)
G	Pruning sab kuch karta hai (root pe bound)	ek check poora tree kill karta hai	Ex 7 (subset-sum, all too big)
H	Real-world word problem	words → candidates + isValid translate karo	Ex 8 (assign tasks)
I	Exam twist: "count nodes visited"	tree ke baare mein socho, answer ke baare mein nahi	Ex 9 (node-count analysis)
J	EK solution dhundho, turant ruko	pehle hit pe poori recursion upar return karo	Ex 10 (first subset sum=6)

Hum deep-dive prerequisites link karte hain jahan help milti hai: Recursion, Depth-First-Search, N-Queens, Permutations-and-Combinations, Time-Complexity, Branch-and-Bound.

---

Ex 1 — Cell A: N-Queens n=4, backtracks ke baad solution

Attack test precisely define karte hain, kyunki sab kuch usi pe depend karta hai.

Neeche ki figure row 0, column 1 pe ek akela queen plant karti hai aur har square paint karti hai jise woh attack karta hai: orange squares uska column share karte hain, red squares $|r-i|=|c-\text{col}[i]|$ satisfy karte hain aur diagonal pe hote hain. Ek red square pe apni ungali rakho — kaho row 2, column 3 — aur confirm karo $|2-0|=2=|3-1|$. Yahi woh equality hai jo hamara test check karta hai; picture test ko visible banati hai.

Steps (columns 0..3 numbered):

1. Row 0 → col 0. State [0]. Yeh step kyun? Hum hamesha columns left-to-right try karte hain; col 0 ke liye koi earlier row conflict nahi hai, isliye yeh trivially valid hai.

2. Row 1: col 0 ✗ (same column as row 0). col 1 ✗ (diagonal: $|1-0|=|1-0|$). col 2 ✓ → [0,2]. Yeh step kyun? Humne cols 0 aur 1 ko recurse karne se pehle prune kiya — unke poore subtrees (rows 2 aur 3 unke neeche) kabhi build nahi hote.

3. Row 2: do earlier queens ke against har column test karo — row 0 col 0 aur row 1 col 2.

   • col 0 ✗ — row 0 ke saath same column.
   • col 1 ✗ — row 1 col 2 se diagonal: $|2-1|=|1-2|=1$.
   • col 2 ✗ — row 1 ke saath same column.
   • col 3 ✗ — row 1 col 2 se diagonal: $|2-1|=|3-2|=1$ (row 0 col 0 ke against theek hai, kyunki $|2-0|=2$ lekin $|3-0|=3$).

   Koi column survive nahi karta → dead end → backtrack. Yeh step kyun? Koi column saari constraints pass nahi karta, isliye yeh node ek dead-end leaf hai. Hum row-1 ka choice undo karte hain aur uska next sibling try karte hain.

4. Row 1 pe wapas, col 3 try karo → [0,3]. Row 2: col 1 ✓ → [0,3,1]. Row 3: koi valid col nahi → dead end → phir backtrack. Yeh step kyun? Dikhata hai ki jab poora sub-branch fail hota hai toh backtracking do levels upar jaati hai.

5. Aakhirkar search [1,3,0,2] aur [2,0,3,1] tak pahunchi — yahi do full solutions hain.

Agli figure dono finished boards side by side dikhati hai. Notice karo ki har ek mein koi bhi do blue queens row share nahi karti (construction se ek per row), column (vertical-alignment check), ya diagonal ($|r-i|=|c-\text{col}[i]|$ check) — yahi "no two attacking" aisa dikhta hai jab search succeed hoti hai.

Verify: Do boards hain [1,3,0,2] aur [2,0,3,1]. [1,3,0,2] haath se check karo: columns {1,3,0,2} saare distinct hain ✓; rows $(0,1)$ pe diagonal test deta hai $|0-1|=1$ lekin $|1-3|=2$, toh yeh alag hain ✓. Saare chhe row-pairs pe yahi repeat karne pe koi conflict nahi milta. Answer: 2 solutions.

---

Ex 2 — Cell B: N-Queens n=3, KOI solution NAHI

Steps:

1. Row 0 → col 0 → [0].
2. Row 1: col 0 ✗(col), col 1 ✗(diag), col 2 ✓ → [0,2]. Yeh step kyun? Sirf col 2 survive karta hai — pruning ne humein already ek path pe narrow kar diya.
3. Row 2: col 0 ✗(col=row0), col 1 ✗(row1 col2 se diag: $|2-1|=|1-2|$), col 2 ✗(col=row1). Dead end. Row 1 pe backtrack karo — aur columns nahi. Row 0 pe backtrack karo.
4. Row 0 → col 1 → [1]. Row 1: col 0 ✗(diag), col 1 ✗(col), col 2 ✗(diag). Turant dead end. Yeh step kyun? Center-start dono neighbours ko diagonal se poison karta hai — pruning row 1 ko poori tarah kill kar deta hai.
5. Row 0 → col 2 → col-0 case ka mirror, woh bhi fail.
6. Teeno starting columns exhaust ho gaye → kuch record nahi → 0 solutions.

Verify: Search zero solutions record karta hai. Yeh "empty result" case hai — algorithm correctly terminate hoti hai, yeh prove karke ki koi arrangement kaam nahi karti. Answer: 0 solutions. (Machine-checked: koi valid [c0,c1,c2] permutation exist nahi karti.)

---

Ex 3 — Cell C: EMPTY list ke subsets

Steps:

1. Empty list ke liye, len(list) = 0, isliye root pe i = 0 = len(list) aur is_complete immediately true hai — koi decisions lene hi nahi hain. Yeh step kyun? Kisi bhi recursion ka base case (dekho Recursion) degenerate input hota hai; yahan yeh kisi bhi branching se pehle fire karta hai.
2. record(state) empty partial solution pe ek baar fire karta hai.

Verify: size $n$ ke set ke subsets ki sankhya $2^n$ hai; $n=0$ ke liye, $2^0=1$ — empty subset $\{\}$ khud. Answer: 1 subset (the empty set). Ek common bug hai 0 subsets return karna; sahi count 1 hai.

---

Ex 4 — Cell D: impossible target ke saath subset-sum

Steps:

1. Root pe, running_sum = 0, remaining_total = 2+4+6+8 = 20, target = 100.
2. Bound test: $0+20=20<100$ → root pe prune. Ek bhi element examine karne se pehle poora tree cut ho jaata hai. Yeh step kyun? Ek arithmetic comparison se $2^4=16$ saare leaves explore karne ki zaroorat khatam ho jaati hai.

Verify: Maximum reachable sum $=20<100$, isliye 0 subsets 100 sum karte hain, aur search essentially 1 node visit karta hai. Answer: 0 subsets.

---

Ex 5 — Cell E: 6 sum karne wale SAARE subsets count karo

Steps:

1. 2 include karo (sum 2). 4 include karo (sum 6) ✓ → {2,4} record karo. Ab 6, 8 ko exclude/include try karo — koi bhi inclusion sum ko 6 se aage push karta hai, running_sum > target se pruned. Yeh step kyun? Hum pehle hit pe nahi rukते — Cell E saare solutions chahta hai, isliye counter chalate rehte hain aur DFS continue karte hain.
2. Backtrack: 2 include karo, 4 exclude karo, phir 6 include karo → sum 8 > 6 ✗ pruned; 8 include karo → 10 ✗. Is branch pe koi solution nahi. Yeh step kyun? {2,4} record karne ke baad, undo step running_sum ko wapas 2 pe restore karta hai taaki hum honestly exclude-4 sibling explore kar sakein — yeh dikhata hai kyun "undo" sibling branches ko correct rakhta hai.
3. 2 exclude karo: 4 include karo → 4, 6 include karo → 10 ✗ …; single-element {6} → sum 6 ✓ → {6} record karo. Yeh step kyun? 2 exclude karna woh branch kholta hai jahan 6 akele target hit karta hai.
4. Baaki saare branches overshoot ya undershoot karte hain.

Verify: Solutions hain {2,4} aur {6} → 2 subsets. ({2,4}→6 ✓, {6}→6 ✓; [2,4,6,8] ka koi aur subset 6 sum nahi karta.) Answer: 2.

---

Ex 6 — Cell F: permutations, pruning KUCH NAHI karta (worst case)

Steps:

1. State = ab tak bana permutation; candidates = unused elements. is_valid = "already used nahi" — lekin wahi ek rule hai, aur yeh kabhi partial prefix ko hopeless prune nahi karne deta (har partial permutation ek full mein extend hoti hai). Yeh step kyun? Pruning ke liye yeh adversarial case hai: leaves se pehle koi dead-ends nahi. Dekho Permutations-and-Combinations.
2. Depth 0: 3 choices. Depth 1: 2 remaining. Depth 2: 1 remaining. Har path ek valid leaf tak pahunchti hai. Yeh step kyun? Hum branching enumerate karte hain yeh dikhane ke liye ki tree complete hai — koi prune kabhi fire nahi karta. Koi prefix kyun kabhi hopeless nahi hota: sirf constraint "distinct elements" hai, aur distinct elements ka koi bhi prefix hamesha baaki (abhi bhi distinct) elements ko kisi bhi order mein append karke finish ho sakta hai. Koi aise partial arrangement nahi hai jisse valid completion impossible ho, isliye kuch early cut nahi ho sakta.

Verify: 3 distinct items ke permutations ki sankhya $=3!=6$, aur visited leaves ki sankhya 6 equals hai — pruning ne kuch nahi bachaya. Isliye parent note warn karta hai: worst-case Big-O $O(b^d)$ rehta hai. Dekho Time-Complexity. Answer: 6 permutations.

---

Ex 7 — Cell G: pruning SABA KUCH karta hai (bound root pe cut karta hai)

Steps:

1. running_sum > target prune: jis pal hum koi bhi element include karte hain, sum $\ge 10>5$ → woh "include" branch turant mar jaata hai. Yeh step kyun? Har "include" child instantly pruned hoti hai; sirf all-exclude path survive karta hai.
2. Empty subset sum 0 deta hai, jo 5 nahi hai → koi solution record nahi.

Recall Ex 7 ke liye exact node count (include-first, prune when sum>target)

[10,12,14] ke include/exclude tree ko walk karo:

• Root (sum 0) — node 1.
• 10 include karo → sum 10 > 5 → pruned, child create nahi hoti.
• 10 exclude karo → sum 0 — node 2.
  • 12 include karo → sum 12 > 5 → pruned.
  • 12 exclude karo → sum 0 — node 3.
    • 14 include karo → sum 14 > 5 → pruned.
    • 14 exclude karo → sum 0, leaf — node 4. Toh exactly 4 nodes visit hote hain (full unpruned tree mein $1+2+4+8=15$ hote), aur 0 leaves target 5 hit karte hain.

Verify: Koi nonempty subset $\le 5$ nahi; empty subset 0 sum karta hai ≠ 5 → 0 subsets, aur exactly 4 nodes visit hote hain $2^3=8$ leaves / 15 total nodes ki jagah. Answer: 0 subsets, 4 nodes.

---

Ex 8 — Cell H: real-world word problem (task assignment)

Backtracking mein translate karo:

• Worker r pe Candidates = abhi tak assign nahi ki gayi jobs.
• is_valid = forbidden-pair rules: W2↔A reject karo, W3↔C reject karo.

Steps (W1, W2, W3 order mein assign karo):

1. W1 = A. Phir W2 ∈ {B,C}, W3 ko last milti hai.
   • W2 = B → W3 = C ✗ (W3 C nahi kar sakta) → dead end, backtrack.
   • W2 = C → W3 = B ✓ → (A,C,B) record karo. Yeh step kyun? W3–C ban (A,B,·) branch ko finish hone se pehle prune karta hai.
2. W1 = B. W2 ∈ {A,C}; W2=A ✗ (ban) pruned. W2 = C → W3 = A ✓ → (B,C,A) record karo. Yeh step kyun? W2–A ban depth 1 pe poora subtree prune karta hai.
3. W1 = C. W2 ∈ {A,B}; W2=A ✗ pruned. W2 = B → W3 = A ✓ → (C,B,A) record karo.

Verify: Valid assignments = (A,C,B), (B,C,A), (C,B,A) → 3 assignments. Brute force se cross-check: 6 permutations mein se, W2=A ya W3=C wale hata do, exactly yahi teen bachte hain. Answer: 3.

---

Ex 9 — Cell I: exam twist — NODES visited count karo

Steps — tree walk karo, pruned children mark karo (pruned child create nahi hoti, isliye count nahi):

1. Root (sum 0). node 1.
2. 3 include karo (sum 3) — node 2.
   • 3 include karo (sum 6) — node 3. 3 include karo (sum 9 > 6 → pruned, child create nahi hoti). 3 exclude karo (sum 6, leaf) — node 4.
   • 3 exclude karo (sum 3) — node 5. 3 include karo (sum 6, leaf) — node 6. 3 exclude karo (sum 3, leaf) — node 7.
3. 3 exclude karo (sum 0) — node 8.
   • 3 include karo (sum 3) — node 9. 3 include karo (sum 6, leaf) — node 10. 3 exclude karo (leaf) — node 11.
   • 3 exclude karo (sum 0) — node 12. 3 include karo (leaf) — node 13. 3 exclude karo (empty subset, leaf) — node 14. Yeh step kyun? Sirf woh do branches jo sum 9 tak push karti hain cut hoti hain; baaki sab jagah running_sum ≤ 6 hai isliye kuch aur prune nahi hota.

Verify: Full tree = 15 nodes; exactly 1 node pruned hai (node 3 ke neeche sum-9 child), 14 nodes visited bachhta hai. Recorded subsets (sum exactly 6) {3,3} hain kaafi index-combinations mein chosen — yahan 3 leaves sum 6 hit karti hain (nodes 3, 6, 10). Answer: 14 nodes visited, 3 successful leaves.

---

Ex 10 — Cell J: EK solution dhundho aur turant ruk jao

Steps:

1. 2 include karo (sum 2). 4 include karo (sum 6) ✓ → yeh ek solution hai → true return karo. Yeh step kyun? Include-first order {2,4} tak pahunchta hai {6} consider karne se pehle; pehla hit jeetta hai.
2. Woh true sidha root tak propagate hota hai — tree ka "exclude 2" wala aadha hissa (jisme {6} tha) kabhi explore nahi hota. Yeh step kyun? Short-circuiting hi Cell J ka poora point hai: humne effort sirf pehle solution ke path pe lagaya.

Verify: Pehla subset {2,4} mila (sum 6 ✓). Yeh do "include" decisions se reach hota hai, isliye search sirf leftmost spine touch karti hai — Ex 5 ke full enumeration se kaafi kam nodes. Answer: {2,4}, pehle successful leaf pe mila.

---

Matrix, filled

Recall Kis example ne kaunsa cell cover kiya?

A (backtracks ke baad solution) → Ex 1 · B (koi solution nahi) → Ex 2 · C (empty input) → Ex 3 · D (impossible target, root pe prune) → Ex 4 · E (saare count karo) → Ex 5 · F (pruning useless, worst case) → Ex 6 · G (pruning total) → Ex 7 · H (word problem) → Ex 8 · I (nodes count karo) → Ex 9 · J (ek dhundho, ruk jao) → Ex 10.

Recall Self-test

Subset-sum [2,4,6,8] target 6 — kitne subsets? ::: 2 — {2,4} aur {6}. N-Queens n=3 — kitne solutions? ::: 0. N-Queens n=4 — kitne solutions? ::: 2. Empty list ke subsets — kitne? ::: 1 (empty set). [1,2,3] ke permutations ne kuch kyun prune nahi kiya? ::: Koi partial prefix kabhi hopeless nahi hoti — har prefix ek valid full permutation tak extend hoti hai, isliye koi subtree cut nahi hoti. Task assignment bans W2≠A, W3≠C ke saath — valid count? ::: 3. $b$ aur $d$ yahan kya matlab hai? ::: $b$ = branching factor (children per node), $d$ = depth (ek full solution ke liye decisions); tree mein $b^d$ tak leaves ho sakte hain. Find-one vs find-all — code mein kya badalta hai? ::: Find-one ek boolean return karta hai aur short-circuit karta hai (pehle hit pe recursion upar return karta hai); find-all recurse karta rehta hai aur list mein collect karta hai.

---

Connections

• Parent: Backtracking (Hinglish) — woh core template jo yeh examples drill karte hain.
• N-Queens — Ex 1, Ex 2 uske n=4 aur n=3 instances hain.
• Permutations-and-Combinations — Ex 6 ki counting.
• Branch-and-Bound — Ex 4, Ex 7 uska "kya yeh ceiling target tak pahunch sakti hai?" bound use karte hain.
• Recursion · Depth-First-Search — traversal machinery; Ex 10 ka short-circuit full DFS se contrast karta hai.
• Time-Complexity — pruning average case mein kyun help karta hai, worst case mein nahi (Ex 6); $b^d$ growth define karta hai.
• Sudoku-Solver · Dynamic-Programming — jahan yahi cells dobara aate hain.