Backtracking — N-queens, subset sum আর Hamiltonian cycle

১ · ধারণা — চেষ্টা করুন, যাচাই করুন, না হলে ফিরে আসুন

সকালে অফিসে বের হওয়ার মুখে চাবি খুঁজে পাচ্ছেন না। আপনি কী করেন? একটি ঘরে ঢোকেন — শোবার ঘর। টেবিলে দেখেন, নেই; ড্রয়ারে দেখেন, নেই। শোবার ঘরের সব জায়গা শেষ হলে বেরিয়ে আসেন — যেখান থেকে ঢুকেছিলেন, সেই বারান্দায় — আর পরের ঘরে ঢোকেন। কোনো ঘর দুবার খোঁজেন না, আর কোনো ঘরে “এখানে নিশ্চয়ই নেই” বুঝলে (ধরুন রান্নাঘর, যেখানে আজ যাননি) পুরো ঘরটিই বাদ দেন।

Backtracking হলো এমন সমস্যার সাধারণ পদ্ধতি, যেখানে উত্তর একটি সিদ্ধান্তের ধারা — x₁, x₂, …, xₙ — আর প্রতিটি সিদ্ধান্তের কয়েকটি বিকল্প আছে। তিনটি ধাপ বারবার চলে:

1. চেষ্টা (choose): পরের সিদ্ধান্তের একটি বিকল্প বসান।
2. যাচাই (check): এ পর্যন্ত বসানো সিদ্ধান্তগুলো কি এখনো সব শর্ত মানছে? না মানলে এই পথে আর এগোনোর মানে নেই।
3. ফেরত (undo): এই বিকল্পের নিচের সব সম্ভাবনা দেখা শেষ হলে (বা যাচাইয়ে ব্যর্থ হলে) সিদ্ধান্তটি মুছে পরের বিকল্প ধরুন। সব বিকল্প শেষ হলে আরও এক ধাপ পেছনে যান।

সাধারণ brute force-এর সাথে পার্থক্য দ্বিতীয় ধাপে। Brute force প্রথমে পুরো একটি সম্ভাব্য উত্তর বানায়, তারপর যাচাই করে — ৮টি রানির জন্য, প্রতি সারিতে একটি করে ধরলেও, ৮⁸ ≈ ১ কোটি ৬৭ লাখ বোর্ড। Backtracking আংশিক উত্তরেই যাচাই করে: প্রথম দুটি রানি যদি একে অন্যকে আক্রমণ করে, বাকি ছয়টি কোথায় বসবে তা ভাবারই দরকার নেই — একসাথে ৮⁶ ≈ ২ লাখ ৬২ হাজার বোর্ড বাদ। এই আগাম বাদ দেওয়াকে বলে pruning (গাছের ডাল ছাঁটা), আর এই পর্বের প্রায় সব কৌশল আসলে ভালো pruning-এর কৌশল।

২ · State-space tree আর choose–explore–un-choose টেমপ্লেট

সব সম্ভাব্য সিদ্ধান্ত-ধারাকে একটি গাছ হিসেবে কল্পনা করুন — state-space tree. Root হলো খালি আংশিক সমাধান (কোনো সিদ্ধান্ত নেওয়া হয়নি)। গভীরতা k-এর একটি node মানে প্রথম k টি সিদ্ধান্ত নেওয়া হয়েছে; তার প্রতিটি সন্তান (k + 1)-তম সিদ্ধান্তের একটি বিকল্প। Leaf হলো হয় পূর্ণ সমাধান, নয়তো এমন অবস্থা যেখান থেকে আর এগোনো যায় না। গাছটি মেমরিতে কখনো বানানো হয় না — এটি একটি implicit graph, যার প্রতিবেশী দরকারের সময় হিসাব হয়। Backtracking এই গাছে DFS চালায়, আর pruning মানে কিছু node-এ পৌঁছে বুঝে ফেলা যে তার নিচের পুরো উপ-গাছে কিছু নেই।

Pseudocode — the backtracking template (state = the partial solution)

