ব্যাকট্র্যাকিং (Backtracking) হলো একটি অ্যালগরিদম-ভিত্তিক টেকনিক যা সমস্যা সমাধান করতে ব্যবহৃত হয়। এটি রিকার্সিভ কল ব্যবহার করে ধাপে ধাপে সমাধান তৈরি করে এবং সময়ের সাথে সাথে মান বাড়ায়। এটি সমস্যা সমাধানের জন্য দেওয়া কনস্ট্রেইন্টস (constraints) অনুযায়ী সমাধান দিয়ে না এমন পথগুলো সরিয়ে দেয়।
ব্যাকট্র্যাকিং অ্যালগরিদম কিছু নির্দিষ্ট ধরনের সমস্যার জন্য প্রয়োগ করা হয়,
ডিসিশন প্রব্লেম (Decision problem) - সমস্যার একটি ফিজিবল সমাধান খুঁজে বের করতে।
অপ্টিমাইজেশন প্রব্লেম (Optimisation problem) - প্রয়োগ করা যেতে পারে এমন সেরা সমাধান খুঁজে বের করতে।
এনুমেরেশন প্রব্লেম (Enumeration problem) - সমস্যার সব ফিজিবল সমাধানের সেট খুঁজে বের করতে।
ব্যাকট্র্যাকিং সমস্যায়, অ্যালগরিদমটি সমাধানের तरफ একটি সিকোয়েন্স পথ খুঁজে বের করার চেষ্টা করে যেটিতে কিছু ছোট চেকপয়েন্ট থাকে। যদি কোনো ফিজিবল সমাধান না পাওয়া যায়, তবে সেখান থেকে ব্যাকট্র্যাক (পিছিয়ে যাওয়া) করে।
উদাহরণ,
এখানে,
গ্রিন হলো স্টার্ট পয়েন্ট, ব্লু হলো ইন্টারমিডিয়েট পয়েন্ট, রেড হলো কোনো ফিজিবল সমাধান নেই এমন পয়েন্ট, ডার্ক গ্রিন হলো এন্ড সমাধান।
এখানে, যখন অ্যালগরিদমটি এন্ড পর্যন্ত পৌঁছায় চেক করতে যে সেটি সমাধান কিনা, যদি হয় তবে সমাধান রিটার্ন করে অন্যথায় এক ধাপ পিছিয়ে যেতে হবে পরবর্তী পয়েন্ট খুঁজে সমাধান পাওয়ার জন্য।
অ্যালগরিদম
ধাপ ১ − যদি current_position goal হয়, তবে success রিটার্ন ধাপ ২ − অন্যথায়, ধাপ ৩ − যদি current_position একটি এন্ড পয়েন্ট হয়, তবে failed রিটার্ন। ধাপ ৪ − অন্যথায়, যদি current_position এন্ড পয়েন্ট নয় হয়, তবে এক্সপ্লোর করুন এবং উপরের ধাপগুলো রিপিট করুন।
এই ব্যাকট্র্যাকিং সমস্যা ব্যবহার করে N-Queen Problem সমাধান করা যাক।
N-Queen সমস্যায়, আমাদের একটি NxN চেসবোর্ড দেওয়া থাকে এবং আমাদের বোর্ডে n কুইন রাখতে হবে এমনভাবে যাতে দুটি কুইন একে অপরের ওপর আক্রমণ না করতে পারে। একটি কুইন অন্য কুইনকে আক্রমণ করবে যদি সেটি হরিজেন্টাল, ভার্টিক্যাল বা ডায়াগোনাল পজিশনে থাকে। এখানে আমরা ৪-Queen সমস্যা করব।
এখানে সমাধান হলো −
এখানে, n queen সমস্যার বাইনারি আউটপুট যেখানে ১ oznac কুইন প্লেস করা হয়েছে।
{0 , 1 , 0 , 0}
{0 , 0 , 0 , 1}
{1 , 0 , 0 , 0}
{0 , 0 , 1 , 0}
N Queens সমস্যা সমাধানের জন্য, আমরা এক রোয়ের বিভিন্ন পজিশনে কুইন রাখার চেষ্টা করব। এবং চেক করবো এটি অন্য কুইনদের সাথে ক্ল্যাশ করছে কিনা। যদি বর্তমান পজিশনে যেকোনো দুটি কুইন একে অপরের ওপর আক্রমণ করে, তবে আমরা পিছিয়ে যাব (backtrack) আগের কুইন লোকেশনে এবং তার পজিশন পরিবর্তন করব। আবার কুইন ক্ল্যাশ চেক করব।
অ্যালগরিদম
ধাপ ১ − অ্যারেতে ১ম পজিশন থেকে শুরু করুন।
ধাপ ২ − বোর্ডে কুইন রাখুন এবং চেক করুন। করুন, ধাপ ২.১ − কুইন রাখার পর, পজিশনটি সমাধানের অংশ হিসেবে মার্ক করুন এবং তারপর রিকার্সিভলি চেক করুন এটা সমাধান দিকে নিয়ে যাবে কিনা। ধাপ ২.২ − এখন, যদি কুইন রাখা সমাধান দিকে নিয়ে যেতে না পারে তবে ব্যাকট্র্যাক করুন এবং ধাপ (a)-এ যান এবং কুইনকে অন্য রোতে রাখুন। ধাপ ২.৩ − যদি কুইন রাখা সমাধান দিকে নিয়ে যায় তবে TRUE রিটার্ন। ধাপ ৩ − যদি সব কুইন প্লেস করা হয়ে যায় তবে TRUE রিটার্ন।ধাপ ৪ − যদি সব রো ট্রাই করা হয় এবং কোনো সমাধান না পাওয়া যায়, তবে FALSE রিটার্ন।
এখন, ব্যাকট্র্যাকিং ব্যবহার করে Rat in a Maze সমস্যা সমাধান করা যাক −
Rat in a Maze সমস্যায়, আমাদের একটি NxN মেজ দেওয়া থাকে। মেজের প্রথম পজিশন অর্থাৎ [0][0] থেকে শুরু হবে এবং অ্যারের শেষ পজিশন [n-1][n-1]-এ শেষ হবে। এই পথে কিছু ডেড রোড (dead roads) থাকে যা কোনো সমাধান দিকে নিয়ে যায় না।
এই সমস্যায় ব্যাকট্র্যাকিং ব্যবহার করে আমরা ধাপে ধাপে নিচের দিকে যাবো মেজের ফাইনাল গোল পজিশনে পৌঁছানোর জন্য।
নিচের ২D অ্যারেটি দেখায় সমস্যাটি কেমন দেখায়।
এখানে ড্যাশড লাইনগুলো ট্রাভার্স করা পথ দেখাচ্ছে।
