Backtracking — state-space tree, pruning: Exercises

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

Intuition Is page kaise use karein

Ye 12 problems ek ladder climb karte hain: Recognition → Application → Analysis → Synthesis → Mastery. Har ek clearly stated hai, phir uska poora worked solution ek collapsible [!recall]- callout mein chhupa hai — taaki pehle khud try karo, phir reveal karo. Ye tumhara self-test hai Backtracking ke liye. Yahan sab kuch wohi vocabulary reuse karta hai jo parent note ne build ki thi: state-space tree, candidate, promising node, pruning, backtrack (undo).

Shuru karne se pehle, simple words mein ek refresher taaki koi bhi term unfamiliar na lage:

Decision = ek choice jo tum partial solution ko badhane ke liye karte ho (queen place karna, item include karna).
State-space tree = un decisions ki har possible sequence, branches ke roop mein draw ki gayi.
Pruning = usi waqt ek branch ko kaat dena jab partial solution already koi rule break kar raha ho, kyunki uske neeche ki har cheez doomed hai.
Backtrack (undo) = tree mein ek step wapas upar jaana aur agla sibling choice try karna.

Figure — Backtracking — state-space tree, pruning

Upar ki picture is poore page ka mental model hai: decisions ka ek tree, jahan rule violate hone par red scissor hai (prune) aur ek dashed arrow wapas upar jaata hai (backtrack).

Level 1 — Recognition

Exercise 1.1 — Pruning line dhundho

Yahan ek backtracking skeleton hai. Kaun si single line pruning karti hai, aur agar tum use delete kar do toh kya hoga?

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in candidates(state):
        if is_valid(state, choice):   # (A)
            state.add(choice)         # (B)
            backtrack(state)          # (C)
            state.remove(choice)      # (D)

Recall Solution

Line (A) — if is_valid(state, choice) — prune hai. Ye ek aisi branch mein enter karne se mana karta hai jiska partial solution already koi constraint violate kar raha ho.

Ise delete karne ka effect: (A) ke bina, har candidate expand hota hai, toh tum poora state-space tree generate karte ho, $b^{d}$ nodes tak ( $b$ = har step par choices, $d$ = depth). Tumhe phir bhi sahi answers milenge (invalid wale elsewhere filter ho jaate hain ya kabhi record nahi hote), lekin tum poora brute-force cost pay karte. Pruning exactly "smart" aur "blind" search ke beech ka fark hai.

(Line (B) move karta hai, (C) explore karta hai, (D) undo/backtrack hai.)

Exercise 1.2 — Tree hai ya nahi?

True ya false: State-space tree mein, do alag nodes ek hi child share kar sakte hain.

Recall Solution

False. Ek state-space tree mein root se kisi bhi node tak exactly ek hi path hota hai — har node ka ek single parent hota hai (woh partial solution jo last decision se pehle thi). Agar do parents ek child share karte toh ye ek graph (a DAG) hota, jisko Dynamic-Programming memoization ke zariye exploit karta hai. Backtracking search space ko decision sequences ke pure tree ki tarah treat karta hai.

Level 2 — Application

Exercise 2.1 — Full binary decision tree ke leaves count karo

Tum subset-sum solve karte ho [3, 1, 4] par include/exclude har element ko decide karke, bina kisi pruning ke. State-space tree mein kitne leaves hain, aur kitne internal nodes?

Recall Solution

Har ek $n = 3$ elements ek binary decision hai, toh branching factor $b = 2$ , depth $d = 3$ .

Leaves = $b^{d} = 2^{3} = 8$ . (Har complete include/exclude assignment.)
Total nodes depth 3 ke full binary tree mein = $2^{0} + 2^{1} + 2^{2} + 2^{3} = 1 + 2 + 4 + 8 = 15$ .
Internal nodes = total $-$ leaves = $15 - 8 = 7$ .

Ye unpruned cost hai — pruning inhe se kuch hata deta hai lekin koi naya add nahi karta.

Exercise 2.2 — Subset-sum prune trace karo

[2, 3, 5] ke woh saare subsets dhundho jinka sum 5 ho, include/exclude left-to-right decide karte hue, aur prune karo jab bhi running_sum > 5 ho. Batao kaun si branches prune hoti hain.

Recall Solution

Target $= 5$ . Tree walk karo (I = include, E = exclude):

I 2 (sum 2)
- I 3 (sum 5) — already at target; phir bhi 5 process karo:
  - I 5 → sum 10 > 5 → PRUNED
  - E 5 → sum 5 ✓ → record {2, 3}
- E 3 (sum 2)
  - I 5 → sum 7 > 5 → PRUNED
  - E 5 → sum 2 ✗ (5 nahi), koi record nahi