solve(state):
    if state is a complete solution:
        record(state); return               // a leaf we want
    for each option x for the next decision:
        if not feasible(state, x): continue // prune: this child can never work
        apply x to state                    // CHOOSE
        solve(state)                        // EXPLORE the subtree below
        undo x from state                   // UN-CHOOSE: state is exactly as before

শেষ লাইনটিই backtracking-এর প্রাণ। প্রতিটি ডাকের জন্য state-এর নতুন কপি না বানিয়ে, একটিই অ্যারে বা তালিকা রাখা হয়; নিচে যাওয়ার আগে বদলানো হয়, ফিরে এসে ঠিক উল্টোভাবে বদলে আগের অবস্থায় ফেরানো হয়। তাই বাড়তি জায়গা লাগে শুধু গাছের গভীরতার সমান — recursion depth আর state মিলে সাধারণত O(n). Undo ভুলে গেলে (বা অর্ধেক করলে) পরের শাখা আগের শাখার ময়লা নিয়ে শুরু করে — backtracking কোডের সবচেয়ে প্রচলিত বাগ।

তিনটি মৌলিক গাছ — subset, permutation, combination

পর্ব ৭-এ recursion দিয়ে subset আর permutation তৈরি করেছিলেন। এখন সেগুলোকে state-space tree হিসেবে দেখুন, কারণ প্রায় সব backtracking সমস্যা এই তিনটির একটির ওপর শর্ত বসিয়ে তৈরি:

সংখ্যাগুলো কেন: subset-এ n টি স্বাধীন হ্যাঁ/না, তাই 2 · 2 · … · 2 = 2ⁿ. Permutation-এ প্রথম ঘরে n টি বিকল্প, দ্বিতীয়তে n − 1, …, তাই n!. Combination-এ ক্রম গুরুত্বহীন, তাই n!/(n − k)! টি সাজানো বাছাইয়ের প্রতিটি দল k! বার গোনা হয়েছিল: C(n, k) = n!/(k! (n − k)!). Combination গাছে ক্রম-ভেদে একই দল দুবার না আসতে, পরের জিনিস সবসময় আগেরটির পরের সূচক থেকে নেওয়া হয় — তাই {1, 3} আসে, {3, 1} আসে না।

সময়: n! টি leaf, প্রতিটি ছাপতে O(n), আর ভেতরের node মোট প্রায় (e − 1) · n!, প্রতিটিতে O(n)-এর লুপ — সব মিলে Θ(n · n!). জায়গা: path, used আর recursion — Θ(n). Subset গাছে একইভাবে 2ⁿ⁺¹ − 1 node, প্রতিটিতে O(1) কাজ, আর leaf ছাপতে O(n): সব মিলে Θ(n · 2ⁿ). এই “node গুনুন, তারপর প্রতি node-এর কাজ দিয়ে গুণ করুন” পদ্ধতিই অংশ ৭-এ সাধারণ নিয়ম হবে।

৩ · N-queens — সারি ধরে রানি বসানো

দাবার রানি নিজের সারি, কলাম আর দুই কোণাকুণি রেখায় যত দূর খুশি যেতে পারে। N-queens সমস্যা: n × n বোর্ডে n টি রানি বসান যাতে কেউ কাউকে আক্রমণ না করে। প্রতিটি সারিতে ঠিক একটি রানি থাকতেই হবে (n টি সারিতে n টি রানি, আর এক সারিতে দুটি থাকলে তারা একে অন্যকে আক্রমণ করে)। তাই সিদ্ধান্তের ধারা হলো: “সারি 0-এর রানি কোন কলামে, সারি 1-এর রানি কোন কলামে, …” — গভীরতা n-এর একটি গাছ, প্রতিটি node-এ n টি বিকল্প। নিচে ৪ × ৪ বোর্ডে প্রথম সমাধান খোঁজা (কলাম বাঁ থেকে ডানে চেষ্টা করা হয়; x = এই সারিতে এই ঘর চেষ্টা করে বাদ):

