Sliding Puzzle (LeetCode 773)
You have a 2 x 3 sliding-tile board: five numbered tiles 1-5 plus one empty slot marked 0. A move swaps the empty slot with a tile that's directly above, below, left, or right of it.
The board counts as solved only when it reads [[1,2,3],[4,5,0]].
Return the fewest moves needed to reach that solved layout from the given board, or -1 if no sequence of moves can solve it.
Worked Examples
board = [[1,2,3],[4,0,5]]1board = [[1,2,3],[5,4,0]]-1board = [[4,1,2],[5,0,3]]5⚖️Formal Constraints & Bounds
board.length == 2board[i].length == 30 <= board[i][j] <= 5Each value
board[i][j]is unique.
Core Insight
The tile board and the deadend lock are the same shape of problem: serialize the whole state into one hashable value, precompute its neighbor rule once, then BFS.
Real-World Scenario & Production Applications
Physical sliding-tile puzzles (15-puzzle style toys) and any small finite configuration space where the goal is minimum moves between two board layouts.
Subproblems & Recurrence Decomposition3 Phases
A 2D board is awkward to compare and hash. Flattening it row-by-row into a single 6-character string turns 'have I already explored this exact board?' into an instant O(1) set lookup.
start = "".join(str(x) for row in board for x in row)
target = "123450"Step-by-Step Execution Trace Table
Hand-Executed Step Trace (board = [[1,2,3],[4,0,5]])
| Moves | Dequeued State | Blank Index | Candidate Swaps | Target Check | Enqueued Neighbors (Marked on Enqueue) |
|---|---|---|---|---|---|
| 0 | "123405" | 4 | swap with 1, 3, 5 -> "103425", "120435", "123450" | "123450" == target! | Return moves + 1 = 1 ✅ |
board = [[1,2,3],[4,0,5]]1Hand-Executed Step Trace (board = [[1,2,3],[4,0,5]])
| Moves | Dequeued State | Blank Index | Candidate Swaps | Target Check | Enqueued Neighbors (Marked on Enqueue) |
|---|---|---|---|---|---|
| 0 | "123405" | 4 | swap with 1, 3, 5 -> "103425", "120435", "123450" | "123450" == target! | Return moves + 1 = 1 ✅ |
| 1 | start = flatten(board) |
| 2 | target = '123450' |
| 3 | if start == target: |
| 4 | return 0 |
| 5 | queue = deque([(start, 0)]) |
| 6 | visited = {start} |
| 7 | while queue: |
| 8 | state, moves = queue.popleft() |
| 9 | zero = state.index('0') |
| 10 | for nb in neighbors[zero]: |
| 11 | nxt = state with the tiles at zero and nb swapped |
| 12 | if nxt == target: |
| 13 | return moves + 1 |
| 14 | if nxt not in visited: |
| 15 | visited.add(nxt) |
| 16 | queue.append((nxt, moves + 1)) |
| 17 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The 15-puzzle (or sliding puzzle) looks like a mechanical game, but it is an implicit graph traversal problem. A board containing digits through has exactly possible configurations. Each unique board arrangement is a single node in a 720-node state graph. An edge exists between two nodes if swapping the empty slot (digit ) with an adjacent tile transforms one configuration into the other. Finding the minimum moves to reach the solved target "123450" is simply unweighted BFS on this finite 720-node permutation graph.
🏟️ The Analogy: A Combination Lock with 720 Discrete Faces
Imagine a Rubik's-style puzzle box that can display 720 distinct symbols on its face. Each turn of a dial transitions the box to one of 2, 3, or 4 adjacent symbols. You want to reach the "unlocked" symbol "123450". Because there are only 720 possible configurations in the entire universe of the puzzle, you could write every configuration on an index card. Finding the shortest sequence of turns is just tracing the shortest chain of cards from your starting state to the unlocked card.
🔑 Why It Works
Serializing the board into a string enables hashing in the visited set, turning a confusing 2D matrix swap problem into a clean, deterministic graph traversal.
Mutating 2D grid instead of string serialization: Serializing the 2x3 board as a 6-character string (e.g.
'123450') allows hashing and clean state transitions.Wrong precomputed adjacency mapping: In a 2x3 board flattened to indices 0..5, index 2 can move to indices 1 and 5 (not 3, as index 3 is on the next row). Verify neighbor list for all 6 slots.
Unreachable target state: Some permutations of the 15-puzzle/8-puzzle are mathematically unreachable (odd parity of inversions); BFS must return
-1when queue empties.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Small finite discrete configuration space + minimum moves to a single fixed goal configuration.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: flattening the board into a string turns 'have I seen this board before?' into an O(1) set lookup, and the blank's legal swap partners depend only on grid shape, not board contents.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Comparing 2D board arrays directly instead of serializing to a string, making the visited set unusable.
Recomputing legal neighbor positions per board instead of precomputing them once from the fixed 2x3 shape.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I flatten the board into a 6-character string, then BFS using a precomputed adjacency table of which flattened index the blank ('0') can swap with. Mark-on-enqueue against a visited set of seen strings, and return the move count the instant a swap produces '123450'. Bounded by the 720-state permutation space."
Complexity & Mathematical Proof
O(R!)
Look at the execution steps: the board has R = 6 fixed cells, so there are at most R! = 720 distinct permutations (states). Each state generates at most 4 neighbor swaps (blank has at most 4 legal partners), and building each candidate string takes O(R) time.
O(R!) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Visited set and BFS queue hold at most R! = 720 strings, each of length R = 6.
T(R) = R! · 4 · O(R) = O(R! · R)
Derivation Progression
R! = 720 total distinct board permutations
Finite permutation graph with a fixed, tiny vertex count.
<= 4 transitions per state
The blank's precomputed adjacency list has at most 4 legal swap partners on a 2x3 grid.
O(R) per state creation
Copies and re-joins the flattened board string per candidate swap.
Variable Definitions
Total number of cells on the board (R = 6 for a 2x3 grid)
Memory Architecture & Bounds
O(1) Iterative
O(R!) Visited set and BFS queue of board strings
O(1) Moves count integer
Boundary Best / Worst Cases
if the board starts already solved.
.
visiting all 720 reachable board permutations.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "least number of moves to solve 2x3 board". Board state serialization: flatten the grid into a 6-character string (e.g. "123450"). Each move swaps '0' with an adjacent index.
Total state permutations: . Maximum states is strictly 720.
Unsolvable boards: if BFS exhausts the queue without reaching "123450", return -1.
Sliding Puzzle (LeetCode 773)
You have a 2 x 3 sliding-tile board: five numbered tiles 1-5 plus one empty slot marked 0. A move swaps the empty slot with a tile that's directly above, below, left, or right of it.
The board counts as solved only when it reads [[1,2,3],[4,5,0]].
Return the fewest moves needed to reach that solved layout from the given board, or -1 if no sequence of moves can solve it.
Worked Examples
board = [[1,2,3],[4,0,5]]1board = [[1,2,3],[5,4,0]]-1board = [[4,1,2],[5,0,3]]5⚖️Formal Constraints & Bounds
board.length == 2board[i].length == 30 <= board[i][j] <= 5Each value
board[i][j]is unique.
Core Insight
The tile board and the deadend lock are the same shape of problem: serialize the whole state into one hashable value, precompute its neighbor rule once, then BFS.
Real-World Scenario & Production Applications
Physical sliding-tile puzzles (15-puzzle style toys) and any small finite configuration space where the goal is minimum moves between two board layouts.
Subproblems & Recurrence Decomposition3 Phases
A 2D board is awkward to compare and hash. Flattening it row-by-row into a single 6-character string turns 'have I already explored this exact board?' into an instant O(1) set lookup.
start = "".join(str(x) for row in board for x in row)
target = "123450"Step-by-Step Execution Trace Table
Hand-Executed Step Trace (board = [[1,2,3],[4,0,5]])
| Moves | Dequeued State | Blank Index | Candidate Swaps | Target Check | Enqueued Neighbors (Marked on Enqueue) |
|---|---|---|---|---|---|
| 0 | "123405" | 4 | swap with 1, 3, 5 -> "103425", "120435", "123450" | "123450" == target! | Return moves + 1 = 1 ✅ |
board = [[1,2,3],[4,0,5]]1Hand-Executed Step Trace (board = [[1,2,3],[4,0,5]])
| Moves | Dequeued State | Blank Index | Candidate Swaps | Target Check | Enqueued Neighbors (Marked on Enqueue) |
|---|---|---|---|---|---|
| 0 | "123405" | 4 | swap with 1, 3, 5 -> "103425", "120435", "123450" | "123450" == target! | Return moves + 1 = 1 ✅ |
| 1 | start = flatten(board) |
| 2 | target = '123450' |
| 3 | if start == target: |
| 4 | return 0 |
| 5 | queue = deque([(start, 0)]) |
| 6 | visited = {start} |
| 7 | while queue: |
| 8 | state, moves = queue.popleft() |
| 9 | zero = state.index('0') |
| 10 | for nb in neighbors[zero]: |
| 11 | nxt = state with the tiles at zero and nb swapped |
| 12 | if nxt == target: |
| 13 | return moves + 1 |
| 14 | if nxt not in visited: |
| 15 | visited.add(nxt) |
| 16 | queue.append((nxt, moves + 1)) |
| 17 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
The 15-puzzle (or sliding puzzle) looks like a mechanical game, but it is an implicit graph traversal problem. A board containing digits through has exactly possible configurations. Each unique board arrangement is a single node in a 720-node state graph. An edge exists between two nodes if swapping the empty slot (digit ) with an adjacent tile transforms one configuration into the other. Finding the minimum moves to reach the solved target "123450" is simply unweighted BFS on this finite 720-node permutation graph.
🏟️ The Analogy: A Combination Lock with 720 Discrete Faces
Imagine a Rubik's-style puzzle box that can display 720 distinct symbols on its face. Each turn of a dial transitions the box to one of 2, 3, or 4 adjacent symbols. You want to reach the "unlocked" symbol "123450". Because there are only 720 possible configurations in the entire universe of the puzzle, you could write every configuration on an index card. Finding the shortest sequence of turns is just tracing the shortest chain of cards from your starting state to the unlocked card.
🔑 Why It Works
Serializing the board into a string enables hashing in the visited set, turning a confusing 2D matrix swap problem into a clean, deterministic graph traversal.
Mutating 2D grid instead of string serialization: Serializing the 2x3 board as a 6-character string (e.g.
'123450') allows hashing and clean state transitions.Wrong precomputed adjacency mapping: In a 2x3 board flattened to indices 0..5, index 2 can move to indices 1 and 5 (not 3, as index 3 is on the next row). Verify neighbor list for all 6 slots.
Unreachable target state: Some permutations of the 15-puzzle/8-puzzle are mathematically unreachable (odd parity of inversions); BFS must return
-1when queue empties.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Small finite discrete configuration space + minimum moves to a single fixed goal configuration.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: flattening the board into a string turns 'have I seen this board before?' into an O(1) set lookup, and the blank's legal swap partners depend only on grid shape, not board contents.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Comparing 2D board arrays directly instead of serializing to a string, making the visited set unusable.
Recomputing legal neighbor positions per board instead of precomputing them once from the fixed 2x3 shape.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I flatten the board into a 6-character string, then BFS using a precomputed adjacency table of which flattened index the blank ('0') can swap with. Mark-on-enqueue against a visited set of seen strings, and return the move count the instant a swap produces '123450'. Bounded by the 720-state permutation space."
Complexity & Mathematical Proof
O(R!)
Look at the execution steps: the board has R = 6 fixed cells, so there are at most R! = 720 distinct permutations (states). Each state generates at most 4 neighbor swaps (blank has at most 4 legal partners), and building each candidate string takes O(R) time.
O(R!) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Visited set and BFS queue hold at most R! = 720 strings, each of length R = 6.
T(R) = R! · 4 · O(R) = O(R! · R)
Derivation Progression
R! = 720 total distinct board permutations
Finite permutation graph with a fixed, tiny vertex count.
<= 4 transitions per state
The blank's precomputed adjacency list has at most 4 legal swap partners on a 2x3 grid.
O(R) per state creation
Copies and re-joins the flattened board string per candidate swap.
Variable Definitions
Total number of cells on the board (R = 6 for a 2x3 grid)
Memory Architecture & Bounds
O(1) Iterative
O(R!) Visited set and BFS queue of board strings
O(1) Moves count integer
Boundary Best / Worst Cases
if the board starts already solved.
.
visiting all 720 reachable board permutations.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "least number of moves to solve 2x3 board". Board state serialization: flatten the grid into a 6-character string (e.g. "123450"). Each move swaps '0' with an adjacent index.
Total state permutations: . Maximum states is strictly 720.
Unsolvable boards: if BFS exhausts the queue without reaching "123450", return -1.