How do you solve Sliding Puzzle?

Use BFS starting from the initial board state string. Maintain a queue of (state, moves) and a visited set to avoid revisiting states. For each dequeued state, if it matches the target, return moves. Otherwise, generate all valid next states by swapping zero with its neighbors, enqueue unseen states with moves + 1. If the queue empties without finding the target, return -1.

What pattern does Sliding Puzzle use?

The Pattern: BFS (Shortest Path on Unweighted Graph) The Heuristic: When searching for the minimum number of moves or steps to reach a target configuration in a state space where each move has equal cost, model the problem as a graph and use BFS to guarantee the shortest path is found efficiently.

Sliding Puzzle — BFS

Q: What is the time complexity of Sliding Puzzle?

O(6!). There are 6! = 720 possible board states. BFS explores each state at most once, so the worst-case time is proportional to the number of states.

Problem

Given a 2x3 board representing a sliding puzzle with numbers 1 to 5 and a zero representing the empty space, return the minimum number of moves to reach the target state '123450', or -1 if it is unsolvable.

board.length == 2
board[i].length == 3
0 ≤ board[i][j] ≤ 5
All numbers from 0 to 5 appear exactly once

Example

Input: board = [[1,2,3],[4,0,5]]

Output: 1

Starting from '123405' (flattened), the zero is at index 4. It can swap with neighbors at indices 1, 3, or 5. Swapping with index 5 yields '123450', the target state, in one move. The BFS explores states layer by layer, ensuring the first time the target is found is the shortest path.

Approach

Straightforward Solution

A brute-force approach would try all permutations of the board by swapping tiles arbitrarily, which is factorial in complexity and infeasible.

Core Observation

The puzzle states form a graph where each node is a board configuration and edges represent valid moves by sliding the zero tile. The shortest path to the target state corresponds to the minimum number of moves in this graph.

Path to Optimal

Preview

Recognizing the problem as a shortest path in an unweighted graph suggests BFS as the optimal approach. BFS explores states in order of increasing moves, guaranteeing the first time the target is reached is the minimal move count…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use BFS starting from the initial board state string. Maintain a queue of (state, moves) and a visited set to avoid revisiting states…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(6!)

There are 6! = 720 possible board states. BFS explores each state at most once, so the worst-case time is proportional to the number of states.

Space

O(6!)

The visited set and queue can hold up to all possible states in the worst case, which is factorial in the number of tiles.

Solution

Python

1class Solution:
  def slidingPuzzle(self, board: List[List[int]]) -> int:
      start = "".join(str(num) for row in board for num in row)
      target = "123450"
5
      neighbors = {
          0: [1,3],
          1: [0,2,4],
          2: [1,5],
          3: [0,4],
          4: [1,3,5],
          5: [2,4]
      }
14
      q = deque([(start, 0)])
      seen = {start}
17
      while q:
          state, moves = q.popleft()
20
          if state == target:
              return moves
23
          zero = state.index("0")
25
          for nei in neighbors[zero]:
              state_list = list(state)
              state_list[zero], state_list[nei] = state_list[nei], state_list[zero]
              next_state = "".join(state_list)
30
              if next_state not in seen:
                  seen.add(next_state)
                  q.append((next_state, moves + 1))
34
      return -1

Step-by-Step Solution

1

Encode Board State and Define Zero Tile Neighbors

3start = "".join(str(num) for row in board for num in row)
4target = "123450"
6neighbors = {
7    0: [1,3],
8    1: [0,2,4],
9    2: [1,5],
10    3: [0,4],
11    4: [1,3,5],
12    5: [2,4]
13}

Objective

To represent the board as a string for easy state comparison and to predefine valid zero tile swap positions for efficient neighbor generation.

Key Insight

Flattening the 2D board into a string creates a unique, hashable representation of each state, enabling quick membership checks in the visited set. Predefining neighbors for each zero index avoids costly computations during BFS, allowing constant-time generation of next states by swapping zero with its neighbors.

Interview Quick-Check

Core Logic

Flattening the board into a string creates a canonical representation of states, enabling O(1) membership checks in the visited set.

Common Pitfalls & Bugs

Forgetting to predefine neighbors leads to repeated, expensive computations of valid moves during BFS.

2

Perform BFS to Explore States and Track Moves

To systematically explore all reachable board states using BFS, tracking the number of moves taken to reach each state.

3

Return -1 if Target State is Unreachable

To indicate failure by returning -1 when the BFS exhausts all states without reaching the target.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 21 Critical

if state == target:

Check if the current state matches the target state.

Detecting the target state allows immediate termination with the minimal move count.

Line 16 Critical

seen = {start}

Initialize the visited set with the start state to avoid revisits.

Tracking visited states prevents infinite loops and redundant processing in BFS.

Line 22 Critical

return moves

Return the number of moves taken to reach the target state.

Returning here ensures the shortest path length is reported as BFS guarantees minimal moves.

Full line-by-line criticality + rationale for all 25 lines available on Pro.

Test Your Understanding

Why does BFS guarantee the minimum number of moves to reach the target state in this sliding puzzle?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Sliding Puzzle from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Sliding Puzzle drill

or drill a free problem

1	`class Solution:`
2	`def slidingPuzzle(self, board: List[List[int]]) -> int:`
3	`start = "".join(str(num) for row in board for num in row)`
4	`target = "123450"`
5
6	`neighbors = {`
7	`0: [1,3],`
8	`1: [0,2,4],`
9	`2: [1,5],`
10	`3: [0,4],`
11	`4: [1,3,5],`
12	`5: [2,4]`
13	`}`
14
15	`q = deque([(start, 0)])`
16	`seen = {start}`
17
18	`while q:`
19	`state, moves = q.popleft()`
20
21	`if state == target:`
22	`return moves`
23
24	`zero = state.index("0")`
25
26	`for nei in neighbors[zero]:`
27	`state_list = list(state)`
28	`state_list[zero], state_list[nei] = state_list[nei], state_list[zero]`
29	`next_state = "".join(state_list)`
30
31	`if next_state not in seen:`
32	`seen.add(next_state)`
33	`q.append((next_state, moves + 1))`
34
35	`return -1`

3	`start = "".join(str(num) for row in board for num in row)`
4	`target = "123450"`
6	`neighbors = {`
7	`0: [1,3],`
8	`1: [0,2,4],`
9	`2: [1,5],`
10	`3: [0,4],`
11	`4: [1,3,5],`
12	`5: [2,4]`
13	`}`