3.7.17 · D1Backtracking problems — N-Queens, Sudoku solver, all permuta
Intuition Ek hi core ideaBacktracking matlab adhi-bani answers ka ek tree explore karna — ek branch pe walk karo, aur jaise hi koi branch prove ho jaye ki hopeless hai, apna last move erase karo aur next option try karo . Parent page pe jo bhi hai — queens, Sudoku, subsets, permutations — sab isi ek "try, check, undo" move ka alag-alag roop hai.
Parent note ko fluently padhne se pehle, kuch choti ideas tumhare dimaag mein already honi chahiye: tree kya hoti hai, recursion ek stack of paused calls ki tarah kaisi dikhti hai, "choose → explore → un-choose " physically ek shared list ke saath kya karta hai, aur chhote notation pieces jaise path[:], r//3, r-c, aur 2 n
Sab kuch yahan se shuru hota hai.
Choice matlab ek chhota sa decision jo tum answer banate waqt lete ho: "is queen ko column 3 mein rakho", "number 2 ko apne subset mein lo", "is Sudoku cell mein 7 likho". Partial solution matlab abhi tak ka answer, kuch choices ke baad lekin sab nahi.
Intuition "Partial" kyun matter karta haiTum kabhi bhi ek poora finished answer ek saath judge nahi karte. Tum use choice by choice judge karte ho. Yahi backtracking aur brute force ka farq hai: brute force poori cheez banata hai phir check karta hai; backtracking har ek choice ke baad check karta hai aur jaldi chhod deta hai.
Figure dekho: partial solution ek branching diagram ke beech mein ek jagah hai. Neeche ke dots complete answers hain; unse upar ke har dot ka matlab hai "adha hua".
Definition Tree (search tree)Tree ek branching diagram hai: ek starting point (the root , yaani empty answer), aur har point se kuch branches neeche jaati hain, ek branch per possible next choice. Ek point ko node kehte hain; bilkul neeche ke end points ko leaves kehte hain.
Upar wali figure mein in words ko match karo:
root = tumne abhi tak koi bhi choice nahi ki (empty subset, empty board).ek edge (branch) = "ek aur choice karo".
ek node = ek partial solution.
ek leaf = ek complete candidate (saari choices ho gayi).
Intuition Tree kyun, list kyun nahi?Kyunki har choice kayi naye choices khol deti hai . Ek decision bahut saari cheezein ban jaata hai. Jis shape mein ek cheez kai mein split hoti hai, jo phir kai mein split hoti hain, woh tree hai. Isliye parent note kehta hai "the search space is a tree" — choices ki branching nature yahi force karti hai.
Recall Backtracking terms mein leaf kya hoti hai?Ek node jahan har choice ho chuki ho — ek complete candidate answer jise hum record ya test kar sakte hain.
Is tree ko depth-first walk karna exactly Depth-First-Search hai; backtracking is DFS with an "undo" step, aur yeh constraint satisfaction ka ek special disciplined form hai.
Upar wali tree ek aisi function se walk hoti hai jo khud ko call karti hai. Code padhne ke liye tumhe picture karni hogi ki "function apne aap ko call karna" kaisa dikhta hai.
Recursion matlab ek function jo ek bada problem khud ko chhote piece pe call karke solve karta hai. backtrack(row 0) poora board handle karta hai backtrack(row 1) ko rest ke liye call karke, jo backtrack(row 2) call karta hai, aur aage.
Definition The call stackJab bhi ek function khud ko call karta hai, outer call pause ho jaata hai aur ek pile ke upar stack ho jaata hai — the call stack . Jab inner call khatam hoti hai, hum pop karke paused outer call pe wapas aate hain aur wahi se aage chalte hain jahan ruke the.
Figure mein, boxes ka lamba stack call stack hai. Har box apne local variables yaad rakhta hai — kaun sa row tha, kaun sa column try kar raha tha. Isliye "un-choose" line sahi time pe chalta hai: jab backtrack(r+1) return karta hai, control paused backtrack(r) ke paas wapas aata hai, jiski bilkul agली line undo hai.
Intuition Stack "un-choose" ke liye kyun matter karta haiTree ke neeche jaana = calls push karna. Wapas upar jaana = calls pop karna. Jaise hi tum pop karke wapas aate ho, tum ek aisi node pe khade ho jo tumne pehle visit ki thi, aur uski shared state abhi bhi woh choice hold karti hai jo tumne neeche jaate waqt ki thi. Toh popped-back-to call ko us choice ko undo karna hi hoga next branch try karne se pehle. Deep-dive: dekho Recursion-and-the-call-stack .
Recall "Un-choose" line actually kab execute hoti hai?Recursive call return hone ke baad — yaani jab call stack us paused frame pe wapas pop karta hai, next sibling branch try karne se bilkul pehle.
Yeh sabse tricky foundation hai, isliye hum ise dheere-dheere build karte hain.
Definition List aur mutationList jaise path = [1, 2] ek box hai jo items order mein hold karta hai. Use mutate karna matlab same box ko in-place change karna: path.append(3) ise [1,2,3] bana deta hai; path.pop() last item remove karta hai. Yeh abhi bhi same box hai, bas alag contents ke saath.
Definition Reference vs copyReference ek pointer hai box ki taraf, contents ki taraf nahi. Agar tum reference store karo res.append(path) aur phir path mutate karo, toh jo tumne store kiya tha woh bhi change ho jaata hai — kyunki woh same box ki taraf point karta hai. Copy path[:] ek brand-new box banata hai same items ke saath, us moment pe frozen.
Figure khatra dikhati hai: left pe, teen arrows sab EK box ko point karte hain; jab box empty ho jaata hai, teeno "saved answers" empty ho jaate hain. Right pe, path[:] har ek ka apna box mein snapshot leti hai, toh woh alag rehte hain.
Intuition Mutate karo hi kyun — fresh lists kyun nahi?Kyunki ek path hai jo tree mein upar-neeche chalta hai, neeche jaate waqt append hota hai aur wapas aate waqt pop hota hai. Ek box reuse karna fast hai aur "choose / un-choose" motion se exactly match karta hai. Price yeh hai: jab bhi tum ek answer rakhna chaho, tumhe ise copy karna hoga (path[:]), warna tum ek aisi box ka reference rakhte ho jo change hone wali hai.
res.append(path) instead of res.append(path[:])
Sahi lagta hai: "Maine apna answer store kar liya." Kyun galat hai: tumne reference store kiya; box mutate hota rehta hai, toh har stored answer identical ho jaata hai. Fix: copy store karo, path[:] ya list(path).
Ab pehle ke pieces milkar template ki heartbeat mein fit ho jaate hain.
Intuition Un-choose kyun non-negotiable haiSections 1–3 milke ise force karte hain: state ek shared, mutated box hai (§3), aur call stack pop back karta hai ek aisi node pe jo tumne already touch ki thi (§2). Agar tum undo skip karo, sibling branches leftover choices inherit karengi aur garbage produce karengi.
Yeh parent code mein har jagah aata hai. Har ek chhota sa hai jab naam pata ho.
range(n) aur index i
range(n) sequence hai 0 , 1 , 2 , … , n − 1 Index i ek position number hai; nums[i] position i pe element read karta hai. Positions 0 se start hote hain, toh last index n-1 hai, n nahi.
2**n aur count 2 n 2 n 2 n 2**n hai (double-star = power). Yeh subsets count karta hai kyunki n in ya out hai — do options har ek, multiply karke: 2 × 2 × ⋯ = 2 n
n! (factorial)
n ! = n × ( n − 1 ) × ⋯ × 2 × 1 n n − 1
Definition Integer division// aur remainder %
a // b divide karta hai aur fraction hataa deta hai (7 // 3 = 2). a % b bachi hui remainder hai (7 % 3 = 1). Sudoku r // 3 use karta hai yeh pata karne ke liye ki ek cell kaun se 3×3 box-row mein hai (0, 1, ya 2). (Math text mein \% likha jata hai: 7 \% 3 = 1.) Yeh box membership decide karte hain; neeche wali box-index figure dekho.
r - c aur r + c
Row r, column c wali cell ke liye:
ek ↘ diagonal ke along, down-right jaane par r aur c dono mein 1 add hota hai, toh r - c constant rehta hai — yeh us ↘ line ko name karta hai.
ek ↗ anti-diagonal ke along, down-left jaane par r mein 1 add hota hai lekin c mein se 1 subtract hota hai, toh r + c constant rehta hai — yeh us ↗ line ko name karta hai.
Isliye do queens diagonally attack karti hain exactly jab woh ek r-c value share karti hain ya ek r+c value share karti hain. Figure dono families of lines aur unke constant labels dikhata hai.
Recall r - c ek ↘ diagonal ke along same kyun rehta hai?
Ek step down-right jaane par r mein 1 aur c mein 1 add hota hai; difference r - c isliye change nahi hota, toh us diagonal ki har cell ek hi number share karti hai.
Pruning = ek aisi branch explore karne se mana karna jise tum already prove kar chuke ho ki doomed hai, recursion mein jaane se pehle . if valid(...) (ya if attacked: continue) check jo recursive call guard karta hai, woh prune hai.
Intuition Pehle prune kyun karo, baad mein kyun nahi?Agar tum sirf leaves pe check karo, tum phir bhi pehle har doomed branch generate karte ho — yahi brute force hai. Branch ko top pe kaatna uske sab millions leaves ko skip karta hai. Pruning poora speed advantage hai, aur yeh backtracking ko Branch-and-Bound se link karta hai (jo numeric bounds use karke prune karta hai) aur Dynamic-Programming se contrast karta hai (jo overlapping subproblems reuse karke prune karta hai). In trees ki cost Time-Complexity-of-Recursive-Algorithms mein padhte hain.
choice and partial solution
index notation and powers
diagonal keys r minus c and r plus c
integer division and remainder
pruning cut dead branches
Har arrow ka matlab hai "right idea samajhne ke liye left idea chahiye." Sab Backtracking topic node mein funnel hote hain — yeh parent page hai: the topic .
Right side cover karo; kya tum reveal karne se pehle har ek ka jawab de sakte ho?
Partial solution kya hai?Kuch choices se banaya answer lekin sab se nahi — search tree mein beech mein ek node.
Search space tree kyun hoti hai? Kyunki har choice kayi naye choices kholti hai, toh ek node bahut mein branch hoti hai, recursively.
Recursion ke dauran call stack pe kya hota hai? Har ek paused outer call, apne local variables yaad karke, apni inner call ke return hone ka wait kar raha hai.
Mutate a list in place ka matlab kya hai?Same box ki contents change karna (append, pop) bina naya box banaye.
Reference vs copy — path[:] kya deta hai? Ek copy: ek fresh box same items ke saath, baad ke mutation se safe.
path[:] kyun store karein, path kyun nahi?path ek shared box hai jo badhta rehta hai; reference store karne se sab saved answers identical ho jaate hain.
Teen magic words batao. choose → explore → un-choose.
Un-choose mandatory kyun hai?State shared hai aur stack already-touched node pe wapas pop karta hai; leftover choices sibling branches ko poison kar dengi.
7 // 3 kya deta hai, aur 7 % 3?7 // 3 = 2 (floor division); 7 \% 3 = 1 (remainder).
r - c ek ↘ diagonal ke along constant kyun rehta hai?Down-right jaane par r aur c dono mein 1 add hota hai, difference unchanged rehta hai.
r + c ek ↗ anti-diagonal ke along constant kyun rehta hai?Down-left jaane par r mein 1 add hota hai lekin c mein se 1 subtract hota hai, sum unchanged rehta hai.
2 n n
Pruning kya hai aur ise recurse karne se pehle kyun karo?Provably-doomed branch skip karna; recurse karne se pehle karna uske neeche saare leaves cut karta hai, jo poora speed win hai.