O(1)-এ নিরাপত্তা যাচাই — কলাম আর দুই কোণাকুণির অ্যারে

নতুন রানি (r, c) নিরাপদ কি না, তা আগের সব রানির সাথে মিলিয়ে দেখলে প্রতিবার O(n). তার বদলে তিনটি boolean অ্যারে রাখুন। একই কলামের সব ঘরে c সমান। একই “/” কোণাকুণিতে r + c সমান (ডানে-ওপরে গেলে r কমে, c বাড়ে), মান 0 থেকে 2n − 2. একই “\” কোণাকুণিতে r − c সমান; ঋণাত্মক সূচক এড়াতে r − c + n − 1 লিখুন, মানও 0 থেকে 2n − 2. তাহলে নিরাপত্তা-যাচাই তিনটি অ্যারে-পড়া, আর বসানো ও তোলা তিনটি করে লেখা — সব O(1).

নিচের প্রোগ্রাম n = 1 থেকে 8 পর্যন্ত সব সমাধান গোনে, প্রতিবার কতটি node (place-এর ডাক) লাগল তা-ও, আর শেষে ৬ × ৬-এর প্রথম সমাধানটি আঁকে:

#include <iostream>
#include <vector>
using namespace std;

int n, cnt;
long long nodes;
vector<int> pos, first;              // pos[r] = column of the queen in row r
vector<bool> col, d1, d2;            // used column, "/" diagonal r+c, "\" diagonal r-c+n-1

void place(int r) {                  // put a queen in row r
    ++nodes;
    if (r == n) { if (cnt++ == 0) first = pos; return; }
    for (int c = 0; c < n; ++c) {
        if (col[c] || d1[r + c] || d2[r - c + n - 1]) continue;   // O(1) safety check
        col[c] = d1[r + c] = d2[r - c + n - 1] = true;  pos[r] = c;   // choose
        place(r + 1);                                                 // explore
        col[c] = d1[r + c] = d2[r - c + n - 1] = false;              // un-choose
    }
}
void solve(int size) {
    n = size; cnt = 0; nodes = 0; pos.assign(n, -1);
    col.assign(n, false); d1.assign(2 * n - 1, false); d2.assign(2 * n - 1, false);
    place(0);
}
int main() {
    for (int k = 1; k <= 8; ++k) {
        solve(k);
        cout << "n=" << k << " solutions=" << cnt << " nodes=" << nodes << '\n';
    }
    solve(6);
    cout << "first 6x6 board, queen columns:";
    for (int c : first) cout << ' ' << c;
    cout << '\n';
    for (int r = 0; r < 6; ++r)
        for (int c = 0; c < 6; ++c) cout << (first[r] == c ? 'Q' : '.') << (c < 5 ? ' ' : '\n');
}

n=1 solutions=1 nodes=2
n=2 solutions=0 nodes=3
n=3 solutions=0 nodes=6
n=4 solutions=2 nodes=17
n=5 solutions=10 nodes=54
n=6 solutions=4 nodes=153
n=7 solutions=40 nodes=552
n=8 solutions=92 nodes=2057
first 6x6 board, queen columns: 1 3 5 0 2 4
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .

def solve(n):
    col, d1, d2 = [False] * n, [False] * (2 * n - 1), [False] * (2 * n - 1)
    pos, first = [-1] * n, []
    count = nodes = 0

    def place(r):                                   # put a queen in row r
        nonlocal count, nodes
        nodes += 1
        if r == n:
            if count == 0:
                first.extend(pos)                   # remember the first board
            count += 1
            return
        for c in range(n):
            if col[c] or d1[r + c] or d2[r - c + n - 1]:
                continue                            # O(1) safety check
            col[c] = d1[r + c] = d2[r - c + n - 1] = True    # choose
            pos[r] = c
            place(r + 1)                                     # explore
            col[c] = d1[r + c] = d2[r - c + n - 1] = False   # un-choose

    place(0)
    return count, nodes, first

