অ্যাডভান্সড টপিক৮ মিনিট পড়া

ব্যাকট্র্যাকিং (Backtracking)

প্রতিটি সম্ভাব্য পথ ঘুরে দেখুন, তবে ডেড এন্ড বা অন্ধগলি পেলেই পেছনে ফিরে আসুন
worst case:\(O(b^d)\) — ব্রাঞ্চিং ফ্যাক্টর (branching factor) এর পাওয়ার হিসেবে গভীরতা বা ডেপথ (depth)with pruning:সমস্যার ওপর নির্ভরশীল, প্রায়ই উল্লেখযোগ্যভাবে কমpattern:বাছাই করুন (Choose) → অন্বেষণ করুন (Explore) → আগের অবস্থায় ফিরুন (Undo)

ধরুন আপনি একটি গোলকধাঁধা বা মেজ (maze) সমাধান করছেন। আপনি একটি পথ ধরে হাঁটলেন, বাঁয়ে ঘুরলেন, আরেকটু হাঁটলেন, এবং একটি দেয়ালে গিয়ে আটকে গেলেন। আপনি কিন্তু হাল ছেড়ে দেন না — আপনি ব্যাকট্র্যাক (backtrack) করে আবার আগের সংযোগস্থলে বা জংশনে ফিরে আসেন এবং এরপরের সম্ভাব্য পথটি চেষ্টা করেন। আপনি পদ্ধতিগতভাবে এটি করতেই থাকেন, যতক্ষণ না পর্যন্ত আপনি বের হওয়ার পথটি খুঁজে পান অথবা অন্তত এটুকু নিশ্চিত হন যে এখানে কোনো বের হওয়ার পথ নেই।

সংক্ষেপে এটিই হলো ব্যাকট্র্যাকিং (backtracking): একটু একটু করে একটি সমাধান তৈরি করা, এবং যখনই সেই আংশিক সমাধানটি কোনো শর্ত বা নিয়ম ভঙ্গ করে, ঠিক তক্ষুনি সেই পুরো ব্রাঞ্চ বা শাখাকে বাতিল করে দেওয়া এবং অন্য কোনো উপায় চেষ্টা করে দেখা। ডেড এন্ড বা অন্ধগলির নিচের দিকে আর কী আছে তা অন্বেষণ করার কোনো প্রয়োজন নেই।

তিন-ধাপের মূল ছন্দ (The three-step heartbeat)

প্রতিটি ব্যাকট্র্যাকিং অ্যালগরিদম ঠিক একই ছন্দে কাজ করে:

১. বাছাই করা (Choose) — বর্তমান স্লটের বা অবস্থার জন্য একটি উপযুক্ত মান বেছে নিন (যেমন: রানীর জন্য কলাম, সুডোকু ডিজিট, বা পরবর্তী যুক্ত করার আইটেম)।

২. অন্বেষণ করা (Explore) — যদি এই বাছাই হওয়া মানটি কোনো শর্ত ভঙ্গ না করে, তবে পরবর্তী স্লটের জন্য সেটিকে রিকার্স (recurse) বা পুনরাবৃত্তি করুন।

৩. আগের অবস্থায় ফেরা (Undo) — যখন রিকার্সনটি রিটার্ন করে (সেটি সমাধান খুঁজে পাক বা ডেড এন্ড বা অন্ধগলিতে পৌঁছাক), তখন আপনার বাছাই করা মানটিকে আবার মুছে নিয়ে আগের অবস্থায় ফিরে আসুন এবং এরপরের সম্ভাব্য মানটি নিয়ে চেষ্টা করুন। মূলত এই রিস্টোর (restore) বা পূর্বাবস্থায় ফিরে আসার ধাপটির জন্যই এর নামকরণ ব্যাকট্র্যাকিং করা হয়েছে।

এই "আগের অবস্থায় ফেরা বা আনডু (undo)" অংশটি অত্যন্ত গুরুত্বপূর্ণ। এটি ছাড়া, একটি ব্রাঞ্চ বা শাখার সিদ্ধান্ত অন্য শাখায় মিশে যাবে এবং পুরো সার্চিং প্রক্রিয়াটিকে নষ্ট করে দেবে।

এন-কুইন্স (N-Queens) — একটি ক্লাসিক উদাহরণ

