ব্যাকট্র্যাকিং (Backtracking) হল একটি অ্যালগরিদমিক কৌশল, যেখানে সমাধানের সম্ভাব্য সকল পথ পরীক্ষা করে এবং প্রয়োজন হলে পূর্ববর্তী পদক্ষেপে ফিরে এসে নতুন পথে সমাধান খুঁজে বের করা হয়। এটি একটি রিকার্সিভ পদ্ধতি, যা সমস্যার সমাধানে সঠিক পথে পৌঁছাতে সাহায্য করে।
ব্যাকট্র্যাকিং এর ধারণা
ব্যাকট্র্যাকিং মূলত একটি ট্রায়াল অ্যান্ড এরর (Trial and Error) ভিত্তিক পদ্ধতি, যেখানে সম্ভাব্য সকল সমাধান পর্যায়ক্রমে পরীক্ষা করা হয়। যেই পথে বাধা বা শর্ত পূরণ হয় না, সেই পথ পরিহার করা হয় এবং পূর্ববর্তী ধাপে ফিরে আসা হয়, তারপর নতুন পথে অনুসন্ধান শুরু হয়।
এটি প্রধানত তখন ব্যবহার করা হয় যখন কোনো সমস্যা একাধিক সম্ভাব্য সমাধানের মধ্যে নির্দিষ্ট সমাধান খুঁজে বের করতে হয়। ব্যাকট্র্যাকিং পদ্ধতির মাধ্যমে সমাধানটি ধাপে ধাপে নির্মিত হয় এবং কোন পদক্ষেপে যদি শর্ত পূরণ না হয়, তখন আগের ধাপে ফিরে এসে নতুন সমাধান খোঁজা হয়।
ব্যাকট্র্যাকিং কৌশল
ব্যাকট্র্যাকিং সমাধান নির্ণয়ের জন্য সাধারণত নিম্নলিখিত স্টেপগুলো অনুসরণ করা হয়:
- সম্ভাব্য পদক্ষেপগুলো পরীক্ষা করা: প্রতিটি ধাপে যেসব পদক্ষেপ সম্ভব, সেগুলোর মধ্যে একটি নির্বাচন করা হয়।
- শর্ত পরীক্ষা করা: নির্বাচিত পদক্ষেপটি সমস্যার শর্ত পূরণ করছে কিনা তা পরীক্ষা করা হয়। যদি পূরণ না করে, তাহলে সেই পথ বাদ দিয়ে অন্য পথ অনুসন্ধান করা হয়।
- রিকার্সন ও ব্যাকট্র্যাকিং: শর্ত পূরণ হলে রিকার্সিভ কলের মাধ্যমে পরবর্তী ধাপে এগিয়ে যাওয়া হয়। যদি কোনো ধাপে সমাধান না পাওয়া যায়, তবে রিকার্সন ব্যাকট্র্যাকিং করে আগের ধাপে ফিরে আসে।
- সম্পূর্ণ সমাধান পাওয়া: উপযুক্ত সমাধান পাওয়া গেলে রিকার্সন বন্ধ হয় এবং সমাধানটি রিটার্ন করা হয়।
ব্যাকট্র্যাকিং এর উদাহরণ
১. এন-কুইন সমস্যা (N-Queens Problem)
N-Queens সমস্যায় একটি N×NN×N চেস বোর্ডে NNটি কুইন এমনভাবে স্থাপন করতে হয় যাতে দুটি কুইন একই সারি, কলাম, বা ডায়াগোনালে না থাকে। ব্যাকট্র্যাকিং পদ্ধতিতে একাধিক সম্ভাব্য সমাধান পরীক্ষা করে নির্দিষ্ট সমাধান পাওয়া সম্ভব।
উদাহরণ কোড:
def solve_n_queens(board, col):
if col >= len(board):
return True
for i in range(len(board)):
if is_safe(board, i, col):
board[i][col] = 1
if solve_n_queens(board, col + 1):
return True
board[i][col] = 0 # Backtrack
return False
২. নাইটস ট্যুর (Knight’s Tour Problem)
নাইটস ট্যুর সমস্যায় চেস বোর্ডে একটি নাইটকে এমনভাবে সরানো হয় যাতে প্রতিটি ঘরে কেবল একবারই গিয়ে সব ঘর ভ্রমণ করে। ব্যাকট্র্যাকিং এর মাধ্যমে সম্ভাব্য প্রতিটি ঘরে গিয়ে নাইটের গতিবিধি পরীক্ষা করা হয় এবং শর্ত পূরণ না হলে আগের ঘরে ফিরে আসে।
৩. সাবসেট সমস্যা (Subset Sum Problem)
এই সমস্যায় একটি সেট থেকে এমন উপাদানগুলো নির্বাচন করতে হয় যার সমষ্টি নির্দিষ্ট মানের সমান। ব্যাকট্র্যাকিং পদ্ধতিতে সম্ভাব্য সমস্ত উপসেট পরীক্ষা করে সমাধান পাওয়া সম্ভব।
৪. সুডোকু সলভার (Sudoku Solver)
সুডোকু সমস্যা সমাধানে ব্যাকট্র্যাকিং পদ্ধতি অত্যন্ত কার্যকর। এখানে প্রতিটি ঘরে সম্ভাব্য সংখ্যা স্থাপন করা হয় এবং প্রতিটি পদক্ষেপে শর্ত পূরণ করা হচ্ছে কিনা পরীক্ষা করা হয়। যদি না হয়, তাহলে ব্যাকট্র্যাক করে অন্য সংখ্যা স্থাপন করা হয়।
ব্যাকট্র্যাকিং এর সুবিধা
- সম্ভাব্য সব সমাধান খুঁজে বের করা যায়: ব্যাকট্র্যাকিং এর মাধ্যমে সকল সমাধানের মধ্যে নির্দিষ্ট সমাধান খুঁজে বের করা যায়।
- অপ্টিমাইজেশন সমস্যায় কার্যকর: বিশেষ করে এন-কুইন, সাবসেট, গ্রাফ, এবং কম্বিনেটোরিয়াল সমস্যা সমাধানে কার্যকর।
- রিকার্সন এবং মেমরি ব্যবস্থাপনা সহজতর করা: সহজে রিকার্সন ব্যবহার করে সমাধান নির্মাণ করা যায়।
ব্যাকট্র্যাকিং এর সীমাবদ্ধতা
- সময়ের জটিলতা বেশি: বড় সমস্যায় অনেক সম্ভাব্য সমাধান থাকলে ব্যাকট্র্যাকিংয়ের সময় জটিলতা দ্রুত বেড়ে যেতে পারে।
- অপ্টিমালিটি গ্যারান্টিযুক্ত নয়: ব্যাকট্র্যাকিং সবসময়ই গ্লোবাল অপটিমাল সমাধান গ্যারান্টি দিতে পারে না।
সারসংক্ষেপ
ব্যাকট্র্যাকিং এমন সমস্যাগুলির জন্য কার্যকর যেখানে একাধিক সম্ভাব্য সমাধান থাকতে পারে এবং প্রতিটি সমাধান পরীক্ষা করা প্রয়োজন। এটি ছোট ও মাঝারি সমস্যার জন্য খুব কার্যকর হলেও বড় সমস্যার জন্য ডাইনামিক প্রোগ্রামিং বা গ্রিডি মেথডের মতো অ্যালগরিদম কার্যকর হতে পারে।