for k in range(1, 9):
    cnt, nodes, _ = solve(k)
    print(f"n={k} solutions={cnt} nodes={nodes}")
_, _, board = solve(6)
print("first 6x6 board, queen columns:", *board)
for r in range(6):
    print(" ".join("Q" if board[r] == c else "." for c in range(6)))

n=1 solutions=1 nodes=2
n=2 solutions=0 nodes=3
n=3 solutions=0 nodes=6
n=4 solutions=2 nodes=17
n=5 solutions=10 nodes=54
n=6 solutions=4 nodes=153
n=7 solutions=40 nodes=552
n=8 solutions=92 nodes=2057
first 6x6 board, queen columns: 1 3 5 0 2 4
. Q . . . .
. . . Q . .
. . . . . Q
Q . . . . .
. . Q . . .
. . . . Q .

// bitmask N-queens: count all solutions; call go(0, 0, 0) with all = (1 << n) - 1
long long go(int cols, int ld, int rd) {
    if (cols == all) return 1;                    // every column has a queen
    long long total = 0;
    for (int avail = all & ~(cols | ld | rd); avail; avail &= avail - 1) {
        int bit = avail & -avail;                 // lowest free square in this row
        total += go(cols | bit, ((ld | bit) << 1) & all, (rd | bit) >> 1);
    }
    return total;
}

৪ · Subset sum — দুটি সীমা দিয়ে গাছ ছাঁটা

ঈদের আগে একটি স্কুলের ছাত্রকল্যাণ তহবিলে ঠিক ১৫ হাজার টাকা দিতে হবে, আর হাতে কয়েকটি আলাদা অনুদানের খাম আছে — ৮, ৬, ৭, ৫, ৩, ১০ আর ৯ হাজার। খাম ভাঙা যাবে না। কোন কোন খাম মিলে ঠিক ১৫ হয়? এটি subset sum: n টি ধনাত্মক সংখ্যা আর লক্ষ্য T; যোগফল ঠিক T এমন সব subset বের করুন। State-space tree হলো subset গাছ — প্রতিটি স্তরে “এই খাম নেব, না নেব না”, ২⁷ = ১২৮টি leaf আর ২৫৫টি node.

Pruning-এর জন্য প্রথমে সংখ্যাগুলো ছোট থেকে বড় সাজান: 3 5 6 7 8 9 10. আর rest[i] = a[i] + a[i+1] + … + a[n−1] আগেই হিসাব করে রাখুন (এটি suffix sum — পর্ব ১৭-এর prefix sum-এরই উল্টো দিক থেকে হিসাব). এখন index i-তে চলতি যোগফল s নিয়ে দাঁড়ালে তিনটি নিয়ম:

• s = T: একটি সমাধান! আর কিছু নেওয়ার দরকার নেই (সব ধনাত্মক, নিলে বেড়ে যাবে)।
• সম্ভাব্যতার সীমা (feasibility): s + a[i] > T হলে a[i] নেওয়া যায় না — আর সাজানো বলে পরের সবগুলো আরও বড়, কোনোটিই নেওয়া যাবে না। পুরো উপ-গাছ বাদ।
• বাকি-যোগফলের সীমা (bound): s + rest[i] < T হলে বাকি সব খাম নিলেও T-তে পৌঁছানো যাবে না। পুরো উপ-গাছ বাদ।

ছোট একটি উদাহরণে দেখুন: সংখ্যা 2 3 5 6 (সাজানো), T = 8, তাই rest = 16, 14, 11, 6. প্রতিটি node-এ আগে “নেব” শাখা, তারপর “নেব না”:

পুরো খাম-সমস্যায় দুই সংস্করণই চালিয়ে node গুনুন — pruning ছাড়া সাধারণ গাছ, আর দুই সীমাসহ:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<int> a = {8, 6, 7, 5, 3, 10, 9}, rest, cur;
vector<vector<int>> found;
const int T = 15;
long long nodes = 0;

