#773 Sliding Puzzle - Solution

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:

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

Example 2:

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

Example 3:

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.

The Sliding Puzzle problem asks you to determine the minimum number of moves required to reach a target board configuration by sliding tiles into the empty space. The key idea is to treat each board configuration as a state and explore all reachable states until the target configuration is found.

A common strategy is to model the puzzle as a graph and apply Breadth-First Search (BFS). Convert the board into a compact representation such as a string, which allows easy comparison and storage in a visited set. From each state, generate new states by swapping the blank tile with its valid neighbors. BFS guarantees the shortest path because it explores configurations level by level.

For optimization, predefine neighbor indices of the blank tile to quickly generate transitions. Since the puzzle size is fixed (e.g., 2×3 board), the total number of possible permutations is limited. BFS combined with memoization of visited states efficiently avoids repeated exploration.

Time Complexity: approximately O(N!) for all possible permutations of tiles, but bounded for small boards. Space Complexity: O(N!) to store visited states and the BFS queue.

Approach	Time Complexity	Space Complexity
Breadth-First Search with state encoding	O(N!)	O(N!)
A* Search (heuristic optimization)	O(N!) worst case, often faster in practice	O(N!)

Solutions (4)

Breadth-First Search (BFS) Approach

The BFS approach performs a level-order traversal beginning from the initial board state, ensuring that the shortest path is found. Each state is enqueued with its move count, and dequeue states expand via possible '0' swaps. Unvisited states are tracked for efficiency.

Time Complexity: O(1) - There are a constant number of states (720) due to permutation limits.
Space Complexity: O(1) - As with time, space usage peaks at 720 given state permutations.

Python C#

1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int SlidingPuzzle(int[][] board) {
6        string start = string.Join("", board[0]) + string.Join("", board[1]);
7        string target = "123450";
8        int[][] neighbors = {
9            new int[] {1, 3},
10            new int[] {0, 2, 4},
11            new int[] {1, 5},
12            new int[] {0, 4},
13            new int[] {3, 1, 5},
14            new int[] {2, 4}
15        };
16        Queue<(string, int)> queue = new Queue<(string, int)>();
17        queue.Enqueue((start, 0));
18        HashSet<string> visited = new HashSet<string> { start };
19        while (queue.Count > 0) {
20            (string status, int steps) = queue.Dequeue();
21            if (status == target) return steps;
22            int zeroIndex = status.IndexOf('0');
23            foreach (int adj in neighbors[zeroIndex]) {
24                char[] newStatus = status.ToCharArray();
25                (newStatus[zeroIndex], newStatus[adj]) = (newStatus[adj], newStatus[zeroIndex]);
26                string newBoard = new string(newStatus);
27                if (!visited.Contains(newBoard)) {
28                    visited.Add(newBoard);
29                    queue.Enqueue((newBoard, steps + 1));
30                }
31            }
32        }
33        return -1;
34    }
35}

Explanation

In this C# solution, BFS is applied to find the minimum swaps to reach the solution. By treating tile positions as a linear string, we swap positions of '0', track visited states to avoid redundancy, and find optimized pathways quickly.

A* Search Algorithm

Utilizing A* search, the algorithm proceeds by maintaining a priority queue based on potential shortest paths (current state cost plus heuristic estimate). The heuristic here is the Manhattan distance, guiding exploration toward the goal efficiently.

Time Complexity: O((6! = 720) log(720))
Space Complexity: O(720), based on the number of states handled.

Java C++

1#include <iostream>
2#include <unordered_set>
3#include <queue>
4#include <vector>
5#include <string>
6#include <cmath>
#include <algorithm>

using namespace std;

struct Node {
    string board;
    int depth;
    int cost;
    bool operator<(const Node& other) const {
        return cost > other.cost;
    }
};

int slidingPuzzle(vector<vector<int>>& board) {
    string start;
    for (auto &row : board)
        for (auto &num : row)
            start += to_string(num);
    string target = "123450";
    vector<vector<int>> neighbor = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {3, 1, 5}, {2, 4}};
    priority_queue<Node> pq;
    unordered_set<string> visited;
    pq.push({start, 0, heuristic(start, target)});

    while (!pq.empty()) {
        Node current = pq.top(); pq.pop();
        if (current.board == target) {
            return current.depth;
        }
        visited.insert(current.board);

        int zeroIndex = current.board.find('0');
        for (int adj : neighbor[zeroIndex]) {
            string newBoard = current.board;
            swap(newBoard[zeroIndex], newBoard[adj]);
            if (visited.find(newBoard) == visited.end()) {
                pq.push({newBoard, current.depth + 1, current.depth + 1 + heuristic(newBoard, target)});
            }
        }
    }
    return -1;
}

int heuristic(const string& state, const string& goal) {
    int dist = 0;
    for (int i = 0; i < state.length(); i++) {
        if (state[i] != '0') {
            int targetPosition = goal.find(state[i]);
            dist += abs(targetPosition / 3 - i / 3) + abs(targetPosition % 3 - i % 3);
        }
    }
    return dist;
}