This problem requires calculating the fewest moves to reach the solved 2x3 board state using state transition dynamic programming. Use BFS to explore all valid board configurations, treating each as a node and moves as edges. Memoization prevents revisiting states, ensuring the algorithm handles unsolvable boards by returning -1 efficiently.
Problem Statement
You are given a 2x3 board representing a sliding puzzle with tiles numbered 1 to 5 and one empty square 0. A move consists of swapping 0 with a 4-directionally adjacent tile. The goal is to transform the board into the solved state [[1,2,3],[4,5,0]].
Given any initial configuration of the board, compute the minimum number of moves required to reach the solved state. If the board cannot be solved, return -1. Each board position is unique and within the range 0 to 5.
Examples
Example 1
Input: board = [[1,2,3],[4,0,5]]
Output: 1
Swap the 0 and the 5 in one move.
Example 2
Input: board = [[1,2,3],[5,4,0]]
Output: -1
No number of moves will make the board solved.
Example 3
Input: board = [[4,1,2],[5,0,3]]
Output: 5
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.
Solution Approach
Use Breadth-First Search over Board States
Model each board configuration as a node and legal swaps of 0 as edges. BFS guarantees the minimum moves are found first. Keep a queue of states with their current move count.
Memoize Visited Configurations
Store visited board states to prevent cycles and redundant exploration. This is crucial because many states can be reached through different sequences of moves.
Map Neighbor Indices for Efficient Swaps
Precompute 0's possible moves using a mapping of index positions to adjacent indices. This allows constant-time swaps and keeps BFS traversal fast for each state.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O((m \cdot n)! \times (m \cdot n)) |
| Space | O((m \cdot n)!) |
Time complexity is O((m * n)! * (m * n)) because each unique board state is visited once and generating neighbors takes O(m * n). Space complexity is O((m * n)!) due to storing all visited states.
What Interviewers Usually Probe
- Candidate tries BFS but does not track visited states.
- Candidate fails to map 0's neighbors efficiently, slowing traversal.
- Candidate confuses solvable and unsolvable board configurations.
Common Pitfalls or Variants
Common pitfalls
- Not memoizing visited boards leads to exponential runtime.
- Swapping tiles incorrectly due to wrong index mapping.
- Returning a move count for unsolvable boards instead of -1.
Follow-up variants
- Generalize to m x n sliding puzzles for larger boards using the same BFS + DP approach.
- Return the actual sequence of moves that solves the puzzle, not just the count.
- Use A* search with Manhattan distance heuristic instead of pure BFS to optimize performance.
How GhostInterview Helps
- GhostInterview provides step-by-step BFS traversal and state memoization for Sliding Puzzle boards.
- It identifies unsolvable states immediately and shows correct handling patterns for state transition DP.
- Offers debugging cues when swaps or move counts are miscalculated during board exploration.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the most efficient way to solve Sliding Puzzle on a 2x3 board?
Use BFS treating each board as a node, edges as swaps of 0, and memoize visited states to find minimum moves quickly.
Why is state transition dynamic programming relevant for Sliding Puzzle?
Each board state depends on previous moves; memoization avoids recomputing moves for states already explored, a classic state transition DP pattern.
Can Sliding Puzzle be unsolvable?
Yes, some configurations cannot reach [[1,2,3],[4,5,0]], in which case the algorithm should return -1.
How do I efficiently generate next moves from a board state?
Precompute 0's adjacent positions as neighbor indices and swap in constant time during BFS traversal.
What is the time complexity of solving Sliding Puzzle with BFS?
O((m * n)! * (m * n)), since every unique board state is explored once and generating neighbors costs O(m * n).
Need direct help with Sliding Puzzle instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Sliding Puzzle from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the length of the longest increasing path in a matrix with given movement constraints using graph techniques.
Open problem page#698 Partition to K Equal Sum SubsetsDetermine if an integer array can be partitioned into k subsets where each subset sums to the same value using DP and backtracking.
Open problem page#691 Stickers to Spell WordDetermine the minimum number of stickers needed to spell a target word using array scanning and hash lookups for efficient letter tracking.
Open problem page