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

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

Hum kuch bhi assume nahi karte. Agar koi word aata hai, pehle hum use draw karte hain.

---

Step 1 — "Partial solution" kya hota hai?

KYA. Maano hum list nums = [1, 2] ke har subset chahte hain. Subset in numbers ka koi bhi selection hota hai — khaali selection [] aur poora [1,2] bhi include hai. Partial solution ek adha-bana jawab hai: humne kuch elements ke baare mein decide kar liya hai aur baaki ke baare mein abhi nahi kiya.

YE YAHAN SE KYUN SHURU KARTE HAIN. Backtracking kabhi ek hi baar mein poora jawab nahi banata. Woh answers incrementally banata hai, ek decision ek time pe. Toh ek tree draw karne se pehle, hum yeh agree karna padega ki ek "half-built" cheez kaisi dikhti hai.

PICTURE. Hum chalte waqt do cheezein track karte hain:

• i — us element ka index jiske baare mein hum abhi decide karne wale hain (list mein ek pointer).
• path — woh elements ki list jo humne abhi tak choose ki hain.

Neeche, path ek box hai; i ek chhota sa arrow hai jo agli undecided element ki taraf point karta hai.

---

Step 2 — Ek element = do branches wala ek fork

KYA. Index i pe element ke liye, hum exactly do kaam kar sakte hain: skip it (subset se bahar rakho) ya take it (path mein daalo). Yeh ek fork hai raaste mein jisme se do edges nikalti hain.

DO KYUN. Har element independently andar ya bahar hai — aur kuch possible nahi. Element ke per do options precisely wahi reason hai jis se total $2^n$ subsets hote hain: $2$ ko apne aap se ek baar per element multiply karo.

$\underset{\text{element }0}{\underbrace{2}}\times \underset{\text{element }1}{\underbrace{2}}\times \cdots \times \underset{\text{element }n-1}{\underbrace{2}}=2^n$

$2$ ka har factor ek fork hai; product leaves count karta hai.

PICTURE. [1,2] ke index 0 ke liye fork draw karo. Left edge = skip, path unchanged. Right edge = take, path mein 1 append.

---

Step 3 — Fork ko repeat karke poora tree grow karo

KYA. Element 0 decide karne ke baad, hum index 1 pe hain, aur wahi do-taraf wala fork phir se hota hai — dono level-0 nodes se. Tab tak repeat karo jab tak i n = 2 tak nahi pahunch jaata. Tab path ek finished subset hai: ek leaf.

KYUN. Template mein "recurse deeper" ka matlab yahi hai: bt(i+1) kehta hai "ab agli index se shuru hoke chhote problem ko solve karo." Har recursive call ek aur level ke forks lagaata hai. Jab i == len(nums), decide karne ke liye kuch nahi bata → hum path record karte hain.

PICTURE. [1,2] ke liye poora tree. Char root-to-leaf paths, char leaves: [], [2], [1], [1,2] — exactly $2^2=4$ subsets.

---

Step 4 — DFS actually nodes ko kis order mein visit karta hai

KYA. Hum magically poora tree nahi dekhte. Computer use depth-first walk karta hai: ek branch mein jitna ho sake gehra jao, leaf hit karo, phir wapas aao aur agli branch try karo. Yeh exactly Depth-First-Search hai.

DEPTH-FIRST KYUN, LEVEL-BY-LEVEL KYUN NAHI? Kyunki hum same path list ko descend karte waqt reuse karna chahte hain. Pehle gehra jaana matlab ek waqt pe sirf ek hi root-to-current path memory mein hold karna — woh path call stack pe rehti hai. Breadth-first humein ek saath har adhi-bani path yaad rakhne par majboor karega.

PICTURE. Numbered arrows follow karo: visit order. Dekho kaise walk pehle left spine mein neeche dhabba jaati hai, wapas aati hai, phir right jaati hai.

---

Step 5 — "Un-choose": woh move jo ise backtracking banata hai

KYA. Recursive call ke baad code line path.pop() dekho. Jab hum take branch explore karna khatam karte hain, humein woh element remove karna padta hai jo humne append kiya tha — warna woh path mein baith jaata hai aur agli branch ko poison kar deta hai.

KYUN. path ek hi single list hai, shared aur mutated har call ke dwara. Neeche jaate waqt copy nahi hoti. Toh "take 1" se wapas aane ke baad, 1 abhi bhi wahan baitha hai. Tree ke sibling branch try karne se pehle, path ko restore karna padta hai woh jo tha is fork pe. Wahi restoration backtracking mein "back" hai.

$\underset{\text{choose}}{\underbrace{\text{path.append}(x)}}\to \underset{\text{explore}}{\underbrace{\text{bt}(i+1)}}\to \underset{\text{un-choose}}{\underbrace{\text{path.pop}()}}$