একটি n×n সাইজের দাবার বোর্ডে n সংখ্যক রানী এমনভাবে স্থাপন করুন যাতে কোনো দুজন রানী একে অপরকে আক্রমণ করতে না পারে। এর চমৎকার কৌশলটি হলো: রানীগুলোকে সারি অনুযায়ী (row by row) স্থাপন করুন। r সারিতে, প্রতিটি কলাম c চেষ্টা করুন। যদি আগে থেকে থাকা কোনো রানী c কলাম, বাঁদিকের ডায়াগোনাল বা কর্ণ, অথবা ডানদিকের ডায়াগোনাল বা কর্ণ শেয়ার না করে থাকে — তবে সেখানে রানীকে বসান এবং r+1 সারির জন্য আবার রিকার্স (recurse) করুন। আর এরপর যখন আপনি ফিরে আসবেন (return), তখন আপনি সেই রানীটিকে সরিয়ে ফেলবেন এবং c+1 কলামের জন্য চেষ্টা করবেন।

n=8 এর ক্ষেত্রে প্রায় ১৬ মিলিয়ন (\(8^8\)) সাধারণ কম্বিনেশন বা সংমিশ্রণ রয়েছে, কিন্তু প্রুনিং (pruning)-এর মাধ্যমে অ্যালগরিদমটি শুধুমাত্র প্রায় ১৫,০০০টি নোড ভিজিট করে — যা ১০০০ গুণ দ্রুতগতি (1000× speedup) সম্পন্ন।

সুডোকু (Sudoku)

প্রতিটি ফাঁকা ঘরের জন্য, ১-৯ পর্যন্ত ডিজিট বা সংখ্যা বসানোর চেষ্টা করুন। একই সারি, কলাম বা ৩×৩ বক্সে ইতিমধ্যে রয়েছে এমন যেকোনো সংখ্যা এড়িয়ে যান। যদি কোনো সংখ্যা সঠিকভাবে মিলে যায়, তবে সেটিকে পূরণ করুন এবং পরবর্তী ফাঁকা ঘরটির জন্য রিকার্স করুন। কিন্তু যদি কোনো সংখ্যাই না মেলে, তবে ফলস (false) রিটার্ন করুন এবং কলারকে (caller) ব্যাকট্র্যাক করার সুযোগ দিন।

এর সাথে কনস্ট্রেইন্ট প্রোপাগেশন (constraint propagation) যুক্ত করুন — একটি ডিজিট বসানোর পর, তৎক্ষণাৎ সেটিকে অন্য সমস্ত পিয়ার সেল (peer cell) বা সংলগ্ন ঘরগুলোর সম্ভাব্য তালিকা থেকে সরিয়ে ফেলুন — এবং এর ফলে দেখবেন বেশিরভাগ সুডোকু পাজল দশটারও কম মোট ব্যাকট্র্যাক ব্যবহার করে সমাধান করা যায়।

বিন্যাস (Permutations) এবং সাবসেট (Subsets)

ব্যাকট্র্যাকিং খুব স্বাভাবিকভাবেই সমস্ত পারমুটেশন বা বিন্যাস এবং সমস্ত সাবসেট তৈরি করে (প্রতিটি পজিশনে, অব্যবহৃত বা আনইউজড প্রতিটি এলিমেন্ট চেষ্টা করুন, সেটিকে ব্যবহৃত হিসেবে চিহ্নিত করুন, রিকার্স করুন, আবার অব্যবহৃত চিহ্নিত করুন) এবং সমস্ত সাবসেট তৈরি করে (প্রতিটি এলিমেন্টে, হয় যুক্ত করুন অথবা বাদ দিন এরকম ব্রাঞ্চ তৈরি করুন)। "চলমান যোগফল ইতিমধ্যেই টার্গেট বা লক্ষ্যমাত্রা অতিক্রম করেছে" — এরকম প্রুনিং শর্তগুলো পুরো ব্রাঞ্চকে শুরুতেই বাতিল বা বাদ দিয়ে দিতে সাহায্য করে।

