⚡Flashcard Drill➔
NeetCode #619LC-773HardGraphs
← Back to All Problems

#619 · #773 · Sliding Puzzle(滑动谜题)

📌 Problem Statement & Constraints

On a 2x3 board there are tiles 1-5 and a blank (0). A move slides a tile into the adjacent blank. Given a board configuration, return the minimum moves to reach [[1,2,3],[4,5,0]], or -1. Constraints: board.length == 2, board[i].length == 3, the board is a permutation of 0..5.

💡 Core Algorithmic Approaches

  1. BFS over board states, encoded as a 6-character string for hashing.
  2. The blank's legal moves depend on its position: index 0 can swap with 1 and 3, index 1 with 0, 2 and 4, and so on.
  3. A precomputed move table makes each expansion O(1).
  4. There are only 6! = 720 states, so the BFS is trivially fast.

💻 Benchmark Python3 Implementation

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        from collections import deque
        start = "".join(str(x) for row in board for x in row)
        target = "123450"
        # adjacent indices for each blank position on a 2x3 board
        moves = {0: (1, 3), 1: (0, 2, 4), 2: (1, 5),
                 3: (0, 4), 4: (1, 3, 5), 5: (2, 4)}
        q = deque([(start, 0)])
        seen = {start}
        while q:
            state, d = q.popleft()
            if state == target:
                return d
            i = state.index("0")           # the blank's position
            for j in moves[i]:
                lst = list(state)
                lst[i], lst[j] = lst[j], lst[i]   # slide a tile in
                nxt = "".join(lst)
                if nxt not in seen:
                    seen.add(nxt)
                    q.append((nxt, d + 1))
        return -1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(6! * 3) = O(1): at most 720 states with at most 3 moves each.
💾 Space Complexity
O(6!) for the visited set.

⚠️ Interview Pitfalls & Follow-ups

  • Getting the adjacency table wrong: the 2x3 layout wraps differently from a 1x6 row.
  • Swapping in place on the string: strings are immutable, so a list round-trip is needed.
  • Using A\* or a heuristic: unnecessary at 720 states; BFS is exact and simple.
  • Forgetting the blank's index lookup: state.index("0") is O(6) and fine here.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems