Sliding Puzzle - Solution & Explanation

Problem Overview: You are given a 2x3 board containing numbers 1–5 and an empty tile represented by 0. Each move swaps the empty tile with one of its adjacent tiles. The task is to determine the minimum number of moves required to reach the target configuration [[1,2,3],[4,5,0]]. If the configuration cannot reach the goal state, return -1.

Approach 1: Breadth-First Search (BFS) (Time: O((m*n)!), Space: O((m*n)!))

This puzzle naturally forms a graph where each board configuration is a node and each valid tile swap is an edge. Breadth-First Search works well because every move has equal cost, and BFS guarantees the shortest path to the goal. Convert the board into a string such as "123450" so configurations can be stored in a hash set for fast visited checks. For every state, locate the index of 0, generate neighbors by swapping it with valid adjacent indices, and push unseen states into the queue. Since the puzzle has at most 6! = 720 states, BFS quickly explores all reachable configurations. This approach is straightforward and reliable for interview settings.

The board itself can be treated like a flattened array, and adjacency rules define which indices the blank tile can swap with. Using a visited set prevents revisiting states and avoids exponential blow‑up.

Approach 2: A* Search Algorithm (Time: O(b^d) worst case, typically faster; Space: O(b^d))

A* search improves exploration efficiency by prioritizing states closer to the goal. Each state is assigned a score f(n) = g(n) + h(n), where g(n) is the number of moves taken so far and h(n) is a heuristic estimating remaining distance. A common heuristic for sliding puzzles is the Manhattan distance between each tile’s current and target positions in the matrix. The algorithm stores states in a priority queue ordered by the smallest estimated total cost.

When expanding nodes, generate neighboring configurations the same way as BFS by swapping the blank tile. The heuristic guides the search toward promising states instead of exploring blindly. For larger sliding puzzles (like 8‑puzzle or 15‑puzzle), A* dramatically reduces the number of explored states compared to BFS. Even for the 2x3 variant, it demonstrates how heuristic search works in pathfinding problems.

Recommended for interviews: BFS is usually the expected solution because it clearly models the puzzle as an unweighted graph and guarantees the minimum number of moves. Implementing BFS with a queue and visited set demonstrates solid understanding of state‑space traversal. A* is a strong follow‑up optimization that shows deeper knowledge of heuristic search and algorithm design.