C++-এ স্লাইডিং পাজল (Sliding Puzzle) সমাধান

ধরুন আমাদের একটি ২x৩ বোর্ড আছে যেখানে ১ থেকে ৫ নম্বরের ৫টি টাইল এবং একটি খালি স্থান (০ দিർഘ উপস্থাপিত) রয়েছে। একটি মুভ বলতে ০ এবং তার সন্নিহিত কোনো সংখ্যা (উপর, নিচ, বাম, ডান) এর মধ্যে সোয়াপ বোঝায়। পাজলটি সমাধান হয়ে যাবে যখন বোর্ডটি [[1,2,3],[4,5,0]] এই অবস্থানে আসবে।

আমাদের দেওয়া বোর্ড থেকে সমাধান অবস্থায় যেতে কমপক্ষে কতটি মুভ দরকার তা বের করতে হবে। অসম্ভব হলে -১ রিটার্ন করুন।

উদাহরণ

ইনপুট: [[1,2,3],[0,4,5]] → আউটপুট: 2

ব্যাখ্যা: প্রথমে [0,4] সোয়াপ, তারপর [0,5] সোয়াপ।

সমাধানের ধাপসমূহ

BFS (Breadth-First Search) ব্যবহার করুন কারণ এটি সবচেয়ে ছোট পাথ বের করে।
প্রতিটি স্টেটকে একটি নোড হিসেবে বিবেচনা করুন।
ভিজিটেড স্টেটগুলো সেটে রাখুন যাতে পুনরাবৃত্তি 나 না।
লেভেল বাই লেভেল এক্সপ্লোর করুন যতক্ষণ না সমাধান পাওয়া যায়।

প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

class Solution {
public:
    bool ok(vector<vector<int>>& b) {
        return b[0][0] == 1 && b[0][1] == 2 && b[0][2] == 3 && 
               b[1][0] == 4 && b[1][1] == 5;
    }
    
    int slidingPuzzle(vector<vector<int>>& board) {
        if (ok(board)) return 0;
        
        queue<vector<vector<int>>> q;
        q.push(board);
        set<vector<vector<int>>> visited;
        visited.insert(board);
        
        for (int lvl = 1; !q.empty(); lvl++) {
            int sz = q.size();
            while (sz--) {
                auto node = q.front();
                q.pop();
                
                int x = -1, y = -1;
                for (int i = 0; i < board.size(); i++) {
                    for (int j = 0; j < board[0].size(); j++) {
                        if (node[i][j] == 0) {
                            x = i; y = j;
                            break;
                        }
                    }
                }
                
                for (int k = 0; k < 4; k++) {
                    int nx = x + dir[k][0];
                    int ny = y + dir[k][1];
                    if (nx < 0 || ny < 0 || nx >= board.size() || ny >= board[0].size())
                        continue;
                    
                    swap(node[x][y], node[nx][ny]);
                    if (visited.count(node)) {
                        swap(node[x][y], node[nx][ny]);
                        continue;
                    }
                    visited.insert(node);
                    if (ok(node)) return lvl;
                    q.push(node);
                    swap(node[x][y], node[nx][ny]);
                }
            }
        }
        return -1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,2,3},{0,4,5}};
    cout << (ob.slidingPuzzle(v));
}

ইনপুট

{{1,2,3},{0,4,5}}