void plain(size_t i, int s) {                 // no pruning: visit the whole tree
    ++nodes;
    if (i == a.size()) { if (s == T) found.push_back(cur); return; }
    cur.push_back(a[i]); plain(i + 1, s + a[i]); cur.pop_back();   // take a[i]
    plain(i + 1, s);                                               // skip a[i]
}
void pruned(size_t i, int s) {
    ++nodes;
    if (s == T) { found.push_back(cur); return; }
    if (i == a.size() || s + a[i] > T || s + rest[i] < T) return;  // too big / can never reach T
    cur.push_back(a[i]); pruned(i + 1, s + a[i]); cur.pop_back();
    pruned(i + 1, s);
}
int main() {
    sort(a.begin(), a.end());                 // small items first
    rest.assign(a.size() + 1, 0);             // rest[i] = a[i] + ... + a[n-1]
    for (size_t i = a.size(); i-- > 0;) rest[i] = rest[i + 1] + a[i];
    cout << "items:";
    for (int x : a) cout << ' ' << x;
    cout << " target: " << T << '\n';
    for (int pass = 0; pass < 2; ++pass) {
        found.clear(); nodes = 0;
        if (pass == 0) plain(0, 0); else pruned(0, 0);
        cout << (pass == 0 ? "without pruning" : "with pruning   ") << ": nodes=" << nodes << " subsets=" << found.size() << '\n';
    }
    for (auto& sub : found) {
        for (size_t j = 0; j < sub.size(); ++j) cout << (j ? " + " : "") << sub[j];
        cout << " = " << T << '\n';
    }
}

items: 3 5 6 7 8 9 10 target: 15
without pruning: nodes=255 subsets=4
with pruning   : nodes=45 subsets=4
3 + 5 + 7 = 15
5 + 10 = 15
6 + 9 = 15
7 + 8 = 15

a = sorted([8, 6, 7, 5, 3, 10, 9])     # sort once: small items first
T = 15
rest = [sum(a[i:]) for i in range(len(a) + 1)]   # rest[i] = a[i] + ... + a[n-1]
cur, found, nodes = [], [], 0

def plain(i, s):                     # no pruning: visit the whole tree
    global nodes
    nodes += 1
    if i == len(a):
        if s == T:
            found.append(cur[:])
        return
    cur.append(a[i]); plain(i + 1, s + a[i]); cur.pop()   # take a[i]
    plain(i + 1, s)                                        # skip a[i]

def pruned(i, s):
    global nodes
    nodes += 1
    if s == T:
        found.append(cur[:])
        return
    if i == len(a) or s + a[i] > T or s + rest[i] < T:
        return                       # too big already / can never reach T
    cur.append(a[i]); pruned(i + 1, s + a[i]); cur.pop()
    pruned(i + 1, s)

print("items:", *a, "target:", T)
for name, f in (("without pruning", plain), ("with pruning   ", pruned)):
    found.clear(); nodes = 0
    f(0, 0)
    print(f"{name}: nodes={nodes} subsets={len(found)}")
for sub in found:
    print(" + ".join(map(str, sub)), "=", T)

items: 3 5 6 7 8 9 10 target: 15
without pruning: nodes=255 subsets=4
with pruning   : nodes=45 subsets=4
3 + 5 + 7 = 15
5 + 10 = 15
6 + 9 = 15
7 + 8 = 15

৫ · Sudoku আর graph colouring — শর্ত মেনে মান বসানো

N-queens আর subset sum একটি বড় পরিবারের সদস্য — constraint satisfaction problem (CSP): কিছু ভেরিয়েবল, প্রত্যেকের কিছু সম্ভাব্য মান, আর কিছু শর্ত। Backtracking-এ একটি করে ভেরিয়েবলে মান বসানো হয়, শর্ত ভাঙলেই ফেরত।

Sudoku — সংক্ষেপে

