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

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

Yeh page ek "no surprises" drill hai. Parent ne tumhe chaar templates diye the; yahan hum unhe har tarah ke input pe run karte hain taaki interviewer chahe kuch bhi throw kare — ek tiny array, ek empty array, ek board jiska koi solution nahi, ya "list ki jagah count karo" wala twist — uska shape tumne pehle hi dekha hua ho.

Neeche sab kuch plain recursion hai jo partial choices ke ek tree pe DFS kar rahi hai, aur "un-choose" step shared state ko restore karta hai. Agar koi word unfamiliar lage, to woh word parent mein build kiya gaya tha — ek baar wahan jhaanko, phir wapas aao.

Is page pe hum jo names use karte hain

Kisi bhi example se pehle, aao un muthi bhar variables ko fix kar lein jo har jagah appear hote hain, taaki kuch bhi assumed na ho:

Definition Shared vocabulary

nums — un items (numbers, letters) ki input list jahan se hum choose kar rahe hain. Iska length $n$ hai.
path — partial answer jo hum abhi build kar rahe hain, ek shared list jisme hum push karte hain ("choose") aur pop karte hain ("un-choose").
used — True/False flags ki ek list, nums ke har element ke liye ek, jo mark karta hai ki kaun se items pehle se path mein baithe hain. Sirf permutations ko iski zaroorat hai.
res — accumulator: woh list jahan complete answers collect hote hain. Yeh res = [] se start hoti hai aur jab bhi hum base cases pe pohunchte hain, badhti jaati hai.
bt(...) — backtracking function. Iska parameter kehta hai "main kitna aage hoon?": subsets ke liye bt(i) (current index), permutations ke liye bt() (progress len(path) se padhi jaati hai), N-Queens ke liye bt(r) (current row).
N-Queens ke liye, r row index hai (kaun si horizontal line, top = 0) aur c column index hai (kaun si vertical line, left = 0) board ke kisi square ka.

Neeche har worked example exactly inhi names ko reuse karta hai. Jab bhi tum res.append(path[:]) dekho, socho: "ek finished path growing res mein copy ho gayi."

Scenario matrix

Backtracking problems kuch axes pe vary karti hain. Examples karne se pehle, aao har cell list kar lein jahan ek question land kar sakta hai, taaki koi bhi example random na lage.

Cell	Axis	Kya badalta hai	Example jo cover karta hai
A. Empty input	size	`n = 0` — degenerate	Ex 1
B. Singleton	size	`n = 1` — sabse chhota non-trivial	Ex 2
C. Exponential output	branching	subsets, $2^{n}$ leaves	Ex 3
D. Factorial output	branching	permutations, $n!$ leaves	Ex 4
E. Heavy pruning, all solutions	pruning	N-Queens, har answer collect karo	Ex 5
F. No solution exists	feasibility	woh board jahan recursion har jagah dead-end ho	Ex 6
G. First solution only	short-circuit	stack ke upar `True` return karo	Ex 7
H. Count, don't list	output twist	ek integer return karo, koi `path[:]` copy nahi	Ex 8
I. Duplicates in input	constraint	duplicate branches ko skip karna zaroori	Ex 9
J. Real-world word problem	modelling	ek story ko backtracking ke roop mein frame karo	Ex 10

Aao us matrix ke diagonal pe chalo, ek figure per geometric case. Figure 1 neeche matrix ko ek grid ke roop mein draw karta hai: columns teen output shapes hain (list all / first only / count), rows chaar input shapes hain, aur amber cells dikhate hain ki kaun sa example kahan land karta hai — ise page ke map ki tarah padho.

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

Example 1 — Empty input (Cell A)

Worked example

nums = [] ke subsets Statement: Empty list ke saare subsets return karo. (Yaad karo res res = [] se start hoti hai.)

Forecast: Kuch nahi ke kitne subsets hote hain? Aage padhne se pehle ek number guess karo.

Steps:

bt(0) call karo jahan len(nums) == 0 hai. Yeh step kyun? Subset function ka base case i == len(nums) hai; i = 0 aur length 0 ke saath yeh immediately fire ho jaata hai.
Base case res.append(path[:]) run karta hai, aur path [] hai. Kyun? Ek aur sirf ek complete candidate hai "koi element nahi choose kiya," isliye empty path res mein copy ho jaati hai.
res return karo, jo [[]] hai. Yeh step kyun? Exactly $2^{0} = 1$ subset hai — empty set khud.