Click chart to zoom
বাছাই করুন → অন্বেষণ করুন → আগের অবস্থায় ফিরুন (Choose → Explore → Undo) হার্টবিট যা প্রতিটি ব্যাকট্র্যাকিং অ্যালগরিদমকে চালিত করে
দ্রষ্টব্য: ব্যাকট্র্যাকিং হলো মূলত ডেপথ-ফার্স্ট সার্চ (depth-first search) যা আপনি চলমান অবস্থায় একটি ডিসিশন ট্রির (decision tree) ওপর তৈরি করেন। 'পূর্বাবস্থায় ফেরা' বা 'আনডু (undo)' এর মাধ্যমেই আপনি যেকোনো ডেটাকে কপি না করেই একই মিউটেবল (mutable) স্টেট বা অবস্থা সব ব্রাঞ্চে বা শাখায় পুনরায় ব্যবহার করতে পারেন।

এন-কুইন্স (N-Queens) — সকল সমাধান

def solve_n_queens(n):
    solutions = []
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    board = [-1] * n


    def backtrack(row):
        if row == n:
            solutions.append(board[:])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            # Choose
            board[row] = col
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            # Explore
            backtrack(row + 1)
            # Undo
            cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)


    backtrack(0)
    return solutions


sols = solve_n_queens(8)
print(f"{len(sols)} solutions for 8-Queens")
print("First solution (column per row):", sols[0])
Output
92 solutions for 8-Queens
First solution (column per row): [0, 4, 7, 5, 2, 6, 1, 3]

Complexity

🌳 ওয়ার্স্ট কেস বা সবচেয়ে খারাপ পরিস্থিতি (কোনো প্রুনিং নেই)
b = ব্রাঞ্চিং ফ্যাক্টর (branching factor), d = গভীরতা বা ডেপথ (depth); N-Queens এর জন্য: প্রুনিং ছাড়া সর্বোচ্চ n^n পর্যন্ত হতে পারে
প্রতিটি কম্বিনেশন অন্বেষণ করা হয় \(O(b^d)\)
✂️ কনস্ট্রেইন্ট প্রুনিং সহ (With constraint pruning)
8-Queens: প্রুনিং ছাড়া ১৬ মিলিয়ন ভিজিটের বদলে মাত্র ~১৫,০০০ নোড ভিজিট করা হয়েছে — ১০০০ গুণ দ্রুতগতিসম্পন্ন (1000x faster)
প্রথম শর্ত ভঙ্গের পরেই শাখাটিকে বাতিল করা হয় সমস্যা অনুযায়ী ভিন্ন হয় (Problem-specific)
🔮 কনস্ট্রেইন্ট প্রোপাগেশন সহ (With constraint propagation)
লুকঅ্যাহেড (Lookahead) বৃথা রিকার্সন কল করার আগেই ফাঁকা-ক্যান্ডিডেট সেলগুলো শনাক্ত করে বাতিল করে
রিকার্সন করার আগেই ডেড এন্ড বা অন্ধগলি শনাক্ত করা হয় বেশিরভাগ সুডোকুর জন্য প্রায় তাৎক্ষণিক
📚 স্ট্যাক স্পেস (Stack space)
সম্পূর্ণ সার্চ ট্রি মেমরিতে রাখা হয় না — শুধুমাত্র বর্তমান পাথ বা পথটিই মেমরিতে রাখা হয়
প্রতি লেভেলে একটি ফ্রেম \(O(d)\)

ছোট কুইজ

ব্যাকট্র্যাকিং (backtracking) এবং সাধারণ ব্রুট-ফোর্স সার্চের (brute-force search) মধ্যে মূল পার্থক্য কী?

পড়া চালিয়ে যান

ব্রাঞ্চ অ্যান্ড বাউন্ড (Branch & Bound)
ভবিষ্যত দেখার ক্ষমতাসহ ব্যাকট্র্যাকিং (Backtracking) — যে শাখাগুলো বা ব্রাঞ্চ কোনোভাবেই জিততে পারবে না, সেগুলোকে কেটে ছেঁটে ফেলুন (prune)
→
ডিপি প্যাটার্ন (DP Pattern)
একই পাজলের (puzzle) টুকরো বা সমস্যার সমাধান কখনোই দু'বার করবেন না — বরং সেটিকে লিখে রাখুন এবং দরকার হলে পরের বার সেখান থেকেই দেখে নিন
→