Teen arrows left se right padhte hain har single node pe. Choose x ko daalta hai; explore x ke saath reachable sab kuch mein dive karta hai; un-choose x ko wapas uthata hai taaki world next sibling ke liye clean rahe.

PICTURE. path ko ek poore descent-aur-return ke saath mutate hote dekho. Green = append, red = pop. List saans leti hai: neeche jaate badhti hai, wapas aate ghatti hai.

---

Step 6 — Kyun path[:] store karna padta hai, path nahi

KYA. Leaf pe hum res.append(path[:]) likhte hain — path ki copy — res.append(path) nahi.

KYUN. path woh ek shared, saans leti list hai Step 5 se. Agar hum list itself store karte hain (ek reference), toh jab path baad mein [] tak wapas shrink hoti hai, humne store kiye har "jawab" ki pointer us same ab-khaali list ki taraf hai. path[:] ek snapshot freeze karta hai: ek brand-new list jo aaj ke contents hold karti hai, future mutation se safe.

PICTURE. Left: teen stored references sab ek box ki taraf point karte hain jo end mein khaali hai → teen khaali results. Right: teen independent snapshot boxes → teen sahi results.

---

Step 7 — Pruning: woh branch jo hum draw karne se inkar karte hain

KYA. Subsets kabhi prune nahi karte — har branch legal hai, isliye tree complete hai. Lekin puri wajah backtracking brute force se better hai woh hai ki mushkil problems jaldi branches cut karti hain. N-Queens mein code kehta hai: if c in cols or (r-c) in diag or (r+c) in anti: continue. Woh continue kabhi bhi doomed sub-tree mein enter nahi karta.

KYUN. Pruning recursive call se pehle hoti hai. Jis instant ek partial choice provably hopeless hai (ek queen attack hogi), hum us poori branch ko skip karte hain neeche — laakhon leaves jo hum kabhi generate nahi karte. Yeh Branch-and-Bound aur Constraint-Satisfaction-Problems ka workhorse backtracking kyun hai uska beej hai.

PICTURE. Subset tree (poori, kuch cut nahi) ek N-Queens-style tree ke saath jisme grey scissored branches hain — pruned sub-trees faded draw hain, dikha rahe hain woh kaam jo humne bachaya.

---

Step 8 — Degenerate cases (reader ko kabhi stranded mat chhodna)

KYA & KYUN & PICTURE, teen chhote boards:

• Khaali input nums = []. Tab n = 0, isliye i == 0 == len(nums) turant: hum ek leaf record karte hain, khaali subset []. Sahi — kisi bhi cheez ka power set { [] } hai, aur $2^0=1$.
• Ek element nums = [7]. Ek fork, do leaves: [] aur [7]. $2^1=2$.
• "Solution mila, ruko" problem (Sudoku). Yahan bt() ek boolean return karta hai aur ek deep success wapas upar short-circuit karta hai (if bt(): return True) — jis moment ek answer milta hai hum ruk jaate hain, subsets/permutations/N-Queens ki tarah saari branches explore karne ki jagah.

Recall "return True" chain subsets se kaise alag hai?

Subsets/permutations/N-Queens saare answers chahte hain, isliye woh kuch return nahi karte aur poora tree walk karte hain. Sudoku ek chahta hai, isliye True stack ke upar bubble karta hai aur upar ke har pending fork ne siblings try karna band kar diya. ::: Ek har leaf choose karta hai; doosra pehli achi leaf pe ruk jaata hai.

---

Ek-picture summary

Upar sab kuch, compress kiya: fork (Step 2), growing tree (Step 3), DFS order (Step 4), choose/explore/un-choose ke saath saans leti path (Step 5), aur ek pruned branch (Step 7) — sab ek board pe.

Recall Feynman: poora walkthrough ek 12-saal ke bacche ko batao

Tum do toppings, mushroom aur pepper se har possible pizza ki list bana rahe ho. Topping #1 pe khade ho. Tumhare paas do darwaze hain: "no mushroom" (left) aur "yes mushroom" (right). Ek se andar jao, phir topping #2 face karo wahi do darwaze ke saath. Neeche chalte raho jab tak tumne har topping decide nahi kar li — woh jagah ek finished pizza hai; uski photo lo (yahi path[:] hai) aur photo laga do. Ab peechhe chalo last darwaze tak aur, jaise tum wapas bahar nikalte ho, utaaro woh topping jo us darwaze ne daali thi (yahi path.pop() hai) taaki plate agli darwaze ke liye saaf ho. Tab tak repeat karo jab tak har path walk na ho jaaye. Woh trick jo time bachati hai: agar koi darwaza clearly ruined jagah ki taraf le jaata hai — jaise ek doosri queen wahan daalna jahan woh pakad jaaye — us darwaze ko kholo bhi mat (yahi pruning hai). Backtracking bas yahi hai: darwaze, photos, aur wapas jaate waqt apni plate hamesha saaf karo.