Verify: $n = 0$ ke saath $2^{n}$ $2^{0} = 1$ subset deta hai. Answer ek empty list wali list hai, [[]], nahi ki empty list []. Yeh differ karte hain: [[]] ki length 1 hai, [] ki length 0 hai.

Example 2 — Singleton (Cell B)

Worked example

nums = [7] ke permutations Statement: Ek-element list ke saare orderings.

Forecast: Ek single element ke kitne orderings ho sakte hain?

Steps:

bt() res = [], path = [], used = [False] ke saath start hoti hai. Kyun? Standard permutation setup: empty accumulator, empty partial answer, single element ke liye ek unused-flag.
len(path)=0 ≠ len(nums)=1, isliye loop chalta hai: i=0, used[0] False hai, 7 choose karo (path mein push karo, used[0]=True set karo). Yeh step kyun? Humein single slot ko single available element se fill karna hai.
Recurse: ab len(path)=1 == 1, base case res.append(path[:]) run karta hai aur [7] record karta hai. Kyun? Path complete hai.
Un-choose: 7 pop karo, used[0]=False. Loop khatam. Kyun undo? Habit aur correctness — chahe kuch aur try karna baaki na ho, hum hamesha shared state restore karte hain.

Verify: $n! = 1! = 1$ permutation. res [[7]] hai, length 1. ✓

Example 3 — Exponential output (Cell C)

Worked example

nums = [1,2,3] ke saare subsets Statement: Full power set res mein produce karo.

Forecast: $2^{3} = ?$ subsets. Number likho.

Steps: Skip/take tree pe chalo. Har index pe hum pehle skip, phir take branch karte hain (parent ke code order se match karta hai). Figure 2 yeh tree draw karta hai: white internal nodes index decision carry karte hain, cyan left edges matlab "nums[i] skip karo", amber right edges matlab "nums[i] lo", aur bottom ke saath amber squares 8 leaves hain — har leaf ek finished subset hai jo res mein copy hoti hai. Koi bhi root-to-leaf path follow karo aur dekho kaise ek subset assemble hota hai.

Depth 0 element 1 pe branch karta hai. Kyun? Har element independently in ya out hai — woh binary choice poora engine hai.
Depth 1 2 pe branch karta hai, depth 2 3 pe. Kyun? Teen elements ⇒ teen levels ⇒ $2 \times 2 \times 2$ leaves.
8 leaves left-to-right padho: [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]. Yeh order kyun? Har node pe "skip" ko "take" se pehle explore kiya jaata hai, isliye all-skips ([]) sabse leftmost leaf hai.

Verify: $2^{3} = 8$ subsets, aur har element exactly aadhe mein appear karta hai ( $4$ subsets 1 contain karte hain). Size ke hisaab se subset counts ka sum: $(0 3) + (1 3) + (2 3) + (3 3) = 1 + 3 + 3 + 1 = 8$ . ✓

Example 4 — Factorial output (Cell D)

Example 5 — Heavy pruning, all solutions (Cell E)

Worked example

n = 4 ke liye N-Queens Statement: $4 \times 4$ board pe 4 non-attacking queens place karne ke kitne tarike hain?

Forecast: Brute force $(4 16) = 1820$ placements hain. Guess karo kitne survive karte hain.

Steps: Ek queen per row, bt(r) ke zariye call karo jahan r current row index hai (top = 0) aur har candidate c ek column index hai (left = 0); cols, diag = r-c, anti = r+c track karo. Figure 3 ek finished board dikhata hai: amber squares queens hain, aur har queen ke saath uski r-c key label hai taaki tum dekh sako ki charon keys differ karti hain — woh visual "no two share a number" exactly no-diagonal-attack condition hai.

Row 0: column 0 try karo. Choose karo, bt(1) mein recurse karo. Col 0 se kyun start? Hum columns left to right sweep karte hain; pruning bure waalon ko maar deti hai.
Row 1 (r=1): col 0 cols pe clash karta hai; col 1 diagonal pe clash karta hai (r-c: $1 - 1 = 0 = 0 - 0$ , row-0 queen ki same key). Col 2 ya 3 pe continue karo. Teen sets kyun check karo? Column, ↘ diagonal, ↗ anti-diagonal — yahi attack lines hain jab rows unique hoti hain.
Deep branches dead-end ho jaati hain jab koi column free nahi hota — backtrack karo, pehle wali queen ko slide karo. Kyun backtrack? Ek blocked row prove karta hai ki poori partial board doomed hai; use abandon karo.
Do full boards emerge hote hain (mirror images): queens at (0,1),(1,3),(2,0),(3,2) aur (0,2),(1,0),(2,3),(3,1).

