Sliding Puzzle

Sliding Puzzle

What is this problem about?

The "Sliding Puzzle" interview question is a classic state-space search problem. You are given a 2x3 board with numbers 1 through 5 and one empty space (represented by 0). The goal is to find the minimum number of moves to reach the target state [[1,2,3],[4,5,0]]. A move consists of swapping the 0 with an adjacent number (up, down, left, right). This "Sliding Puzzle coding problem" is a variation of the famous 8-puzzle but on a smaller grid.

Why is this asked in interviews?

Companies like Uber and Google ask this because it tests a candidate's ability to model a problem as a graph. Each board configuration is a "state" (a node in the graph), and a move is an "edge" between states. It evaluates your proficiency with Breadth-First Search (BFS) for finding the shortest path in an unweighted graph and your ability to manage visited states using memoization or hash sets.

Algorithmic pattern used

The primary pattern is "Breadth-First Search (BFS) interview pattern". Since we want the minimum number of moves, BFS is the ideal choice.

1. Represent the 2x3 grid as a string to make it easy to store in a hash set (e.g., "123450").
2. Define the possible moves for each index (0-5) in the flattened string.
3. Use a queue to store pairs of (current_state, moves_count).
4. Use a visited set to keep track of seen configurations to avoid infinite loops.
5. Pop the state, check if it's the target, otherwise generate all possible next states by swapping '0' with its neighbors and add new states to the queue.

Example explanation

Initial board: [[4,1,2],[5,0,3]] -> String "412503"

1. Target: "123450"
2. Start BFS with ("412503", 0). Visited: {"412503"}
3. '0' is at index 4. Neighbors: index 1 (up), 3 (left), 5 (right).
4. Possible next states:
   • Swap 0 and 1: "402513"
   • Swap 0 and 5: "412530"
   • Swap 0 and 3: "412053"
5. Add these to the queue and continue until "123450" is found.

Common mistakes candidates make

A common error is not correctly mapping the 2D grid indices to the 1D string indices, especially for "up" and "down" moves. Another mistake is forgetting to use a visited set, which leads to redundant work and potential stack overflow or memory exhaustion. Some candidates might try Depth-First Search (DFS), but DFS does not guarantee the shortest path and is much harder to implement for this specific requirement.

Interview preparation tip

When you need the "shortest path" or "minimum moves" in a graph where all edges have a weight of 1, always reach for BFS. Practice converting 2D grids into strings or integers to simplify the state representation. This technique is useful in many "Sliding Puzzle interview question" variations and pathfinding problems.