773. Sliding Puzzle - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given a 2 x 3 board which represents a sliding puzzle. The board is represented as a 2D list. The board contains numbers from 0 to 5 where 0 represents the empty space. You can move the empty space by swapping it with one of its neighbors (up, down, left, or right).

Goal:
Rearrange the board to reach the target configuration:

[[1, 2, 3],
 [4, 5, 0]]

Return the minimum number of moves required to reach the target configuration. If it is impossible to solve the puzzle, return -1.

Example 1:

Input: board = [[1, 2, 3], [4, 0, 5]]
Output: 1
Explanation:
Swap the empty space (0) with 5:
[[1, 2, 3], [4, 5, 0]]
The board is solved in 1 move.

Example 2:

Input: board = [[1, 2, 3], [5, 4, 0]]
Output: -1
Explanation:
There is no sequence of moves that transforms the board into the target configuration.

Example 3:

Input: board = [[4, 1, 2], [5, 0, 3]]
Output: 5
Explanation:
One possible sequence of moves is:
1. [[4, 1, 2], [5, 0, 3]]
2. [[4, 1, 2], [0, 5, 3]] (swap 0 and 5)
3. [[0, 1, 2], [4, 5, 3]] (swap 0 and 4)
4. [[1, 0, 2], [4, 5, 3]] (swap 0 and 1)
5. [[1, 2, 0], [4, 5, 3]] (swap 0 and 2)
6. [[1, 2, 3], [4, 5, 0]] (swap 0 and 3)

Constraints:

The board is always a 2x3 grid.
Each number from 0 to 5 appears exactly once on the board.

Hints to Approach the Problem

Think of the board as a state represented by a string.
You can convert the 2D board into a one-dimensional string (e.g., "123450") which makes it easier to track visited states and swap positions.
Use Graph Search Algorithms.
Consider each state as a node in a graph. A valid move (swapping the empty space with one of its neighbors) is an edge. You want to find the shortest path from the initial state to the target state. This naturally suggests using a Breadth-First Search (BFS).

3. Approaches to Solve the Problem

Approach 1: Breadth-First Search (BFS) – The Brute Force Method

Idea:
Since the board has only 6 cells, the total number of states is limited (at most 6! = 720). We can perform a BFS where:

State: Represented as a string (e.g., "412503").
Neighbors: For each state, find all states reachable by swapping the empty space (0) with its adjacent cells.
Goal: Stop when the state equals "123450".

Step-by-Step:

Convert the 2D board to a string.
Define a mapping of indices to their neighbor indices. For example:
- Position 0 can swap with positions 1 and 3.
- Position 1 can swap with positions 0, 2, and 4.
- And so on...
Use a queue to hold states along with the number of moves taken.
Use a set to keep track of visited states.
In each iteration, dequeue a state, check if it is the target. If not, generate all valid moves by swapping 0 with its neighbors.
If the queue is exhausted and the target is not reached, return -1.

Complexity Analysis:

Time Complexity: O(6!) = O(720) in the worst-case (which is constant given the fixed size).
Space Complexity: O(6!) due to the set storing all states.

Approach 2: A* Search (Optimal with Heuristic)

Idea:
Although BFS is sufficient given the small state space, you can also use the A* search algorithm to potentially improve performance using a heuristic. A common heuristic is the Manhattan distance which calculates the sum of the distances of each number from its target position.

Key Points:

Heuristic: Must be admissible (never overestimate the true cost).
Priority Queue: Instead of a simple queue, use a priority queue (min-heap) where states with lower estimated total cost (moves so far + heuristic) are processed first.

Step-by-Step:

Convert the board into a string.
Calculate the Manhattan distance for each state.
Use a priority queue to select the state with the lowest estimated cost.
Proceed similarly as in BFS, but with the ordering given by the heuristic.
This approach is more scalable to larger puzzles (e.g., 3x3 puzzles), though for a 2x3 puzzle, the benefit is marginal.

Complexity Analysis:

Time Complexity: Depends on the heuristic’s efficiency. In worst-case, it still explores many states, but with a good heuristic, fewer states are processed.
Space Complexity: Similar to BFS, O(6!).

Code Implementation

Python Code

Python3

. . . .

Java Code

Java

. . . .

Step-by-Step Walkthrough (Visual Example)

Let’s walkthrough the example board = [[4, 1, 2], [5, 0, 3]].

Initial State:
Represent as "412503".
Target state is "123450".
Find the position of 0:
- In "412503", 0 is at index 4.
Possible moves for index 4:
- Neighbors (from our mapping): indices 1, 3, and 5.
Generate New States:
- Swap 0 with index 1: "402513"
- Swap 0 with index 3: "412053"
- Swap 0 with index 5: "412530"
Enqueue these new states with move count incremented.
Continue this process in a BFS manner until the state "123450" is reached or all states are explored.

Each move “swaps” the position of the empty space with an adjacent number, gradually rearranging the board until (if possible) the target configuration is reached.

Common Mistakes and Edge Cases

Common Mistakes:

Not converting the board to a proper state representation.
It’s easy to miss converting the 2D list into a one-dimensional string which simplifies state comparison.
Forgetting to mark visited states.
Without a visited set, your BFS might revisit the same states, leading to infinite loops or increased runtime.
Incorrect neighbor mapping.
Ensure that you correctly map the positions of the 0 tile to its neighbors based on the board’s layout.
Using DFS instead of BFS.
DFS might find a solution but not necessarily the shortest one, which is critical in this problem.

Edge Cases:

Already Solved Board:
If the input board is already equal to [[1,2,3],[4,5,0]], the function should return 0 moves.
Unsolvable Boards:
Some board configurations cannot reach the target state. In such cases, the algorithm should return -1.

Variations:

Larger Boards (e.g., 3x3 or 4x4):
The sliding puzzle problem can be extended to larger boards (e.g., the classic 8-puzzle or 15-puzzle). These require more sophisticated search techniques like A* with well-designed heuristics.
Different Moves or Constraints:
Variations where the allowed moves are different or additional constraints are added (such as fixed obstacles).

Word Ladder:
Transform one word to another using a series of valid words (BFS on word graphs).
Open the Lock:
Find the minimum number of moves to open a lock by rotating its dials (BFS on state space).
Minimum Genetic Mutation:
Transform one genetic sequence into another with a series of mutations.
8 Puzzle / 15 Puzzle:
Larger sliding puzzles that require more advanced search techniques like A*.

Complexity Analysis Recap

Time Complexity (BFS):
O(6!) = O(720) in the worst-case scenario since there are at most 720 unique states for a 2x3 board.
Space Complexity (BFS):
O(6!) due to the storage of visited states.

For A* search, the worst-case complexity is similar in theory; however, in practice, the heuristic can greatly reduce the number of states processed.