C++ में स्लाइडिंग पज़ल (Sliding Puzzle) - न्यूनतम चालों में हल करना

समस्या विवरण

हमारे पास एक 2x3 बोर्ड है जिसमें 5 टाइल्स (1 से 5) और एक खाली वर्ग (0) है। एक चाल का अर्थ है 0 और एक आसन्न संख्या (ऊपर, नीचे, बाएं, दाएं) को स्वैप करना। पहेली तब हल होती है जब तत्व इस तरह व्यवस्थित हों: [[1,2,3],[4,5,0]]।

हमें बोर्ड दिया गया है; हमें न्यूनतम चालों की संख्या ज्ञात करनी है जिससे बोर्ड हल हो जाए। यदि हल करना असंभव है, तो -1 लौटाएं।

उदाहरण

इनपुट

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

आउटपुट

2

व्याख्या

हमें [0,4] फिर [0,5] स्वैप करना होगा।

समाधान दृष्टिकोण (BFS - ब्रेडथ-फर्स्ट सर्च)

1. यदि बोर्ड पहले से हल है, तो 0 लौटाएं।
2. कतार (queue) में प्रारंभिक बोर्ड डालें और विज़िटेड सेट में जोड़ें।
3. स्तर-दर-स्तर BFS चलाएं। प्रत्येक स्तर पर सभी संभावित चालें उत्पन्न करें।
4. 0 की स्थिति ढूंढें, 4 दिशाओं में स्वैप करने का प्रयास करें।
5. नई स्थिति विज़िटेड नहीं है तो कतार में जोड़ें।
6. यदि लक्ष्य स्थिति मिले, तो वर्तमान स्तर लौटाएं।
7. यदि कतार खाली हो जाए, तो -1 लौटाएं।

कार्यकारी प्रोग्राम

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

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

class Solution {
public:
    bool isSolved(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 (isSolved(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--) {
                vector<vector<int>> node = q.front();
                q.pop();
                
                int x = -1, y = -1;
                // 0 की स्थिति ढूंढें
                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;
                        }
                    }
                }
                
                // 4 दिशाओं में प्रयास करें
                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 (isSolved(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);
    return 0;
}

आउटपुट

2