Verify: Jaana-pehchana result: 4-Queens ke 2 solutions hain. Pehle board ke diagonals check karo ki sab distinct hain: r-c = $- 1, - 2, 2, 1$ (sab alag); r+c = $1, 4, 2, 5$ (sab alag); columns $1, 3, 0, 2$ (sab alag). ✓

Example 6 — No solution exists (Cell F)

Worked example

n = 3 ke liye N-Queens Statement: $3 \times 3$ board pe 3 non-attacking queens place karo.

Forecast: Possible hai ya impossible?

Steps: Phir se r = row index (top = 0), c = column index (left = 0).

Row 0, col 0 pe place karo. Ab Row 1 try karo: col 0 invalid hai (column clash — cols pehle se 0 hold karta hai); col 1 invalid hai (↘ diagonal clash — r-c yahan $1 - 1 = 0$ hai, row-0 queen ke $0 - 0 = 0$ jaisi same key); col 2 free hai. Kyun exhaustive? Hume koi placement kaam nahi karta yeh prove karna hai, isliye har branch try ki jaati hai.
Row 1 par col 2 choose kiya (cols ab = {0, 2}). Ab Row 2 (r=2) try karo, ek-ek column, har ek exactly ek attack line pe fail karta hai:
- col 0 → column clash: cols pehle se 0 hold karta hai.
- col 1 → ↗ anti-diagonal clash: r+c yahan $2 + 1 = 3$ hai, row-1 queen ke $1 + 2 = 3$ se match karta hai.
- col 2 → column clash: cols pehle se 2 hold karta hai. Dead end — row 2 ka har column kisi na kisi attack line pe mar jaata hai.
Row 1 backtrack karo (koi aur free column nahi), phir row 0 backtrack karo aur col 1, phir col 2 try karo — same conflicts se symmetric dead ends. Kyun symmetric? Board chhota hai; same row/diagonal collisions repeat hoti hain.
res start mein [] tha aur koi base case kabhi fire nahi hua, isliye res empty rehta hai. [] return karo.

Verify: 3-Queens (aur 2-Queens) ke 0 solutions hain. $n = 1, 2, 3, 4$ ke liye N-Queens solution count $1, 0, 0, 2$ hai. ✓

Example 7 — First solution only (Cell G)

Worked example Sudoku short-circuit

Statement: Ek Sudoku solver ko ek filled grid return karke rukna hai.

Forecast: Code ko kaise pata chalta hai ki rukna hai instead of saare fillings dhundhne ke?

Steps: Yahan bt() res mein collect karne ki jagah boolean return karta hai.

bt() True/False return karta hai. Kyun? Upar bubble karta hua True matlab "mere neeche ek full solution complete hua."
Jab kisi cell mein ek digit kaam kare: if bt(): return True. Kyun early return? Jaise hi ek deep call succeed hoti hai, hum baaki saare digits aur siblings abandon kar dete hain — koi waste nahi.
N-Queens (Ex 5) se contrast karo: usne kuch return nahi kiya aur saari answers ke liye res fill karne ko sab kuch explore kiya. Kyun fark hai? Output shape. "Ek answer" ⇒ short-circuit; "saare answers" ⇒ full traversal.
Agar kisi cell mein koi digit kaam nahi karta, False return karo — caller phir apna choice undo karta hai. Kyun? Failure propagate hona chahiye taaki parent apna agla option try kare.

Verify (logic, numeric nahi): Short-circuit ke saath recorded solutions = 1. Contrast ko concrete banane ke liye, ek modest depth pe full traversal se compare karo: depth 9 ki ek branch jahan har node ke 2 open choices hain, $2^{9} = 512$ leaves explore karta hai, jabki short-circuit pehli success pe rok deta hai — $1 ≪ 512$ . (Yeh $2^{9}$ sirf ek illustrative full-traversal size hai saving dikhane ke liye, nahi Sudoku ke 9-way branching tree ka literal count.) ✓ (VERIFY mein $1 < 2^{9}$ ke roop mein check kiya).

Example 8 — Count, don't list (Cell H)