E 2 (sum 0)
- I 3 (sum 3)
  - I 5 → sum 8 > 5 → PRUNED
  - E 5 → sum 3 ✗
- E 3 (sum 0)
  - I 5 → sum 5 ✓ → record {5}
  - E 5 → sum 0 ✗

Solutions: {2,3} aur {5} — exactly 2 subsets. Pruned branches: 3 (teen sum > 5 cuts). Har cut neeche wale leaf ko generate hone se pehle kaat deta hai.

Level 3 — Analysis

Exercise 3.1 — Kaun sa validity test pehle prune karta hai?

N-Queens ke liye safety check karne ke do tarike hain:

(A) saari $n$ queens place karo, phir poora board verify karo.
(B) row $r$ place karte waqt, turant rows $0 \dots r - 1$ ke against check karo.

Conflict [0, 2, 2, ...] (row 0 col 0, row 1 col 2, row 2 col 2 — rows 1 aur 2 ke beech column clash) ko har approach kis tree depth par pehli baar detect karta hai? Har approach kitne leaves waste karta hai?

Recall Solution

Clash hai column 2 repeated rows 1 aur 2 par — detect ho sakta hai jis pal row 2 place ho.

(B) early check: depth 2 par fire karta hai (row index 2), exact woh node jahan col 2 row-1 queen se collide karta hai. Ye [0, 2, 2] ke neeche poora subtree prune kar deta hai. $n = 4$ ke liye us subtree mein $b^{d - depth} = 4^{4 - 3} = 4^{1} = 4$ leaves saved hoti hain (row 3 is dead node ke neeche kabhi explore nahi hoti — yahan row 3 ke liye 4 candidate placements).
(A) leaf check: sirf leaf par detect karta hai (depth $n$ ), saari $n$ queens commit karne ke baad. [0,2,2,*] ke neeche woh saare doomed leaves pehle fully generate hote hain.

Conclusion: (B) highest node par prune karta hai jahan constraint already break ho chuki hai; (A) poora subtree waste karta hai. Same answers, bilkul alag kaam — ye parent note ka "test as early as detectable" principle hai.

Exercise 3.2 — Kya pruning Big-O change karta hai?

Ek adversary tumhe ek aisa input deta hai jis par koi bhi partial solution last decision tak kabhi infeasible nahi hoti. Time complexity kya hai, aur ye pruning ke worst-case Time-Complexity par effect ke baare mein kya kehta hai?

Recall Solution

Agar kuch bhi last decision tak prune nahi hota, search poora tree visit karta hai: $b^{d}$ nodes tak → $O (b^{d})$ , blind brute force jaisa hi.

Isliye pruning worst-case asymptotic bound improve NAHI karta. Ye average/typical runtime kaat deta hai (real inputs tons of branches prune karte hain), lekin Big-O adversarial worst case measure karta hai, jise pruning touch nahi kar sakta. Isliye hum backtracking ko "brute force that gives up early" kehte hain — early constant-aur-average-case win hai, asymptotic nahi.

Level 4 — Synthesis

Exercise 4.1 — Repeats ke bina Permutations

[1, 2, 3] ke saare permutations generate karne ke liye is_valid aur candidates likho, aur count karo ki pruned tree mein kitne nodes hain versus unpruned "3 mein se koi bhi pick karo har 3 slots par" tree.

Recall Solution

State = abhi tak bana hua permutation, plus har element ke liye used[] flag.

candidates(state) = saare elements x.
is_valid(state, x) = not used[x] — kisi aisa element reuse mat karo jo already placed ho.

Unpruned (har slot par 3 mein se koi bhi pick karo): $b = 3$ , $d = 3$ → $3^{3} = 27$ leaves. Pruned (used respect karte hue): pehla slot 3 choices, doosra 2, teesra 1 → $3 \times 2 \times 1 = 3! = 6$ leaves.

Pruned tree ke node counts (ek tree jahan level $k$ par $\frac{3 !}{( 3 - k )!}$ nodes hain):

depth 0: 1
depth 1: 3
depth 2: $3 \times 2 = 6$
depth 3: $3 \times 2 \times 1 = 6$
Total = $1 + 3 + 6 + 6 = 16$ nodes.

used[] flag woh pruning hai jo 27 blind leaves ko sirf 6 valid permutations mein badal deta hai.

Exercise 4.2 — Graph 3-coloring skeleton

Tumhe ek triangle graph (3 mutually-connected vertices $V_{0}, V_{1}, V_{2}$ ) ko 3 colors se color karna hai taaki koi edge same-colored vertices join na kare. Har level par ek vertex ka color decide karo. Kitne complete valid colorings exist karte hain, aur pruning $3^{3}$ ke comparison mein kitne leaves save karti hai?

