Backtracking

একটা choice নিয়ে দেখুন কোথায় যায়, তারপর সেটা undo করে পরের choice try করুন।

মূল ধারণা

চক পেনসিল হাতে একটা maze-এর ভেতর দিয়ে হাঁটার কথা ভাবুন: প্রতিটা মোড়ে একটা পথ বেছে নিয়ে এগিয়ে যান। বন্ধ রাস্তায় পৌঁছালে শেষ মোড় পর্যন্ত ফিরে আসুন (backtrack), চকের দাগ মুছে অন্য পথে যান। Backtracking সব সম্ভাবনা নিয়মমাফিক try করে, কিন্তু যে branch দিয়ে কাজ হবে না সেটা বুঝতে পারলেই ছেড়ে দেয়।

Pattern সবসময় একই: choose → explore (recursion) → un-choose। Subsets: প্রতিটা item-এর জন্য ঠিক করুন “নেব” নাকি “বাদ দেব”। N-Queens: প্রতি row-তে একটা queen বসান; কোনো ঘর attacked হলে সেটা বাদ দিন; কোনো row-তে একটাও safe ঘর না থাকলে আগের row-তে ফিরে গিয়ে আগের queen সরান।

Run করে দেখুন

নিজে চেষ্টা করুন

সাধারণ ভুল

Complexity

Subsets: O(2n) সংখ্যক result, তাই সেগুলো বানাতে O(n·2n) time complexity। N-Queens: polynomial-এর চেয়ে খারাপ, কিন্তু pruning (attacked ঘর আগেই বাদ দেওয়া) করলে সব placement try করার তুলনায় search অনেক কমে যায়। Space complexity: O(n) recursion depth আর জমানো result।