773. Sliding Puzzle - Detailed Explanation
Problem Statement
Description:
You are given a 2 x 3 board (a sliding puzzle) where the board is represented as a 2D array. The board contains numbers from 1 to 5 and one empty slot represented by 0. The goal is to determine the minimum number of moves required to reach the target configuration:
[[1, 2, 3],
[4, 5, 0]]
A move is defined as sliding an adjacent number into the empty slot (0). The allowed moves are up, down, left, or right—but only moves that stay within the board's boundaries are permitted.
If the puzzle is unsolvable, return -1.
Example 1:
- Input:
board = [[1, 2, 3], [4, 0, 5]] - Output:
1 - Explanation:
Only one move is needed by sliding the 5 into the empty space.
Example 2:
- Input:
board = [[1, 2, 3], [5, 4, 0]] - Output:
-1 - Explanation:
The board cannot be solved to reach the target configuration.
Example 3:
- Input:
board = [[4, 1, 2], [5, 0, 3]] - Output:
5 - Explanation:
One sequence of moves to reach the target configuration is:- Move 0 right: [[4, 1, 2], [5, 3, 0]]
- Move 0 up: [[4, 1, 0], [5, 3, 2]]
- Move 0 left: [[4, 0, 1], [5, 3, 2]]
- Move 0 down: [[4, 3, 1], [5, 0, 2]]
- Move 0 right: [[4, 3, 1], [5, 2, 0]] (Note that the exact sequence may vary; the key is that the minimum number of moves is 5.)
Constraints:
- The board is always of size 2 x 3.
- The board contains exactly one 0.
- The numbers in the board range from 0 to 5.
Hints Before You Begin
-
Hint 1:
Think of each board configuration as a unique state. Since the board is small (2x3), you can represent a state as a string (for example, "123450" for the target state). -
Hint 2:
Use Breadth-First Search (BFS) to explore the state space. Each valid move from the current configuration produces a new state. BFS will help you find the minimum number of moves needed to reach the target state.
Approaches to Solve the Problem
1. Brute Force / Exhaustive Search
Idea:
Try all possible sequences of moves from the initial configuration until the target state is reached.
Downside:
- The state space can be explored repeatedly if not managed properly.
- It’s inefficient without a way to mark visited states.
2. BFS (Breadth-First Search)
Idea:
BFS is well suited for finding the minimum number of moves.
Steps:
-
State Representation:
Represent each board configuration as a string (e.g., "123450"). -
Queue and Visited Set:
Use a queue to perform BFS and a set to record visited states. -
State Transitions:
For each state, determine the index of 0 and compute all possible states that result from moving 0 up, down, left, or right. Use an index mapping or precomputed neighbors for each index (0 through 5) on the 2x3 board. -
Termination:
Return the number of moves when the target state ("123450") is reached. If the queue is exhausted without reaching the target, return -1.
Benefits:
- BFS guarantees that the first time the target is reached, it is with the minimum number of moves.
- The 2x3 board limits the total number of states, so the approach is efficient.
3. Alternative Approaches
-
Bidirectional BFS:
Instead of exploring from only the start state, you could simultaneously explore from both the start and target states. This may reduce the number of levels explored. -
A Search (Heuristic Search):*
By using a heuristic (for example, the Manhattan distance of tiles from their target positions), A* can guide the search more efficiently. However, for this problem size, standard BFS is typically sufficient.
Code Implementations
Python Code Implementation
Java Code Implementation
Complexity Analysis
-
Time Complexity:
The total number of unique states for a 2x3 board is limited (at most 720, since 6! = 720). In the worst case, BFS will explore all possible states. Therefore, the time complexity is O(1) in practical terms, but it is commonly expressed as O(V + E) where V is the number of vertices (states) and E is the number of transitions between states. -
Space Complexity:
The space complexity is determined by the queue and the visited set, which in the worst-case scenario may store all possible states. Hence, it is O(720) which is constant for this fixed board size.
Common Pitfalls and Edge Cases
Common Pitfalls:
-
State Representation:
Not converting the 2D board into a consistent string or hashable representation may lead to difficulties in tracking visited states. -
Index Mapping Errors:
Carefully mapping neighbors for each index in the 2x3 board is crucial. An error here can lead to invalid moves or index out-of-bound exceptions. -
Infinite Loops:
Failing to mark visited states can cause the BFS to revisit the same configurations repeatedly.
Edge Cases:
-
Already Solved Board:
If the input board is already in the target configuration, the solution should return 0 moves. -
Unsolvable Puzzle:
If no sequence of moves leads to the target state, ensure that the algorithm correctly returns -1.
Alternative Variations and Related Problems
Alternative Variations:
-
Bidirectional BFS:
Simultaneously perform BFS from both the start and target states. This can sometimes reduce the search space further. -
A Search:*
Use a heuristic (such as the Manhattan distance) to guide the search. While more complex, A* can be effective for larger puzzles.
Related Problems for Further Practice:
-
15-Puzzle:
A classic sliding puzzle with a 4x4 grid. -
Sudoku Solver:
A problem that requires state-space search and backtracking. -
Word Ladder:
Transform one word into another with a series of allowed changes, also typically solved using BFS.
GET YOUR FREE
Coding Questions Catalog
