#773

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Sliding Puzzle

Determine the minimum moves to solve a 2x3 sliding puzzle using BFS and state transition dynamic programming techniques efficiently.

array dynamic programming backtracking breadth first search memoization

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.

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).

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        t = [None] * 6

        def gets():
            for i in range(2):
                for j in range(3):
                    t[i * 3 + j] = str(board[i][j])
            return ''.join(t)

        def setb(s):
            for i in range(2):
                for j in range(3):
                    board[i][j] = int(s[i * 3 + j])

        def f():
            res = []
            i, j = next((i, j) for i in range(2) for j in range(3) if board[i][j] == 0)
            for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                x, y = i + a, j + b
                if 0 <= x < 2 and 0 <= y < 3:
                    board[i][j], board[x][y] = board[x][y], board[i][j]
                    res.append(gets())
                    board[i][j], board[x][y] = board[x][y], board[i][j]
            return res

        start = gets()
        end = "123450"
        if start == end:
            return 0
        vis = {start}
        q = deque([(start)])
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                x = q.popleft()
                setb(x)
                for y in f():
                    if y == end:
                        return ans
                    if y not in vis:
                        vis.add(y)
                        q.append(y)
        return -1

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        t = [None] * 6

        def gets():
            for i in range(2):
                for j in range(3):
                    t[i * 3 + j] = str(board[i][j])
            return ''.join(t)

        def setb(s):
            for i in range(2):
                for j in range(3):
                    board[i][j] = int(s[i * 3 + j])

        def f():
            res = []
            i, j = next((i, j) for i in range(2) for j in range(3) if board[i][j] == 0)
            for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
                x, y = i + a, j + b
                if 0 <= x < 2 and 0 <= y < 3:
                    board[i][j], board[x][y] = board[x][y], board[i][j]
                    res.append(gets())
                    board[i][j], board[x][y] = board[x][y], board[i][j]
            return res

        start = gets()
        end = "123450"
        if start == end:
            return 0
        vis = {start}
        q = deque([(start)])
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                x = q.popleft()
                setb(x)
                for y in f():
                    if y == end:
                        return ans
                    if y not in vis:
                        vis.add(y)
                        q.append(y)
        return -1

Continue Practicing

#329 longest increasing path in a matrix #698 partition to k equal sum subsets #691 stickers to spell word