Backtracking হল একটি প্রোগ্রামিং কৌশল যা সমস্যা সমাধান করার জন্য বিভিন্ন সম্ভাব্য সমাধানগুলির মধ্যে পছন্দ করে এবং ভুল পথে চললে সেগুলি প্রত্যাহার (backtrack) করে পুনরায় সঠিক পথ অনুসরণ করার চেষ্টা করে। এটি বেশিরভাগ ক্ষেত্রেই combinatorial problems বা constraint satisfaction problems সমাধান করার জন্য ব্যবহৃত হয়।
এই গাইডে, আমরা Backtracking ব্যবহার করে দুটি ক্লাসিক্যাল সমস্যা সমাধান করব: N-Queens Problem এবং Maze Solving।
1. N-Queens Problem
N-Queens Problem হল এমন একটি সমস্যা যেখানে আমাদের N সংখ্যক কুইন (Queen) কে একটি NxN চেস বোর্ডে এমনভাবে স্থাপন করতে হয় যাতে কোনও দুটি কুইন একে অপরকে আক্রমণ না করে। কুইন শুধুমাত্র একে অপরকে horizontally, vertically, বা diagonally আক্রমণ করতে পারে।
1.1. Solution Using Backtracking
Backtracking ব্যবহার করে N-Queens সমস্যার সমাধান করা যায়। প্রতিটি কুইন স্থাপন করার পর, আমরা চেক করি যে সেটি বৈধ কিনা, যদি না হয় তবে পূর্ববর্তী কুইনকে সরিয়ে আবার চেষ্টা করি।
public class NQueens {
private int N; // Size of the board
private int[] board; // Array to store positions of queens
public NQueens(int N) {
this.N = N;
this.board = new int[N];
}
// Check if a queen can be placed at board[row][col]
private boolean isSafe(int row, int col) {
for (int i = 0; i < row; i++) {
if (board[i] == col || // Same column
board[i] - i == col - row || // Same diagonal
board[i] + i == col + row) { // Same anti-diagonal
return false;
}
}
return true;
}
// Solve the N-Queens problem using backtracking
public boolean solveNQueens(int row) {
if (row == N) {
printSolution();
return true;
}
for (int col = 0; col < N; col++) {
if (isSafe(row, col)) {
board[row] = col;
if (solveNQueens(row + 1)) {
return true;
}
}
}
return false; // Backtrack
}
// Print the solution (board configuration)
private void printSolution() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (board[i] == j) {
System.out.print("Q "); // Queen position
} else {
System.out.print(". "); // Empty space
}
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
NQueens queens = new NQueens(8); // Example for 8-Queens problem
if (!queens.solveNQueens(0)) {
System.out.println("No solution exists");
}
}
}
1.2. Explanation:
- isSafe: এই ফাংশনটি চেক করে যে একটি কুইন দেওয়া রো এবং কলামে নিরাপদভাবে স্থাপন করা যায় কিনা, যেখানে আগের কুইনগুলি আক্রমণ করতে পারে না।
- solveNQueens: এটি একটি পুনরাবৃত্তি (recursive) ফাংশন যা কুইনগুলি স্থাপন করার চেষ্টা করে। যদি একটি কুইন নিরাপদ হয় তবে এটি পরবর্তী রোতে কুইন স্থাপন করতে চলে যায়, এবং একবার সমস্ত কুইন স্থাপন হয়ে গেলে এটি সমাধান মুদ্রণ করে।
- printSolution: এটি চেস বোর্ডের উপস্থাপনা প্রিন্ট করে, যেখানে কুইনগুলি উপস্থাপন করা হয়েছে।
এটি N-Queens সমস্যার সমাধান করে এবং 8-Queens সমস্যা উদাহরণ হিসেবে নেয়।
2. Maze Solving Using Backtracking
Maze solving হল একটি সাধারণ সমস্যা যেখানে আমাদের একটি মেজ (maze) থেকে বের হওয়া পথ খুঁজে বের করতে হয়। আমাদের একটি start এবং end পয়েন্ট দেওয়া থাকে, এবং backtracking ব্যবহার করে আমরা মেজের ভিতর দিয়ে একাধিক পথ অনুসরণ করি, যখন একটি পথ ভুল হয় তখন আমরা তা ব্যাকট্র্যাক করে অন্য পথে চলে যাই।
2.1. Maze Solving Algorithm
মেজের ভিতর থেকে একটি পথ খুঁজতে আমরা right, down, left, up দিকগুলো পরীক্ষা করি। প্রতিটি সেল ভিজিট করার পর, তা পুনরায় ভিজিট না করার জন্য marked বা visited করা হয়। যদি কোন দিক থেকে সরাসরি শেষ গন্তব্যে পৌঁছানো যায় তবে তা সঠিক পথ হবে।
public class MazeSolver {
private int N; // Size of the maze
private int[][] maze;
private int[][] solution;
// Directions for moving in the maze
private int[] rowDir = { 1, 0, -1, 0 };
private int[] colDir = { 0, 1, 0, -1 };
public MazeSolver(int[][] maze) {
this.maze = maze;
this.N = maze.length;
this.solution = new int[N][N];
}
// Check if the current cell is valid and safe to visit
private boolean isSafe(int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}
// Solve the maze using backtracking
public boolean solveMaze(int x, int y) {
// If we have reached the bottom-right corner, return true
if (x == N - 1 && y == N - 1) {
solution[x][y] = 1;
return true;
}
if (isSafe(x, y)) {
solution[x][y] = 1; // Mark the current cell as part of the solution
// Move right
if (solveMaze(x + 1, y)) {
return true;
}
// Move down
if (solveMaze(x, y + 1)) {
return true;
}
// Move left
if (solveMaze(x - 1, y)) {
return true;
}
// Move up
if (solveMaze(x, y - 1)) {
return true;
}
// Backtrack if none of the moves worked
solution[x][y] = 0;
return false;
}
return false;
}
// Print the solution path
public void printSolution() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(solution[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// A simple maze where 1 represents open paths and 0 represents walls
int[][] maze = {
{ 1, 0, 0, 0, 0 },
{ 1, 1, 0, 1, 0 },
{ 0, 1, 0, 0, 1 },
{ 0, 1, 1, 1, 1 },
{ 0, 0, 0, 0, 1 }
};
MazeSolver solver = new MazeSolver(maze);
if (solver.solveMaze(0, 0)) {
System.out.println("Solution path:");
solver.printSolution();
} else {
System.out.println("No path exists.");
}
}
}
2.2. Explanation:
- isSafe: এই ফাংশনটি চেক করে যে বর্তমান কোঅর্ডিনেটটি মেজের ভিতর অবস্থিত এবং সেটি চলাচলের জন্য অনুমোদিত (যে কোঅর্ডিনেটে
1রয়েছে)। - solveMaze: এটি মূল ফাংশন যা মেজের মধ্যে হাঁটা শুরু করে। এটি right, down, left, up দিকগুলো পরীক্ষা করে এবং যদি কোনো একটি দিক থেকে গন্তব্যে পৌঁছানো যায় তবে সেই পথ অনুসরণ করে।
- Backtracking: যখন একটি পথ ভুল হয়, তখন এটি ব্যাকট্র্যাক করে এবং অন্যান্য পথ অনুসন্ধান করে।
- printSolution: এটি সলিউশনকে একটি ম্যাট্রিক্স আকারে প্রদর্শন করে যেখানে
1প্রতিটি চলা সেলের প্রতিনিধিত্ব করে।
সারাংশ
Backtracking এমন একটি প্রোগ্রামিং কৌশল যা সমস্যাগুলির সম্ভাব্য সমাধানগুলির মধ্যে যাচাই করে সঠিক সমাধান খুঁজে পেতে সাহায্য করে। N-Queens এবং Maze Solving এর মতো সমস্যাগুলি ভালভাবে সমাধান করা যায় Backtracking এর সাহায্যে। N-Queens সমস্যা যেখানে বিভিন্ন কুইন একে অপরকে আক্রমণ না করে একে অপরকে স্থাপন করতে হয় এবং Maze Solving সমস্যায় যেখানে মেজের ভিতর থেকে একটি পথ বের করার চেষ্টা করা হয়, উভয় ক্ষেত্রেই Backtracking অত্যন্ত কার্যকরী সমাধান দেয়।
Read more