৯ × ৯ ঘর, কিছু আগে থেকে ভরা। প্রতিটি খালি ঘর একটি ভেরিয়েবল, মান 1–9; শর্ত — প্রতিটি সারি, কলাম আর ৩ × ৩ বাক্সে প্রতিটি অঙ্ক একবার। N-queens-এর মতোই প্রতিটি সারি, কলাম আর বাক্সের জন্য “কোন অঙ্ক ব্যবহৃত” অ্যারে (বা ৯-bit-এর mask) রাখলে প্রতিটি যাচাই O(1). সরল পদ্ধতি: প্রথম খালি ঘরটি নিন, 1 থেকে 9 পর্যন্ত বৈধ প্রতিটি অঙ্ক বসিয়ে বাকিটা recursively সমাধান করুন, না হলে মুছে পরের অঙ্ক। এর চেয়ে অনেক ভালো: সবসময় সেই খালি ঘরটি নিন যেখানে সবচেয়ে কম বৈধ অঙ্ক আছে — যদি একটি ঘরে মাত্র একটি অঙ্ক বসতে পারে, সেখানে কোনো শাখাই তৈরি হয় না; আর শূন্য হলে সাথে সাথে ফেরত। এই most-constrained-first নিয়মে সাধারণ পত্রিকার sudoku কয়েকশো node-এই মিলে যায়।

Graph colouring (m-colouring)

একটি জেলার পাশাপাশি উপজেলাগুলো মানচিত্রে আলাদা রঙে আঁকতে হবে, আর হাতে মাত্র m টি রং। উপজেলা = vertex, সীমানা ভাগ করা = edge. প্রশ্ন: প্রতিটি vertex-কে m টির একটি রং দেওয়া যায় কি না, যাতে কোনো edge-এর দুই প্রান্ত একই রঙের না হয় (graph colouring). Vertex 0, 1, 2, … ক্রমে রং বসান; প্রতিটিতে শুধু সেই রংগুলো চেষ্টা করুন যা কোনো ইতিমধ্যে-রং-পাওয়া প্রতিবেশীর সাথে মেলে না:

Pseudocode — m-colouring by backtracking (0-based vertices, colours 1..m, 0 = none)

colourFrom(v):
    if v == n: return true                          // every vertex has a colour
    for c = 1 .. m:
        if no neighbour u of v has colour[u] == c:  // feasibility: O(deg v)
            colour[v] = c                           // choose
            if colourFrom(v + 1): return true       // explore
            colour[v] = 0                           // un-choose
    return false                                    // no colour fits: backtrack

সময়: গভীরতা v-তে সর্বোচ্চ mᵛ টি node, প্রতিটিতে m টি রং × O(deg v) যাচাই — যোগ করলে worst case O(mⁿ · (n + E)); জায়গা O(n). দুটি বাস্তব কৌশল: (১) প্রথম vertex-এ রং 1 স্থির করে দিন — রংগুলোর নাম অদলবদল করলে একই সমাধান, তাই এতে m গুণ কাজ বাঁচে (একে বলে symmetry breaking); (২) বেশি degree-র vertex আগে রং করুন, বা যার প্রতিবেশীরা এর মধ্যেই সবচেয়ে বেশি আলাদা রং নিয়েছে (DSATUR নামের heuristic-এর ধারণা) — আবারও most-constrained-first. m = 2 হলে backtracking লাগেই না: গ্রাফটি bipartite কি না BFS দিয়ে O(V + E)-এ বলা যায় (পর্ব ৪০). কিন্তু m = 3-এই প্রশ্নটি NP-complete. আর একটি বিখ্যাত সত্য: সমতলের যেকোনো মানচিত্র (planar graph) ৪টি রঙেই রং করা যায় — four colour theorem, Appel আর Haken ১৯৭৬ সালে কম্পিউটারের সাহায্যে প্রমাণ করেন।

৬ · Hamiltonian cycle — সব vertex ঠিক একবার

