Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets: Exercises

3.7.17 · D4 · Coding › Algorithm Paradigms › Backtracking problems — N-Queens, Sudoku solver, all permuta

Shuru karne se pehle, ek shared vocabulary reminder — neeche ke har solution mein yahi kaam aata hai.

Level 1 — Recognition

Exercise 1.1

Inme se kaun sa backtracking hai, aur kaun sa plain brute force?

(a) Counter ko $0$ se $2^{n} - 1$ tak loop karke saare $2^{n}$ subsets generate karna aur uske bits padhna.
(b) Queens ko row by row place karna, jaise hi koi queen attack mein aaye us branch ko turant chhod dena.

Recall Solution 1.1

(a) brute force hai. Yeh har poori configuration generate karta hai, koi early pruning nahi — bit-counter kabhi nahi poochta "kya yeh partial choice already doomed hai?" (b) backtracking hai. Yeh prune karta hai: jaise hi do queens attack karein, woh poora subtree skip ho jaata hai. Defining feature hai ek partial state ko complete hone se pehle prune karna.

Exercise 1.2

Neeche diye subsets skeleton mein, marked lines par teen magic words ka naam batao.

def bt(i):
    if i == len(nums): res.append(path[:]); return
    bt(i+1)                 # (A)
    path.append(nums[i])    # (B)
    bt(i+1)                 # (C)
    path.pop()              # (D)

Recall Solution 1.2

(A) Explore — "nums[i] skip karo" branch (koi state change nahi hua, toh choose/undo kuch nahi).
(B) Choose — nums[i] ko path mein add karo.
(C) Explore — "nums[i] lo" branch.
(D) Un-choose — isse hataao taaki caller ka path restore ho jaaye.

Note karo ki skip-branch ko choose/undo ki zaroorat nahi kyunki woh kuch mutate nahi karta; sirf take-branch karta hai.

Exercise 1.3

nums = [7] ke liye, kitne subsets produce hote hain, aur woh kya hain?

Recall Solution 1.3

$2^{n} = 2^{1} = 2$ subsets: [] aur [7]. Har element independently andar ya bahar hota hai → har element par $2$ ka factor.

Level 2 — Application

Exercise 2.1

subsets([1,2]) ko hand-trace karo aur results exact order mein likho jis order mein code append karta hai.

Recall Solution 2.1

Code hamesha bt(i+1) (skip) pehle karta hai, phir append (take) karta hai. (i, path) ka tree chalao:

bt(0) path []
- bt(1) (skip 1) path []
  - bt(2) (skip 2) → i==2, append []
  - take 2 → bt(2) append [2]
- take 1 → bt(1) path [1]
  - bt(2) (skip 2) append [1]
  - take 2 → bt(2) append [1,2]

Order: [], [2], [1], [1,2]. (Neeche tree figure dekho.)

Figure — Backtracking problems — N-Queens, Sudoku solver, all permutations - subsets

Exercise 2.2

permute([1,2,3]) — kitne results aate hain, aur code order mein pehle do batao.

Recall Solution 2.2

$n! = 3! = 6$ results. Loop i=0,1,2 order mein try karta hai aur hamesha pehle sabse chhota available element pick karta hai, toh:

Pehla: pick 1 → pick 2 → pick 3 → [1,2,3].
Backtrack: pop 3, pop 2; ab pick 3 → pick 2 → [1,3,2].

Pehle do: [1,2,3], [1,3,2].

Exercise 2.3

N-Queens mein, ek queen (r,c) = (2,5) par baithi hai. Uske teen conflict keys batao: column, ↘ diagonal (r-c), ↗ anti-diagonal (r+c).

Recall Solution 2.3

column key = c = 5
↘ diagonal key = r-c = 2-5 = −3
↗ anti-diagonal key = r+c = 2+5 = 7

Koi bhi doosra cell jo inme se koi bhi number share kare, woh attacked hai. (Figure: is cell se hone wale dono diagonals.)

Exercise 2.4