Worked example

[1,2,3,4] ke subsets count karo jo 5 sum karte hain Statement: 5 sum karne wale subsets ki sankhya return karo. Koi list nahi chahiye.

Forecast: {1,2,3,4} ke kaun se subsets 5 add karte hain? Count guess karo.

Steps: List res ki jagah, hum ek single integer accumulator rakhte hain. Concretely, count = 0 initialize karo (recursion se shared ek variable, e.g. nonlocal count), aur function bilkul end mein count return karta hai.

Ex 3 ki tarah take/skip pe backtrack karo, lekin ek running total carry karo (path mein abhi ke items ka sum). Kyun? Same tree, alag bookkeeping.
Leaf pe, res.append(path[:]) ki jagah, if total == 5: count += 1 karo. Kyun no copy? Hum subset store kabhi nahi karte, sirf tally karte hain — koi shared-state copy trap nahi.
Jab total > 5 ho tab prune karo. Kyun? Elements positive hain, isliye jab hum target exceed kar lein to branch recover nahi kar sakta — classic early pruning.
Root call khatam hone ke baad, return count. Enumerate karo: {1,4} → 5, {2,3} → 5. {1,2,3,4} ka koi aur subset 5 nahi reach karta.

Verify: 5 sum karne wale subsets: {1,4} aur {2,3} → count = 2. Exhaustively check kiye gaye saare 16 subsets exactly 2 dete hain. ✓

Example 9 — Duplicates in input (Cell I)

Worked example

nums = [1, 2, 2] ke unique subsets Statement: Jab input mein repeats hoon to distinct subsets, res mein collect karo.

Forecast: Naïve $2^{3} = 8$ subsets — lekin kitne distinct hain?

Steps:

Pehle sort karo: nums = [1,2,2]. Kyun sort? Duplicates adjacent ho jaate hain, isliye hum unhe spot karke skip kar sakte hain.
Choices iterate karo; har level pe, same level ke andar kisi value ko apne predecessor ke equal hone par skip karo. Kyun? "Pehla 2" choose karna phir "doosra 2" alag branches ke roop mein [2] jaise identical subsets ke do copies produce karta hai.
res mein land karne wale distinct subsets: [], [1], [2], [1,2], [2,2], [1,2,2]. Kyun yeh six? Hum multiplicity rakhte hain ([2,2] real hai) lekin duplicates pick karne ka order nahi.

Verify: Naïve $2^{3} = 8$ ; do collisions hain — duplicate [2] aur duplicate [1,2]. Distinct count $= 8 - 2 = 6$ . ✓

Example 10 — Real-world word problem (Cell J)

Worked example 3 guests ka dinner seating

Statement: Alice, Bob, Carol 3 chairs ki ek row mein baithe hain, lekin Alice Bob ke saath nahi baithegi. Kitne seatings allowed hain?

Forecast: Total orderings $3! = 6$ ; constraint ke baad kitne bachte hain?

Steps:

Har seating ko nums = [A,B,C] ka ek permutation model karo, res mein collect karo. Kyun? "Row mein order" exactly ek permutation hai.
Record karne se pehle ek validity check add karo: aise arrangement reject karo jahan A aur B adjacent chairs pe hoon. Yahan leaf pe kyun prune karo? Adjacency tabhi pata chalti hai jab poori row fix ho; bade problems ke liye tum partial rows prune karte.
Saare 6 enumerate karo aur filter karo: forbidden hain A B C, B A C, C A B, C B A (A,B adjacent). Allowed: A C B, B C A. Sirf do kyun? C ko A aur B ke beech baithna hai unhe separate karne ke liye.

Verify: Allowed seatings = 2 out of $3! = 6$ . (C beech mein, A aur B dono ends pe kisi bhi order mein: $2$ arrangements.) ✓

Recall Har example kaun sa cell tha?

Empty input ::: Ex 1 Singleton ::: Ex 2 Exponential subsets ::: Ex 3 Factorial permutations ::: Ex 4 All-solutions pruning ::: Ex 5 No solution exists ::: Ex 6 First-solution short-circuit ::: Ex 7 Count not list ::: Ex 8 Duplicates ::: Ex 9 Word problem ::: Ex 10

Yeh bhi dekho: kyun $2^n$ aur $n!$ blow up karte hain, Branch-and-Bound (bounds ke saath pruning), aur Dynamic Programming (jab subproblems overlap karte hain).