বহু-স্টেপ বা জাম্প অনুমোদিত র‍্যাট ইন মেজ সমস্যা

র‍্যাট ইন মেজ সমস্যা ব্যাকট্র্যাকিং-এর একটি বিখ্যাত সমস্যা। এখানে আমরা একটু ভিন্নতা সহ সেই সমস্যাটি দেখব। ধরা যাক একটি NxN মেজ M দেওয়া আছে। শুরুতে উপরের বাম কোণ M[0, 0]-এ র‍্যাট থাকে, এবং গন্তব্য নিচের ডান কোণ M[N−1, N−1]। লক্ষ্য হলো র‍্যাট কে শুরু থেকে শেষ পর্যন্ত পথ খুঁজে বের করা। এখানে র‍্যাট জাম্প দিতে পারে (ভিন্নতা)। কিছু শর্ত রয়েছে:

র‍্যাট শুধু ডানে বা নিচে যেতে পারে।
মেজে ০ থাকলে সেল ব্লক করা।
নন-জিরো সেল বৈধ পথ নির্দেশ করে।
সেলের ভিতরের সংখ্যা ওই সেল থেকে র‍্যাট কতটুকু সর্বোচ্চ জাম্প দিতে পারবে তা বলে।

অ্যালগরিদম

ratInMaze

begin    if destination is reached, then       print the solution matrix    else       1. Place the current cell inside the solution matrix as 1       2. Move forward or jump (check max jump value) and recursively check if move leads to solution or not.       3. If the move taken from the step 2 is not correct, then move down, and check it leads to the solution or not       4. If none of the solutions in step 2 and 3 are correct, then make the current cell 0.    end if end

উদাহরণ

#include <iostream> #define N 4 using namespace std; void dispSolution(int sol[N][N]) {    for (int i = 0; i < N; i++) {       for (int j = 0; j < N; j++)          cout << sol[i][j] << " ";       cout << endl;    } } bool isSafe(int maze[N][N], int x, int y) { //check whether x,y is valid or not    // when (x, y) is outside of the maze, then return false    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0)       return true;    return false; } bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) {    if (x == N - 1 && y == N - 1) { //if destination is found, return true       sol[x][y] = 1;       return true;    }    if (isSafe(maze, x, y)) {       sol[x][y] = 1; //mark 1 into solution matrix       for (int i = 1; i <= maze[x][y] && i < N; i++) {          if (ratMazeSolve(maze, x + i, y, sol)) //move right             return true;          if (ratMazeSolve(maze, x, y + i, sol)) //move down             return true;       }       sol[x][y] = 0; //if the solution is not valid, then make it 0       return false;    }    return false; } bool solveMaze(int maze[N][N]) {    int sol[N][N] = { { 0, 0, 0, 0 },       { 0, 0, 0, 0 },       { 0, 0, 0, 0 },       { 0, 0, 0, 0 }    };    if (!ratMazeSolve(maze, 0, 0, sol)) {       cout << "Solution doesn't exist";       return false;    }    dispSolution(sol);    return true; } main() {    int maze[N][N] = { { 2, 1, 0, 0 },       { 3, 0, 0, 1 },       { 0, 1, 0, 1 },       { 0, 0, 0, 1 }    };    solveMaze(maze); }

আউটপুট

1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1