Sudoku box index hai (r//3)*3 + c//3. (r,c) = (7,1) ke liye isko compute karo aur batao yeh kaun sa box (0–8) hai.

Recall Solution 2.4

7//3 = 2 (box-row), 1//3 = 0 (box-col). Index = 2*3 + 0 = 6 — bottom-left box.

Level 3 — Analysis

Exercise 3.1

subsetsWithDup([1,2,2]) ko power set return karna hai bina duplicate subsets ke. Naive subsets [2] do baar dega. Fix explain karo aur correct output list karo.

Recall Solution 3.1

Fix: pehle sort karo, phir skip karte waqt, current value ki saari copies skip karo taaki tum kabhi bhi do branches same "pehli li gayi 2" se shuru na karo. Ek cleaner index form: level i par, j ko i se loop karo; j > i and nums[j]==nums[j-1] ho toh skip karo. Sorted [1,2,2] se distinct subsets milte hain: [], [1], [1,2], [1,2,2], [2], [2,2] — 6 subsets ( $2^{3} = 8$ nahi; duplicate [2]/[1,2] copies collapse ho jaate hain).

Exercise 3.2

Sudoku solver bool kyun return karta hai aur if bt(): return True se short-circuit karta hai, jabki N-Queens kuch return nahi karta aur har branch explore karta hai?

Recall Solution 3.2

Sudoku ek solution chahta hai → boolean ek successful deep call ko True call stack par bubble up karne aur alternatives try karna rokne deta hai, bohot saara kaam bachata hai. N-Queens (jaise likha hai) saare solutions collect karta hai → koi "hum done hain" signal nahi; isse har valid leaf visit karna hi padega, toh yeh kuch return nahi karta aur hamesha continue karta hai. Lesson hai: return signature encode karta hai "ek dhundho" ya "sab dhundho."

Exercise 3.3

Permutation code mein, agar tum un-choose step mein used[i] = False line hata do toh kya galat hoga? [1,2] ke liye ek concrete broken output do.

Recall Solution 3.3

"1 pehle" explore karne ke baad, element 1 used flagged rehta hai. Jab top loop "2 pehle" par jaata hai, element 1 abhi bhi blocked hai, toh branch use kabhi place nahi kar sakti. Result: [1,2],[2,1] ki jagah sirf [1,2] milta hai (aur [2] complete nahi ho sakta → kuch nahi). used[i] reset karna hi element 1 ko sibling branches ke liye free karta hai.

Exercise 3.4

N-Queens diagonal key r-c negative ho sakti hai (jaise −3). Python set ke liye yeh theek kyun hai, aur kya break hota agar tum r-c se indexed fixed-size boolean array naively use karte?

Recall Solution 3.4

set integers ko keys ki tarah store karta hai, sign irrelevant hai — negatives theek hash hote hain. Ek raw array diag[r-c] negative number se index hoga; Python mein yeh silently array ke tail par wrap ho jaata hai, checks corrupt kar deta hai. Arrays use karne ka fix: n-1 se offset karo, matlab diag[r - c + (n-1)], index ko [0, 2n-2] mein rakhte hue.

Level 4 — Synthesis

Exercise 4.1

combinationSum(candidates, target) likho: candidates ke saare multisets (har element unlimited baar reusable, distinct positive ints) jo target tak sum karein. candidates=[2,3,5], target=8 ke liye, har combination list karo.

Recall Solution 4.1

Reuse allowed → candidates[i] choose karne ke baad same index i se recurse karo; permuted duplicates se bachne ke liye, pehle wale indices par kabhi wapas mat jao.

def combinationSum(cands, target):
    res, path = [], []
    def bt(i, remain):
        if remain == 0: res.append(path[:]); return
        if remain < 0 or i == len(cands): return   # prune
        path.append(cands[i]); bt(i, remain - cands[i]); path.pop()  # take, stay at i
        bt(i+1, remain)                                              # skip to next
    bt(0, target)
    return res

[2,3,5], target=8 ke liye: [2,2,2,2], [2,3,3], [3,5] — 3 combinations. Check: $2 \cdot 4 = 8$ ; $2 + 3 + 3 = 8$ ; $3 + 5 = 8$ . ✓

Exercise 4.2

Ideas combine karo: " $N \times N$ board par $N$ non-attacking rooks place karo aur solutions count karo" solve karo (rooks sirf rows/columns par attack karte hain, koi diagonal nahi). General $N$ ke liye count derive karo aur $N = 4$ verify karo.

Recall Solution 4.2

Ek rook per row (row conflicts khatam). Row 0 koi bhi $N$ column pick karta hai; row 1 baaki $N - 1$ columns mein se koi pick karta hai; … → $N \times (N - 1) \times \dots \times 1 = N!$ . Yeh exactly permutations pattern hai (column choice = columns ki ek permutation). $N = 4$ ke liye: $4! = 24$ solutions.

Exercise 4.3

N-Queens ko count karne ke liye modify karo bina boards store kiye, aur $N = 4, 5, 6$ ke liye count do.

Recall Solution 4.3

Board drop karo; append karne ki jagah integer sum return karo.

def countNQueens(n):
    cols, diag, anti = set(), set(), set()
    def bt(r):
        if r == n: return 1
        total = 0
        for c in range(n):
            if c in cols or (r-c) in diag or (r+c) in anti: continue
            cols.add(c); diag.add(r-c); anti.add(r+c)
            total += bt(r+1)
            cols.remove(c); diag.remove(r-c); anti.remove(r+c)
        return total
    return bt(0)

Known distinct-solution counts: $N = 4 \to$ 2, $N = 5 \to$ 10, $N = 6 \to$ 4.

Level 5 — Mastery

Exercise 5.1

Ek backtracking search ka branching factor $b$ aur depth $d$ hai, aur pruning average par har node ke $p$ fraction children ko eliminate karta hai. Koi pruning na ho toh worst-case leaf count do, aur ek line mein explain karo kyun real backtracking us bound se often astronomically faster hoti hai.

Recall Solution 5.1

Worst case (no pruning) leaves $= b^{d}$ . Real backtracking effective branching factor ko har level par $(1 - p)$ se multiply karta hai, roughly $(b (1 - p))^{d}$ deta hai — yeh exponent mein exponential improvement hai, kyunki saving $d$ levels mein se har ek par compound hoti hai. Jaldi prune karna (root ke paas) poore subtrees hata deta hai, isliye L3 ka "recurse karne se pehle prune karo" itna matter karta hai. Numeric-bound version ke liye Branch-and-Bound dekho aur general framing ke liye CSPs dekho.

Exercise 5.2

Simple "pehla empty cell dhundho" order wala Sudoku hard boards par slow ho sakta hai. MRV (minimum-remaining-values) heuristic describe karo aur kyun yeh harder prune karta hai — isse L3 ke pruning principle se connect karo.

Recall Solution 5.2

Pehle empty cell ki jagah, woh empty cell pick karo jiske paas sabse kam legal digits hain (most-constrained variable). Isse pehle choose karne ka matlab hai ki wahan branching factor sabse chhota hai, aur dead ends tree ke upar discover hote hain jahan ek failure sabse bada subtree khatam karta hai. Yeh wahi principle hai jaise "recurse karne se pehle prune karo," ek level aur gehre push kiya: highest-impact node par branching factor chhhota karo. Yeh core CSP technique hai.

Exercise 5.3

Explain karo ki tum Dynamic-Programming ki taraf kab jaoge backtracking ki jagah, subsets-summing ko example use karke. Problem mein kaun si structural property honi chahiye?

Recall Solution 5.3

Backtracking actual solutions enumerate karta hai; DP tab kaam aata hai jab tumhe sirf count/optimum chahiye aur subproblems overlap karte hain (wahi (index, remaining_sum) state kai branches mein dubara aata hai). "Kya koi subset T tak sum kar sakta hai?" ek yes/no hai overlapping (i, T) states ke saath → $O (n \cdot T)$ ke liye memoise/tabulate karo, $O (2^{n})$ ki jagah. Required property: overlapping subproblems + tumhe solutions ki explicit list nahi chahiye, sirf ek aggregate. Agar tumhe har solution list karna hai, toh DP kaam nahi karega — tum backtracking par wapas aao kyunki exponentially many outputs ho sakte hain.

Recall Jaane se pehle ek-line self-check

Har choose ka ek matching un-choose hota hai ::: haan — shared state ko next sibling se pehle restore karo N-Queens diagonal keys ::: r−c (↘) aur r+c (↗), dono sets mein track kiye jaate hain combinationSum([2,3,5], 8) count ::: 3 N=6 ke liye distinct N-Queens solutions ::: 4 DP backtracking se kab behtar hai ::: overlapping subproblems aur tumhe sirf aggregate chahiye, list nahi