Sliding Puzzle in C++

Suppose we have one 2x3 board, there are 5 tiles those are represented by the numbers 1 through 5, and one empty square is there, that is represented by 0.

Here a move means 0 and one adjacent number (top, bottom, left or right) and swapping it. This will be solved when the elements are arranged in this manner: [[1,2,3],[4,5,0]].

We have the puzzle board; we have to find the least number of moves required so that the state of the board is solved. If this is not possible to solve, then return -1.

So, if the input is like [[1,2,3],[0,4,5]], then the output will be 2, as we have to swap [0,4], then [0,5].

To solve this, we will follow these steps −

• Define one function slidingPuzzle(), this will take board as input

• if board is perfectly arranged then −

  • return 0

• Define one queue q of 2d matrices

• insert board into q

• Define one set visited for 2d matrices

• insert board into visited

• for initialize lvl := 1, when not q is empty, update (increase lvl by 1), do −

  • sz := size of q

  • while sz is non-zero, decrease sz after each iteration, do −

    • Define one 2D array node = front element of q

    • delete element from q

    • dx := -1, y := -1

    • for initialize i := 0, when i < size of board, update (increase i by 1), do −

      • for initialize j := 0, when j < size of board[0], update (increase j by 1), do −

        • if node[i, j] is same as 0, then −

          • x := i

          • y := j

          • Come out from the loop

    • for initialize k := 0, when k < 4, update (increase k by 1), do −

    • if nx < 0 or ny < 0 or nx >= row count of board or ny >= column count of board, then −

      • Ignore following part, skip to the next iteration

    • exchange node[x, y] and node[nx, ny]

    • if node is in visited, then −

      • exchange node[x, y] and node[nx, ny]

      • Ignore following part, skip to the next iteration

    • insert node into visited

    • if node is perfect arrangemen of boards, then −

      • return lvl

    • insert node into q

    • exchange node[x, y] and node[nx, ny]

• return -1

Let us see the following implementation to get better understanding −

Example

 Live Demo

#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--) {             vector<vector<int> > node = q.front();             q.pop();             int x = -1;             int 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;    } }; main(){    Solution ob;    vector<vector<int>> v = {{1,2,3},{0,4,5}};    cout << (ob.slidingPuzzle(v)); }

Input

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

Output

2