Recall Solution

is_valid(v, color) = v ke kisi already-colored neighbor ka color nahi hai.

Kyunki teeno vertices mutually adjacent hain, inhe sab differ karna hoga → ye 3 vertices ko 3 distinct colors assign karne ke tarike count karna hai:

$V_{0}$ : 3 choices.
$V_{1}$ : $V_{0}$ se differ karna chahiye → 2 choices.
$V_{2}$ : $V_{0}$ aur $V_{1}$ dono se differ karna chahiye → 1 choice.

Valid colorings = $3 \times 2 \times 1 = 6$ . Unpruned leaves $= 3^{3} = 27$ . Pruning $27 - 6 = 21$ dead leaves save karti hai.

Level 5 — Mastery

Exercise 5.1 — N-Queens exact solution counts

One-queen-per-row model use karte hue, $n = 4$ , $n = 5$ , aur $n = 6$ ke liye kitne distinct solutions exist karte hain? (Ye classic small counts hain.) Woh validity test batao jis par tum rely karte ho.

Recall Solution

Validity (parent note): queen row $r$ , column $c$ par place karte hue, ye safe hai agar aur sirf agar har earlier row $i < r$ ke liye: $c \neq = col [i]$ (koi shared column nahi) aur $∣ r - i ∣ \neq = ∣ c - col [i] ∣$ (koi shared diagonal nahi).

Is prune ke saath backtracking run karne par, full solutions ki sankhya hai:

$n = 4$ : 2 solutions — yaani [1,3,0,2] aur [2,0,3,1].
$n = 5$ : 10 solutions.
$n = 6$ : 4 solutions.

Ye known N-Queens sequence $1, 0, 0, 2, 10, 4, 40, 92, \dots$ se match karte hain $n = 1, 2, 3, 4, 5, 6, 7, 8$ ke liye. $n = 6$ par dramatic dip (sirf 4, $n = 5$ se bhi kam) ek acha reminder hai ki solution counts monotonic nahi hote — pruning exactly valid wale dhundh leta hai chahe kuch bhi ho.

Exercise 5.2 — Hardest-case Sudoku cell ke liye prune design karo

Ek Sudoku-Solver mein, tum empty cells left-to-right, top-to-bottom fill karte ho, har ek mein digit 1–9 se. Naively, branching factor 9 hai. Ek pruning/ordering strategy describe karo jo effective branching factor ko drop kare, aur explain karo kyun ye exponential base $b$ ko attack karta hai na ki depth $d$ ko.

Recall Solution

Strategy — Minimum Remaining Values (MRV): cells ko fixed order mein fill karne ki jagah, hamesha fewest legal candidates wala empty cell expand karo (sabse kam digits jo uski row, column, ya $3 \times 3$ box mein already use nahi hui hain).

Kyun ye $b$ ko attack karta hai, $d$ ko nahi: depth $d$ fixed hai — ye empty cells ki sankhya ke barabar hai, aur har solution inhe sab fill karna chahiye, toh tum $d$ short nahi kar sakte. Lekin branching factor $b$ un choices ki sankhya hai jo tum har node par branch karte ho. Cost $b^{d}$ jaisi scale hoti hai; kyunki $d$ locked hai, sirf lever hai $b$ ko shrink karna. MRV most-constrained cell pick karta hai (aksar $b = 1$ ke saath, ek forced move — bilkul bhi branching nahi!), effective base ko 9 se kaafi neeche le jaata hai. Ek single forced cell us poore level ko fan-out se straight line mein collapse kar deta hai.

Standard row/column/box is_valid prune ke saath combine karke, MRV isliye hai ki real solvers instantly finish karte hain Sudoku ke exponential worst case ke bawajood.

Recall Poore ladder ka one-line summary

L1 prune + undo lines pehchano · L2 include/exclude aur sum-bound prune apply karo · L3 early-vs-late checking aur kyun Big-O $O (b^{d})$ rehta hai analyze karo · L4 used[] aur neighbor-color prunes synthesize karo · L5 solution-counting aur branching-factor-reducing heuristics master karo.

Connections

Parent: Backtracking — ye page uske exercises drill karta hai.
Recursion — woh machinery jis par yahan har solution run karta hai.
Depth-First-Search — upar har state-space tree ka traversal order.
N-Queens, Sudoku-Solver — L3/L5 case studies.
Permutations-and-Combinations — L4.1 ki counting.
Time-Complexity — L3.2 mein $O (b^{d})$ analysis.
Branch-and-Bound, Dynamic-Programming — jab plain backtracking se aage jaana ho.