# Sliding Puzzle
**Difficulty:** HARD
[External](https://leetcode.com/problems/sliding-puzzle)
Canonical: https://scaleengineer.com/dsa/problems/sliding-puzzle
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Nvidia](https://scaleengineer.com/companies/nvidia)
---
## Problem
On an `2 x 3` board, there are five tiles labeled from `1` to `5`, and an empty square represented by `0`. A **move** consists of choosing `0` and a 4-directionally adjacent number and swapping it.

The state of the board is solved if and only if the board is `[[1,2,3],[4,5,0]]`.

Given the puzzle board `board`, return _the least number of moves required so that the state of the board is solved_. If it is impossible for the state of the board to be solved, return `-1`.

**Example 1:**

![](https://assets.glich.co/dsa/sliding-puzzle/image0.jpg) 

**Input:** board = [[1,2,3],[4,0,5]]
**Output:** 1
**Explanation:** Swap the 0 and the 5 in one move.

**Example 2:**

![](https://assets.glich.co/dsa/sliding-puzzle/image1.jpg) 

**Input:** board = [[1,2,3],[5,4,0]]
**Output:** -1
**Explanation:** No number of moves will make the board solved.

**Example 3:**

![](https://assets.glich.co/dsa/sliding-puzzle/image2.jpg) 

**Input:** board = [[4,1,2],[5,0,3]]
**Output:** 5
**Explanation:** 5 is the smallest number of moves that solves the board.
An example path:
After move 0: [[4,1,2],[5,0,3]]
After move 1: [[4,1,2],[0,5,3]]
After move 2: [[0,1,2],[4,5,3]]
After move 3: [[1,0,2],[4,5,3]]
After move 4: [[1,2,0],[4,5,3]]
After move 5: [[1,2,3],[4,5,0]]

**Constraints:**

* `board.length == 2`
* `board[i].length == 3`
* `0 <= board[i][j] <= 5`
* Each value `board[i][j]` is **unique**.

# Approaches
## Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path in a state graph, where each node is a unique board configuration and edges connect configurations that are reachable in a single move. Breadth-First Search (BFS) is a classic and ideal algorithm for finding the shortest path in an unweighted graph like this. We start from the initial board configuration and explore its neighbors, then the neighbors of those neighbors, and so on, level by level. This guarantees that the first time we reach the target configuration, we have done so in the minimum possible number of moves.
**Time:** O(N * K), where N is the total number of states and K is the maximum number of neighbors for a state. For this problem, N = 720 and K = 4. The algorithm visits each state and each transition at most once. Since N and K are constants, the time complexity is effectively O(1). · **Space:** O(N), where N is the total number of possible states. For a 2x3 board with 6 unique tiles, N = 6! = 720. The space is needed for the queue and the visited set, which in the worst case might store all possible states. Since N is a constant, the complexity is O(1).
**Pros:** Guaranteed to find the shortest path because it explores the graph level by level.; Relatively simple to understand and implement.
**Cons:** Explores the state space blindly without any guidance, which can be inefficient for problems with larger state spaces.; May visit many states that are far from the solution before finding the target.
### Explanation
To implement BFS, we first need a convenient way to represent the board state. A 2x3 integer array is cumbersome to use as a key in a hash set or map for tracking visited states. A better approach is to flatten the 2x3 board into a 6-character string, e.g., `[[1,2,3],[4,0,5]]` becomes `"123405"`. This string representation is unique for each board state and easy to work with.

The core of the algorithm is a queue that holds the states to be explored and a set that stores states we have already visited to prevent cycles and redundant work. We start by adding the initial state string to the queue and the visited set. The search proceeds in levels, where each level corresponds to one move. In each iteration of the main loop, we process all the states currently in the queue. For each state, we generate all possible next states by swapping the '0' tile with its valid neighbors. If a generated neighbor state has not been visited before, we add it to the queue and the visited set. We continue this process until we find the target state `"123450"` or the queue becomes empty, indicating the puzzle is unsolvable.

```java
class Solution {
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();

        if (start.equals(target)) {
            return 0;
        }

        // Precomputed possible moves for the '0' at each index (0-5)
        int[][] moves = new int[][]{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        queue.offer(start);
        visited.add(start);
        
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                if (current.equals(target)) {
                    return level;
                }
                
                int zeroPos = current.indexOf('0');
                
                for (int nextPos : moves[zeroPos]) {
                    char[] chars = current.toCharArray();
                    char temp = chars[zeroPos];
                    chars[zeroPos] = chars[nextPos];
                    chars[nextPos] = temp;
                    String nextState = new String(chars);
                    
                    if (!visited.contains(nextState)) {
                        visited.add(nextState);
                        queue.offer(nextState);
                    }
                }
            }
            level++;
        }
        
        return -1;
    }
}
```
### Algorithm
- Convert the 2x3 `board` into a single string `start` for easier manipulation and storage.
- Define the `target` string as "123450".
- Initialize a queue and add the `start` state.
- Initialize a `visited` set to keep track of states we've already processed, and add `start` to it.
- Initialize a `moves` counter to 0.
- While the queue is not empty, perform a level-order traversal:
  - Process all states at the current level (get the queue `size`).
  - For each `current` state dequeued:
    - If `current` matches the `target`, we have found the shortest path. Return the current `moves` count.
    - Find the index of the empty tile '0'.
    - Generate all valid neighbor states by swapping '0' with its adjacent tiles.
    - For each `nextState` that has not been visited, add it to the queue and the `visited` set.
  - Increment the `moves` counter after processing each level.
- If the queue becomes empty and the target has not been reached, it means the puzzle is unsolvable. Return -1.

## A* Search Algorithm
A* Search is an informed search algorithm that improves upon BFS by using a heuristic function to guide its search towards the goal. It prioritizes exploring states that appear to be closer to the solution. The priority of a state `n` is determined by the formula `f(n) = g(n) + h(n)`, where `g(n)` is the actual cost (number of moves) from the start state to `n`, and `h(n)` is the estimated (heuristic) cost from `n` to the target state. By exploring states with the lowest `f(n)` value first, A* can find the shortest path much more efficiently than a blind search.
**Time:** O(N log N), where N is the number of states explored. The `log N` factor comes from the priority queue operations. Since A* explores fewer states than BFS, it's generally faster despite the logarithmic factor. For this problem's fixed state space, the complexity is constant, O(1). · **Space:** O(N), where N is the number of states. In the worst case, it might need to store all states in the priority queue and the cost map. For this problem, N=720, so the space is constant, O(1).
**Pros:** Generally more efficient than blind search algorithms like BFS because it explores fewer states.; Guaranteed to find the shortest path if the heuristic function is admissible (like Manhattan distance).
**Cons:** More complex to implement than BFS due to the priority queue and heuristic calculation.; The performance is highly dependent on the quality of the heuristic function.
### Explanation
For the A* algorithm, we use a priority queue to store states, ordered by their `f(n)` value. A good heuristic `h(n)` for sliding puzzles is the **Manhattan distance**. For each tile (from 1 to 5), we calculate the sum of the absolute differences of its current coordinates and its target coordinates. This heuristic is **admissible** (it never overestimates the true cost), which is a crucial property that guarantees A* will find the optimal solution.

We also maintain a map to store the minimum `g(n)` cost found so far for each visited state. This prevents us from exploring longer paths to states we've already reached more efficiently.

The algorithm proceeds by repeatedly extracting the most promising state (lowest `f` value) from the priority queue. If it's the target, we're done. Otherwise, we generate its neighbors, calculate their `g` and `h` costs, and add them to the priority queue if they represent a better path to that state. This guided approach prunes large parts of the search space that are unlikely to be on the shortest path.

```java
class Solution {
    class State {
        String board;
        int g; // cost from start
        int h; // heuristic cost to target

        State(String board, int g, int h) {
            this.board = board;
            this.g = g;
            this.h = h;
        }
    }

    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        String startStr = sb.toString();

        if (startStr.equals(target)) return 0;

        // Precompute target positions for heuristic calculation
        int[][] targetPos = new int[6][2];
        targetPos[1] = new int[]{0, 0}; targetPos[2] = new int[]{0, 1}; targetPos[3] = new int[]{0, 2};
        targetPos[4] = new int[]{1, 0}; targetPos[5] = new int[]{1, 1}; targetPos[0] = new int[]{1, 2};

        PriorityQueue<State> pq = new PriorityQueue<>((a, b) -> (a.g + a.h) - (b.g + b.h));
        Map<String, Integer> gCosts = new HashMap<>();

        int startH = calculateHeuristic(startStr, targetPos);
        pq.offer(new State(startStr, 0, startH));
        gCosts.put(startStr, 0);

        int[][] moves = new int[][]{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

        while (!pq.isEmpty()) {
            State current = pq.poll();

            if (current.board.equals(target)) {
                return current.g;
            }

            int zeroPos = current.board.indexOf('0');
            for (int nextPos : moves[zeroPos]) {
                char[] chars = current.board.toCharArray();
                char temp = chars[zeroPos];
                chars[zeroPos] = chars[nextPos];
                chars[nextPos] = temp;
                String nextStateStr = new String(chars);

                int newG = current.g + 1;
                if (gCosts.getOrDefault(nextStateStr, Integer.MAX_VALUE) <= newG) {
                    continue;
                }

                gCosts.put(nextStateStr, newG);
                int newH = calculateHeuristic(nextStateStr, targetPos);
                pq.offer(new State(nextStateStr, newG, newH));
            }
        }
        return -1;
    }

    private int calculateHeuristic(String board, int[][] targetPos) {
        int h = 0;
        for (int i = 0; i < 6; i++) {
            int tile = board.charAt(i) - '0';
            if (tile == 0) continue;
            int currentX = i / 3;
            int currentY = i % 3;
            int targetX = targetPos[tile][0];
            int targetY = targetPos[tile][1];
            h += Math.abs(currentX - targetX) + Math.abs(currentY - targetY);
        }
        return h;
    }
}
```
### Algorithm
- Define a `State` object to hold the board string, `g` cost (moves from start), and `f` cost (`g` + heuristic).
- Initialize a priority queue ordered by the `f` cost (lowest first).
- Initialize a map `gCosts` to store the minimum moves found so far to reach any state.
- Calculate the heuristic (Manhattan distance) for the `start` state.
- Add the initial `State(start, 0, h(start))` to the priority queue and `gCosts` map.
- While the priority queue is not empty:
  - Poll the state `current` with the lowest `f` cost.
  - If `current` is the target state, return its `g` cost.
  - Generate all valid neighbor states.
  - For each `nextState`:
    - Calculate its new `g` cost (`current.g + 1`).
    - If a shorter or equal path to `nextState` has already been found (i.e., it's in `gCosts` with a lower value), skip it.
    - Otherwise, update its `g` cost in `gCosts`, calculate its heuristic `h`, and add the new `State` to the priority queue.
- If the loop finishes, the target is unreachable, so return -1.

## Bidirectional Breadth-First Search
Bidirectional BFS is a powerful optimization that performs two simultaneous searches: one forward from the initial state and one backward from the target state. The search terminates as soon as the two search frontiers intersect. This approach dramatically reduces the search space compared to a single-ended search. If the shortest path has length `d` and the branching factor is `b`, a standard BFS explores roughly `b^d` states, whereas a bidirectional BFS explores roughly `2 * b^(d/2)` states. This exponential reduction makes it highly efficient for finding shortest paths.
**Time:** O(b^(d/2)). The algorithm runs two searches that meet in the middle, each exploring to a depth of roughly `d/2`. This provides an exponential speedup over standard BFS. For this problem, the complexity is constant, O(1). · **Space:** O(b^(d/2)), where `b` is the branching factor and `d` is the shortest path length. This is needed to store the two frontiers and the visited set. For this problem, this is constant space, O(1), but theoretically much smaller than a single BFS.
**Pros:** Significantly faster than standard BFS by drastically reducing the number of states explored.; Often the most efficient algorithm for shortest path problems on unweighted graphs with a known target.; Lower overhead per node compared to A* as it doesn't require heuristic calculations or a priority queue.
**Cons:** Slightly more complex to implement than a standard BFS.; Requires the target state to be known and the graph transitions to be reversible, both of which are true for this problem.
### Explanation
The implementation uses two sets to represent the frontiers of the forward and backward searches. We also use a general `visited` set to ensure we don't process any state more than once. We initialize the forward frontier with the `start` state and the backward frontier with the `target` state.

The main loop proceeds level by level, but with a twist. In each step, we first check which frontier is smaller and choose to expand that one. This keeps the two search 'circles' roughly the same size, maximizing the chance of an early intersection. We generate all neighbors for each state in the chosen frontier. If any neighbor is already in the other frontier, we have found a meeting point and thus the shortest path. The length of this path is the current number of moves made. If a neighbor is new (not in the `visited` set), we add it to a temporary set for the next level and to the `visited` set. This process continues until the frontiers meet or one becomes empty.

```java
class Solution {
    public int slidingPuzzle(int[][] board) {
        String target = "123450";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        String start = sb.toString();

        if (start.equals(target)) return 0;

        int[][] moves = new int[][]{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};

        Set<String> q_fwd = new HashSet<>();
        Set<String> q_bwd = new HashSet<>();
        Set<String> visited = new HashSet<>();

        q_fwd.add(start);
        q_bwd.add(target);
        visited.add(start);
        visited.add(target);
        
        int dist = 0;
        while (!q_fwd.isEmpty() && !q_bwd.isEmpty()) {
            // Always expand the smaller frontier
            if (q_fwd.size() > q_bwd.size()) {
                Set<String> temp = q_fwd;
                q_fwd = q_bwd;
                q_bwd = temp;
            }

            dist++;
            Set<String> next_level = new HashSet<>();
            for (String current : q_fwd) {
                int zeroPos = current.indexOf('0');
                for (int nextPos : moves[zeroPos]) {
                    char[] chars = current.toCharArray();
                    char temp = chars[zeroPos];
                    chars[zeroPos] = chars[nextPos];
                    chars[nextPos] = temp;
                    String nextState = new String(chars);

                    if (q_bwd.contains(nextState)) {
                        return dist;
                    }
                    if (!visited.contains(nextState)) {
                        visited.add(nextState);
                        next_level.add(nextState);
                    }
                }
            }
            q_fwd = next_level;
        }
        return -1;
    }
}
```
### Algorithm
- Initialize two sets, `q_fwd` for the forward search frontier and `q_bwd` for the backward search frontier. Add the `start` state to `q_fwd` and the `target` state to `q_bwd`.
- Use a single `visited` set to track all states explored from both directions, initially containing `start` and `target`.
- Initialize a `moves` counter to 0.
- In a loop that continues as long as both frontiers are non-empty:
  - To keep the search balanced, always choose to expand the smaller of the two frontiers.
  - Increment `moves`.
  - Create a `next_level` set to store the new frontier.
  - For each `state` in the chosen frontier:
    - Generate all its neighbor states.
    - For each `nextState`:
      - If the `nextState` is found in the *other* frontier, it means the two searches have met. A path is found, so return the current `moves` count.
      - If the `nextState` has not been visited before, add it to the `visited` set and the `next_level` set.
  - Replace the expanded frontier with the `next_level` set.
- If the loop terminates because one frontier becomes empty, the puzzle is unsolvable. Return -1.

# Solutions
### Java

```java
class Solution {
private
  int m = 2;
private
  int n = 3;
public
  int slidingPuzzle(int[][] board) {
    String start = "";
    String end = "123450";
    String seq = "";
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        start += board[i][j];
        if (board[i][j] != 0) {
          seq += board[i][j];
        }
      }
    }
    if (!check(seq)) {
      return -1;
    }
    PriorityQueue<Pair<Integer, String>> q =
        new PriorityQueue<>(Comparator.comparingInt(Pair : : getKey));
    Map<String, Integer> dist = new HashMap<>();
    dist.put(start, 0);
    q.offer(new Pair<>(f(start), start));
    int[] dirs = {-1, 0, 1, 0, -1};
    while (!q.isEmpty()) {
      String state = q.poll().getValue();
      int step = dist.get(state);
      if (end.equals(state)) {
        return step;
      }
      int p1 = state.indexOf("0");
      int i = p1 / n, j = p1 % n;
      char[] s = state.toCharArray();
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n) {
          int p2 = x * n + y;
          swap(s, p1, p2);
          String next = String.valueOf(s);
          if (!dist.containsKey(next) || dist.get(next) > step + 1) {
            dist.put(next, step + 1);
            q.offer(new Pair<>(step + 1 + f(next), next));
          }
          swap(s, p1, p2);
        }
      }
    }
    return -1;
  }
private
  void swap(char[] arr, int i, int j) {
    char t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
private
  int f(String s) {
    int ans = 0;
    for (int i = 0; i < m * n; ++i) {
      if (s.charAt(i) != '0') {
        int num = s.charAt(i) - '1';
        ans += Math.abs(i / n - num / n) + Math.abs(i % n - num % n);
      }
    }
    return ans;
  }
private
  boolean check(String s) {
    int n = s.length();
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        if (s.charAt(i) > s.charAt(j)) {
          ++cnt;
        }
      }
    }
    return cnt % 2 == 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int m = 2;
  int n = 3;
  int slidingPuzzle(vector<vector<int>> &board) {
    string start, seq;
    string end = "123450";
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        start += char(board[i][j] + '0');
        if (board[i][j] != 0)
          seq += char(board[i][j] + '0');
      }
    }
    if (!check(seq))
      return -1;
    typedef pair<int, string> PIS;
    priority_queue<PIS, vector<PIS>, greater<PIS>> q;
    unordered_map<string, int> dist;
    dist[start] = 0;
    q.push({f(start), start});
    vector<int> dirs = {-1, 0, 1, 0, -1};
    while (!q.empty()) {
      PIS t = q.top();
      q.pop();
      string state = t.second;
      int step = dist[state];
      if (state == end)
        return step;
      int p1 = state.find('0');
      int i = p1 / n, j = p1 % n;
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x < 0 || x >= m || y < 0 || y >= n)
          continue;
        int p2 = x * n + y;
        swap(state[p1], state[p2]);
        if (!dist.count(state) || dist[state] > step + 1) {
          dist[state] = step + 1;
          q.push({step + 1 + f(state), state});
        }
        swap(state[p1], state[p2]);
      }
    }
    return -1;
  }
  bool check(string s) {
    int n = s.size();
    int cnt = 0;
    for (int i = 0; i < n; ++i)
      for (int j = i; j < n; ++j)
        if (s[i] > s[j])
          ++cnt;
    return cnt % 2 == 0;
  }
  int f(string s) {
    int ans = 0;
    for (int i = 0; i < m * n; ++i) {
      if (s[i] == '0')
        continue;
      int num = s[i] - '1';
      ans += abs(num / n - i / n) + abs(num % n - i % n);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int: m, n = 2, 3 seq = [] start, end = '', '123450' for i in range(m): for j in range(n): if board[i][j] != 0: seq . append(board[i][j]) start += str(board[i][j]) def check(seq): n = len(seq) cnt = sum(seq[i] > seq[j] for i in range(n) for j in range(i, n)) return cnt % 2 == 0 def f(s): ans = 0 for i in range(m * n): if s[i] != '0': num = ord(s[i]) - ord('1') ans += abs(i // n - num // n) + abs(i % n - num % n) return ans if not check(seq): return - 1 q = [(f(start), start)] dist = {start: 0} while q: _, state = heappop(q) if state == end: return dist[state] p1 = state . index('0') i, j = p1 // n, p1 % n s = list(state) for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n: p2 = x * n + y s[p1], s[p2] = s[p2], s[p1] next = '' . join(s) s[p1], s[p2] = s[p2], s[p1] if next not in dist or dist[next] > dist[state] + 1: dist[next] = dist[state] + 1 heappush(q, (dist[next] + f(next), next)) return - 1

```