একজন ডেলিভারি কর্মী গুদাম থেকে বের হয়ে কয়েকটি দোকানের প্রতিটিতে ঠিক একবার গিয়ে গুদামে ফিরতে চান, শুধু সরাসরি রাস্তা ধরে। এমন একটি পথ — যা গ্রাফের প্রতিটি vertex ঠিক একবার ছুঁয়ে শুরুতে ফেরে — হলো Hamiltonian cycle; শুরুতে না ফিরলে Hamiltonian path. পর্ব ৩৯-এর Euler circuit (প্রতিটি edge একবার) degree দেখেই O(V + E)-এ বলা যায়; কিন্তু প্রতিটি vertex একবার — এর কোনো দ্রুত পদ্ধতি জানা নেই।

Backtracking: vertex 0 থেকে শুরু করুন (cycle-এ সবাই আছে, তাই শুরু যেকোনো জায়গা থেকে)। পথের শেষ vertex-এর একটি অদেখা প্রতিবেশী যোগ করুন, এগোন; সব vertex পথে এসে গেলে দেখুন শেষ vertex থেকে 0-তে edge আছে কি না। কোনো অদেখা প্রতিবেশী না থাকলে শেষ vertex তুলে নিন। এটি permutation গাছ, শুধু শর্ত হলো “পরপর দুজনের মধ্যে edge থাকতে হবে”। গ্রাফটি এরকম (প্রতিবেশী ছোট নম্বর আগে):

        0              adj[0] = 1 2 4
      / | \            adj[1] = 0 2 3
     1--2--4           adj[2] = 0 1 4
      \    /           adj[3] = 1 4
        3              adj[4] = 0 2 3

কেন exponential: 0 স্থির রেখে বাকি n − 1 টি vertex-এর প্রতিটি ক্রমই একটি সম্ভাব্য পথ — worst case-এ (n − 1)! টি leaf, যেমন প্রায়-complete graph-এ যেখানে প্রায় সব পথ শেষ পর্যন্ত যায়, কিন্তু একটিমাত্র “শেষ edge” না থাকায় সব ব্যর্থ হয়। প্রতি node-এ প্রতিবেশী দেখতে O(n), তাই সময় O(n · n!), জায়গা O(n). Pruning সাহায্য করে — যেমন কোনো অদেখা vertex-এর সব প্রতিবেশী পথে চলে গেলে (তার আর ঢোকার বা বেরোনোর রাস্তা নেই) সাথে সাথে ফেরত — কিন্তু worst case-কে polynomial বানায় না। পর্ব ৫৫-এর bitmask DP (Held–Karp ধাঁচের) একই প্রশ্নের উত্তর O(2ⁿ · n²)-এ দেয় — এখনো exponential, কিন্তু n! থেকে অনেক কম। আর এর চেয়ে মৌলিকভাবে ভালো কিছু কেউ জানে না: Hamiltonian cycle একটি NP-complete সমস্যা — Richard Karp-এর ১৯৭২ সালের বিখ্যাত ২১টি NP-complete সমস্যার তালিকায় আছে। এর মানে কী, তা পর্ব ৬৪-এ। ওজনসহ গ্রাফে সবচেয়ে ছোট Hamiltonian cycle-ই traveling salesman problem, যার জন্য পরের পর্বে branch and bound.

৭ · Pruning-এর কৌশল আর backtracking-এর জটিলতা

জটিলতা কীভাবে গুনবেন

Backtracking-এর সময় = (দেখা node-এর সংখ্যা) × (প্রতি node-এর কাজ)। Worst case-এ node-এর সংখ্যা state-space tree-র আকার: subset গাছে Θ(2ⁿ), permutation গাছে Θ(n!), m-colouring-এ O(mⁿ) — সবই exponential বা factorial. Pruning সাধারণত গড় বা বাস্তব ইনপুটে বিশাল লাভ দেয় (৮-রানিতে ৪০,৩২০ থেকে ২,০৫৭), কিন্তু worst-case সীমা প্রায় কখনো বদলায় না — subset sum-এ এমন ইনপুট বানানো যায় যেখানে কোনো সীমাই তাড়াতাড়ি কাটে না। তাই পরীক্ষায় “backtracking-এর সময় কত?” প্রশ্নে উত্তর হবে worst case, যেমন subset sum-এ O(2ⁿ) (সমাধান ছাপাসহ O(n · 2ⁿ)), N-queens-এ O(n!) টি leaf-এর ধাঁচে, Hamiltonian-এ O(n · n!). জায়গা প্রায় সবসময় শুধু গভীরতা আর state: O(n) — DFS-এর বড় সুবিধা।

