18. Backtracking Introduction
Backtracking হলো একটি অ্যালগরিদমিক পদ্ধতি যা কোনো সমস্যার সব সম্ভাব্য সমাধান খুঁজে বের করার চেষ্টা করে। এটি মূলত একটি ব্রুট-ফোর্স (Brute-force) এপ্রোচ, কিন্তু এটি যখনই বুঝতে পারে যে বর্তমান পথটি সঠিক সমাধানের দিকে যাবে না, তখনই সেটি ফিরে আসে (Backtrack) এবং অন্য পথে চেষ্টা করে।
1. ব্যাকট্র্যাকিং এপ্রোচ (Backtracking Approach)
ব্যাকট্র্যাকিং অনেকটা একটি গোলকধাঁধায় (Maze) হাঁটার মতো। যদি আপনি একটি রাস্তায় গিয়ে দেখেন সেটি বন্ধ, তবে আপনি আগের মোড়ে ফিরে আসেন এবং অন্য আরেকটি রাস্তা বেছে নেন।
🛠 মূল ধাপসমূহ (Core Steps)
- Choose: একটি সম্ভাব্য অপশন বেছে নিন।
- Explore: সেই অপশনটি ব্যবহার করে সামনের দিকে এগিয়ে যান (Recursion)।
- Backtrack: যদি দেখেন এই পথে কোনো সমাধান নেই, তবে আগের অবস্থায় ফিরে যান এবং বাছাই করা অপশনটি বাদ দিয়ে নতুন কিছু চেষ্টা করুন।
2. স্টেট স্পেস ট্রি (State Space Tree)
ব্যাকট্র্যাকিংয়ের সব সম্ভাব্য সিদ্ধান্ত এবং তাদের ফলাফলকে একটি ট্রির মাধ্যমে প্রকাশ করা হয়, যাকে State Space Tree বা Decision Tree বলা হয়।
Root (Start)
/ \
Path 1 Path 2
/ \ / \
S F F S
(S=Success, F=Failure)3. প্রুনিং (Pruning)
যদি আমরা আগেই বুঝতে পারি যে কোনো একটি নির্দিষ্ট সাব-ট্রি (Sub-tree) থেকে সঠিক সমাধান পাওয়া সম্ভব নয়, তবে আমরা সেই পথে আর চেক করি না। এই সময় বাঁচানোর পদ্ধতিকে বলা হয় Pruning। এটি ব্যাকট্র্যাকিংয়ের গতি অনেক বাড়িয়ে দেয়।
4. এন-কুইনস প্রবলেম (N-Queens Problem - Basic)
একটি $N \times N$ চেসবোর্ডে N সংখ্যক রানীকে এমনভাবে বসাতে হবে যাতে কেউ কাউকে আক্রমণ করতে না পারে।
🛠 কর্মপদ্ধতি (Step-by-Step Logic)
- প্রথম রৌ (Row) থেকে শুরু করুন।
- প্রতিটি কলামে রানী বসানোর চেষ্টা করুন।
- চেক করুন বর্তমান পজিশনটি নিরাপদ (Safe) কি না (একই কলাম, রো বা ডায়াগোনালে অন্য রানী নেই)।
- যদি নিরাপদ হয়, রানী বসান এবং পরের রো-তে যান।
- যদি কোনো কলামই নিরাপদ না হয়, তবে আগের রো-তে ফিরে যান এবং পূর্ববর্তী রানীর পজিশন পরিবর্তন করুন (Backtrack)।
Implementation
// Java N-Queens
public class NQueens {
public void solveNQueens(int n) {
char[][] board = new char[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = '.';
solve(0, board, n);
}
private void solve(int col, char[][] board, int n) {
if (col == n) {
printBoard(board, n);
return;
}
for (int row = 0; row < n; row++) {
if (isSafe(row, col, board, n)) {
board[row][col] = 'Q';
solve(col + 1, board, n);
board[row][col] = '.'; // Backtrack
}
}
}
private boolean isSafe(int row, int col, char[][] board, int n) {
for (int i = 0; i < col; i++)
if (board[row][i] == 'Q') return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 'Q') return false;
for (int i = row, j = col; i < n && j >= 0; i++, j--)
if (board[i][j] == 'Q') return false;
return true;
}
private void printBoard(char[][] board, int n) {
for (int i = 0; i < n; i++) {
System.out.println(new String(board[i]));
}
System.out.println();
}
}# Python N-Queens
def solve_n_queens(n):
board = [['.' for _ in range(n)] for _ in range(n)]
def is_safe(row, col):
for i in range(col):
if board[row][i] == 'Q': return False
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 'Q': return False
for i, j in zip(range(row, n, 1), range(col, -1, -1)):
if board[i][j] == 'Q': return False
return True
def solve(col):
if col == n:
for row in board:
print("".join(row))
print()
return
for row in range(n):
if is_safe(row, col):
board[row][col] = 'Q'
solve(col + 1)
board[row][col] = '.' # Backtrack
solve(0)5. র্যাট ইন আ মেজ (Rat in a Maze)
একটি গ্রিডে একটি ইঁদুরকে (0,0) থেকে শুরু করে ডেস্টিনেশনে পৌঁছাতে হবে। গ্রিডে কিছু ব্লক বা বাধা থাকতে পারে।
🛠 কর্মপদ্ধতি (Step-by-Step Logic)
- বর্তমান ঘরটি নিরাপদ কি না চেক করুন (বাউন্ডারির ভেতরে এবং কোনো ব্লক নেই)।
- যদি নিরাপদ হয়, ঘরটিকে মার্ক করুন এবং চারদিকে (ডানে, বামে, উপরে, নিচে) চেক করুন।
- যদি সমাধান না পাওয়া যায়, তবে ঘরটিকে আন-মার্ক (Unmark) করুন এবং ফিরে আসুন।
Implementation
// Java Rat in a Maze
public class RatInMaze {
public boolean solveMaze(int[][] maze, int n) {
int[][] sol = new int[n][n];
if (!solve(maze, 0, 0, sol, n)) return false;
printSolution(sol, n);
return true;
}
private boolean solve(int[][] maze, int x, int y, int[][] sol, int n) {
if (x == n - 1 && y == n - 1 && maze[x][y] == 1) {
sol[x][y] = 1;
return true;
}
if (isSafe(maze, x, y, n)) {
sol[x][y] = 1;
if (solve(maze, x + 1, y, sol, n)) return true;
if (solve(maze, x, y + 1, sol, n)) return true;
sol[x][y] = 0; // Backtrack
return false;
}
return false;
}
private boolean isSafe(int[][] maze, int x, int y, int n) {
return (x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1);
}
private void printSolution(int[][] sol, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) System.out.print(" " + sol[i][j] + " ");
System.out.println();
}
}
}# Python Rat in a Maze
def solve_maze(maze, n):
sol = [[0 for _ in range(n)] for _ in range(n)]
def is_safe(x, y):
return 0 <= x < n and 0 <= y < n and maze[x][y] == 1
def solve(x, y):
if x == n - 1 and y == n - 1 and maze[x][y] == 1:
sol[x][y] = 1
return True
if is_safe(x, y):
sol[x][y] = 1
if solve(x + 1, y): return True
if solve(x, y + 1): return True
sol[x][y] = 0 # Backtrack
return False
return False
if solve(0, 0):
for row in sol:
print(row)
else:
print("No solution")6. সাবসেট জেনারেশন (Subset Generation)
একটি সেটের সব সম্ভাব্য সাবসেট বের করা (যেমন: {1, 2} এর সাবসেট { }, {1}, {2}, {1, 2})।
🛠 কর্মপদ্ধতি (Step-by-Step Logic)
- প্রতিটি এলিমেন্টের জন্য দুটি সিদ্ধান্ত থাকে: হয় এলিমেন্টটি সাবসেটে থাকবে, অথবা থাকবে না।
- একটি ডিসিশন ট্রি তৈরি করুন যেখানে প্রতিটি ধাপে একটি এলিমেন্ট যোগ করা হয় বা বাদ দেওয়া হয়।
Implementation
// Java Subset Generation
import java.util.*;
public class Subsets {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
generate(0, nums, new ArrayList<>(), res);
return res;
}
private void generate(int index, int[] nums, List<Integer> current, List<List<Integer>> res) {
res.add(new ArrayList<>(current));
for (int i = index; i < nums.length; i++) {
current.add(nums[i]);
generate(i + 1, nums, current, res);
current.remove(current.size() - 1); // Backtrack
}
}
}# Python Subset Generation
def subsets(nums):
res = []
def generate(index, current):
res.append(current[:])
for i in range(index, len(nums)):
current.append(nums[i])
generate(i + 1, current)
current.pop() # Backtrack
generate(0, [])
return res📊 কমপ্লেক্সিটি অ্যানালাইসিস (Complexity Analysis)
- Time Complexity: ব্যাকট্র্যাকিং সাধারণত এক্সপোনেনশিয়াল হয়। যেমন, N-Queens-এর জন্য এটি O(n!), এবং সাবসেট জেনারেশনের জন্য O(2ⁿ)।
- Space Complexity: রিকার্সন স্ট্যাকের গভীরতার ওপর নির্ভর করে, সাধারণত O(n)।
IMPORTANT
ব্যাকট্র্যাকিং ব্যবহারের সময় Pruning খুবই গুরুত্বপূর্ণ। সঠিক কন্ডিশন সেট করলে এটি কোডের পারফরম্যান্স অনেকাংশেই উন্নত করতে পারে।
TIP
ব্যাকট্র্যাকিং কোড লেখার সময় সবসময় visited অ্যারে বা স্টেট চেঞ্জ করার পর সেটি পুনরায় আগের অবস্থায় ফিরিয়ে আনার (Undo step) কথা মনে রাখবেন।