""" 06 - Recursion and Backtracking: প্রতিটা core pattern, runnable আর commented। Contents: 1. factorial - decrease-and-conquer, recursion-এর hello-world 2. fib_naive / fib_memo - recursion tree, তারপর memoization সেটা ধসিয়ে দেয় 3. subsets - include/exclude branching (2^n leaves) 4. permutations - choose-each-remaining (n! leaves) 5. solve_n_queens - board printing সহ constraint backtracking শুধু standard library। চালাও: python implementation.py সব assert pass করতে হবে; demo একটা recursion trace আর একটা queens board print করে। """ from functools import lru_cache # --------------------------------------------------------------------- # 1. Factorial — decrease-and-conquer # --------------------------------------------------------------------- def factorial(n): """Recursion দিয়ে n!। Base case সবার আগে: definition অনুযায়ী factorial(0) হলো 1। Progress: প্রতিটা call n-কে 1 কমায়, তাই base case-এ পৌঁছাতেই হবে। Leap of faith: ধরে নাও factorial(n - 1) ঠিক; তাহলে n * সেটাও ঠিক। """ if n == 0: # base case return 1 return n * factorial(n - 1) # এক ধাপ কাজ + একটা ছোট problem # --------------------------------------------------------------------- # 2. Fibonacci — naive (exponential) vs memoized (linear) # --------------------------------------------------------------------- def fib_naive(n, call_counter=None): """Textbook fib। সঠিক কিন্তু O(2^n): recursion tree node repeat করে। call_counter (1-element-এর একটা list) দিয়ে demo কয়টা call হলো তা গুনতে পারে — exponential blowup-টা একটা সংখ্যা হয়ে চোখে দেখা যায়। """ if call_counter is not None: call_counter[0] += 1 if n <= 1: # দুটো base case: fib(0)=0, fib(1)=1 return n return fib_naive(n - 1, call_counter) + fib_naive(n - 2, call_counter) @lru_cache(maxsize=None) def fib_memo(n): """একই recursion + একটা cache = O(n)। lru_cache পর্দার আড়ালে (arguments -> answer) একটা dict-এ মনে রাখে। প্রতিটা আলাদা n ঠিক একবার compute হয়; repeat-গুলো O(1) lookup। এটাই top-down dynamic programming (দেখো ../12-dynamic-programming/)। """ if n <= 1: return n return fib_memo(n - 1) + fib_memo(n - 2) # --------------------------------------------------------------------- # 3. Subsets — the include/exclude branch # --------------------------------------------------------------------- def subsets(nums): """nums-এর সব subset। প্রতিটা element-এর জন্য: নাও, বা নিও না। Shared `path` list-টাই সবচেয়ে গুরুত্বপূর্ণ একটা mechanic: append = choose recurse = explore pop = un-choose (sibling branch-এর জন্য path restore করে) Result-গুলোকে SNAPSHOT হতে হবে (path[:]) — live list-টা বদলাতেই থাকে। """ out = [] def go(i, path): if i == len(nums): # শেষ element পার হয়ে গেছি: out.append(path[:]) # path-টাই একটা সম্পূর্ণ subset return # Branch A: nums[i] include করো path.append(nums[i]) go(i + 1, path) path.pop() # Branch B: nums[i] exclude করো go(i + 1, path) go(0, []) return out # --------------------------------------------------------------------- # 4. Permutations — choose each remaining # --------------------------------------------------------------------- def permutations(nums): """nums-এর সব ordering। Recursion-এর depth বলে আমরা কোন SLOT ভরছি। For-loop বলে সেই slot-এ কী try করছি (যেকোনো unused value)। `used` একটা hash set (05-hashing-এর seen-set pattern), O(1) check-এর জন্য। """ out = [] used = set() def go(path): if len(path) == len(nums): out.append(path[:]) return for x in nums: if x in used: continue # আগের কোনো slot-এ আগেই বসানো used.add(x) # choose path.append(x) go(path) # explore path.pop() # un-choose (choose-এর নিখুঁত আয়না) used.discard(x) go([]) return out # --------------------------------------------------------------------- # 5. N-Queens — constraint backtracking # --------------------------------------------------------------------- def solve_n_queens(n): """n x n board-এ n-টা queen এমনভাবে বসাও যেন কেউ কাউকে attack না করে। প্রতি ROW-তে একটা queen (তাই row-তে clash হতেই পারে না)। প্রতিটা row-এ আমরা প্রতিটা column try করি; একটা column legal যদি আগের কোনো queen এগুলো share না করে: - column-টা (`cols`-এ track করা) - \\-diagonal: এর বরাবর r - c constant (`diag1`) - /-diagonal: এর বরাবর r + c constant (`diag2`) Solution-গুলোর একটা list ফেরত দেয়; প্রতিটা solution এমন একটা list যেখানে solution[r] = row r-এর queen-এর column। """ solutions = [] cols, diag1, diag2 = set(), set(), set() placement = [] # placement[r] = row r-এর জন্য বাছাই করা column def place(row): if row == n: # সব row ভরা: একটা solution! solutions.append(placement[:]) return for col in range(n): if col in cols or (row - col) in diag1 or (row + col) in diag2: continue # attacked — এই option prune করো # choose cols.add(col); diag1.add(row - col); diag2.add(row + col) placement.append(col) # explore place(row + 1) # un-choose (সব state restore করো, choose-এর হুবহু আয়না) placement.pop() cols.discard(col); diag1.discard(row - col); diag2.discard(row + col) place(0) return solutions def board_string(solution): """একটা N-Queens solution-এর ASCII board। 'Q' = queen, '.' = empty।""" n = len(solution) rows = [] for r in range(n): rows.append(" ".join("Q" if c == solution[r] else "." for c in range(n))) return "\n".join(rows) # --------------------------------------------------------------------- # Demo + tests # --------------------------------------------------------------------- if __name__ == "__main__": # --- factorial --- assert factorial(0) == 1 assert factorial(1) == 1 assert factorial(5) == 120 assert factorial(10) == 3628800 # --- fibonacci: correctness, তারপর call-count-এর শিক্ষা --- expected_fib = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] assert [fib_naive(i) for i in range(11)] == expected_fib assert [fib_memo(i) for i in range(11)] == expected_fib assert fib_memo(60) == 1548008755920 # naive এখানে ~যুগ লাগাত counter = [0] fib_naive(20, counter) naive_calls = counter[0] print(f"fib_naive(20) made {naive_calls} calls " f"(memoized needs only ~21). That gap IS the recursion-tree waste.") assert naive_calls > 10000 # exponential blowup, চোখের সামনে # --- subsets --- result = subsets([1, 2, 3]) assert len(result) == 8 # 2^3 as_sets = sorted(tuple(sorted(s)) for s in result) assert as_sets == [(), (1,), (1, 2), (1, 2, 3), (1, 3), (2,), (2, 3), (3,)] assert subsets([]) == [[]] # কিছু-না-র একটাই subset: empty set # result-গুলো independent snapshot হতে হবে, এক list-এর alias না r = subsets([1, 2]) r[0].append(999) assert all(999 not in s for s in r[1:]) # --- permutations --- perms = permutations([1, 2, 3]) assert len(perms) == 6 # 3! assert sorted(map(tuple, perms)) == [ (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1) ] assert all(sorted(p) == [1, 2, 3] for p in perms) # প্রতিটা সব item ব্যবহার করে assert permutations([7]) == [[7]] # --- n-queens --- assert len(solve_n_queens(1)) == 1 assert len(solve_n_queens(2)) == 0 # 2x2-তে অসম্ভব assert len(solve_n_queens(3)) == 0 # 3x3-তে অসম্ভব four = solve_n_queens(4) assert len(four) == 2 # বিখ্যাত সেই জোড়া assert sorted(four) == [[1, 3, 0, 2], [2, 0, 3, 1]] assert len(solve_n_queens(6)) == 4 assert len(solve_n_queens(8)) == 92 # classic chessboard-এর উত্তর # ফেরত-আসা প্রতিটা placement সত্যিই conflict-free হতে হবে for sol in four: n = len(sol) assert len(set(sol)) == n # আলাদা আলাদা col assert len({r - sol[r] for r in range(n)}) == n # আলাদা \ diag assert len({r + sol[r] for r in range(n)}) == n # আলাদা / diag print("\nOne 4-queens solution, choose->explore->un-choose found it:\n") print(board_string(four[0])) print("\nAll asserts passed. Recursion & backtracking toolkit verified.")