বাস্তবে node গোনাই সবচেয়ে সৎ মাপ। ওপরের দুটি প্রোগ্রামের মতো একটি nodes কাউন্টার রাখুন, ছোট n-এ বাড়িয়ে দেখুন কত গুণ বাড়ছে: N-queens-এ n = 6, 7, 8-এ 153, 552, 2057 — প্রতি ধাপে প্রায় ৩.৬–৩.৭ গুণ। এই হার থেকে বড় n-এর সময় আন্দাজ করা যায়, আর বলা যায় আপনার সময়-সীমায় কত বড় n চলবে।

৮ · Backtracking বনাম brute force বনাম DP

সিদ্ধান্তের একটি সহজ প্রশ্ন: “কোনো একটি অবস্থায় আমি কি দুটি ভিন্ন পথে পৌঁছাতে পারি, আর সেখান থেকে বাকি কাজ কি একই?” যদি হ্যাঁ, আর এমন অবস্থার সংখ্যা কম, তবে backtracking-এ memoization যোগ করুন — সেটিই top-down DP (পর্ব ৫২). Subset sum-এ (i, s) অবস্থা মাত্র n · T টি, তাই DP. কিন্তু N-queens-এ অবস্থা হলো “কোন কলাম আর কোণাকুণিগুলো দখল” — সংখ্যায় বিশাল, পুনরাবৃত্তি কম; আর সব সমাধান ছাপতে চাইলে উত্তরের আকারই exponential, কোনো পদ্ধতি তার চেয়ে কম সময়ে পারবে না। তখন ভালো pruning-সহ backtracking-ই সঠিক হাতিয়ার।

৯ · AI-এর যুগে backtracking — undo আর pruning যাচাই করুন

“N-queens solve করো” বা “sudoku solver লেখো” বললে AI সহকারী প্রায় নিশ্চিতভাবেই চলার মতো কোড দেবে — এগুলো ইন্টারনেটে সবচেয়ে বেশি লেখা সমস্যার মধ্যে পড়ে। ভুল আসে নতুন সমস্যায়, যেখানে AI-কে নিজে pruning বানাতে হয়: এমন সীমা যা আসলে সঠিক সমাধানও কেটে দেয় (ঋণাত্মক সংখ্যায় subset sum-এর সীমা), undo ভুলে যাওয়া, একই সমাধান দুবার ছাপা, বা জটিলতা নিয়ে ভুল দাবি — যেমন “pruning-এর পর এটি O(n²)”।

Backtracking-এর কোডে AI সাধারণত যেসব ভুল করে

Backtracking-এর কোড যাচাইয়ের চেকলিস্ট

• প্রতিটি choose-এর ঠিক উল্টো un-choose আছে; ছোট ইনপুটে মোট ফলের সংখ্যা 2ⁿ, n! বা C(n, k)-এর সাথে মিলিয়েছি
• Pruning-ছাড়া একটি brute force রেখে ছোট এলোমেলো ইনপুটে দুটির ফল মিলিয়েছি — stress testing
• প্রতিটি pruning-এর অনুমান (সাজানো, ধনাত্মক, সমমিতি) লিখে রেখেছি আর ইনপুট তা মানে কি না দেখেছি
• Edge case: n = 0 বা 1, কোনো সমাধান নেই, ডুপ্লিকেট মান, লক্ষ্য 0
• একটি node কাউন্টার রেখে n বাড়িয়ে দেখেছি কত বড় n সময়-সীমায় চলবে; AI-এর “polynomial” দাবি বাতিল করেছি
• সমাধান রাখার সময় কপি রেখেছি (Python-এ path[:]), আর recursion-এর গভীরতা n-এর বেশি নয়