LeetCode 773: Sliding Puzzle

Problem Restatement

We are given a 2 x 3 sliding puzzle board.

The board contains the numbers 1 through 5 and one empty slot represented by 0.

A move consists of swapping 0 with one of its 4-directionally adjacent numbers.

The goal state is:

[[1, 2, 3],
 [4, 5, 0]]

Return the least number of moves needed to reach the goal state.

If it is impossible, return -1.

Input and Output

Example function shape:

def slidingPuzzle(board: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

Output:

1

The empty slot 0 is next to 5.

Swap them:

[[1, 2, 3], [4, 5, 0]]

So the answer is 1.

Example 2:

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

Output:

-1

This starting state cannot reach the solved state.

Example 3:

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

Output:

5

One shortest sequence takes 5 moves.

First Thought: Treat Each Board as a State

Every board arrangement is a state.

A move creates another state by swapping 0 with one adjacent tile.

So this is a graph problem:

Since every move has cost 1, we need the shortest path in an unweighted graph.

That means breadth-first search is the right tool.

Key Insight

BFS explores states by number of moves.

It first visits all states reachable in 0 moves, then all states reachable in 1 move, then all states reachable in 2 moves, and so on.

Therefore, the first time BFS reaches the target state, we have found the minimum number of moves.

Because the board is only 2 x 3, there are at most:

6! = 720

possible arrangements.

So BFS is small and efficient.

State Representation

Instead of storing the board as a nested list, convert it to a string.

For example:

[[1, 2, 3], [4, 0, 5]]

becomes:

"123405"

The target is:

"123450"

This makes states easy to store in a set.

Neighbor Positions

The string has indices:

0 1 2
3 4 5

For each possible position of 0, precompute the indices it can swap with:

neighbors = {
    0: [1, 3],
    1: [0, 2, 4],
    2: [1, 5],
    3: [0, 4],
    4: [1, 3, 5],
    5: [2, 4],
}

For example, if 0 is at index 4, it can move up to index 1, left to index 3, or right to index 5.

Algorithm

1. Convert the board into a string start.
2. Set target = "123450".
3. If start == target, return 0.
4. Run BFS from start.
5. For each state:
   1. Find the index of 0.
   2. Swap 0 with each valid neighbor.
   3. If the new state is unseen, add it to the queue.
6. If BFS reaches target, return the current move count.
7. If BFS ends without reaching target, return -1.

Correctness

Each string state represents exactly one board arrangement.

Each generated neighbor is produced by swapping 0 with one adjacent tile, so every generated edge corresponds to one legal puzzle move.

The BFS starts from the initial board and explores states level by level. All states at level d are exactly the states reachable in d moves.

When the algorithm first reaches "123450", BFS guarantees that no smaller number of moves could have reached it earlier. Therefore, returning that level is correct.

If the queue becomes empty, then every reachable board state has been explored. Since the target was not found, the target is unreachable from the starting board, so returning -1 is correct.

Complexity

There are at most 720 board arrangements.

More generally, for a board with m cells, the state space is O(m!).

Implementation

from collections import deque

class Solution:
    def slidingPuzzle(self, board: list[list[int]]) -> int:
        start = "".join(str(value) for row in board for value in row)
        target = "123450"

        if start == target:
            return 0

        neighbors = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4],
        }

        queue = deque([start])
        visited = {start}
        moves = 0

        while queue:
            for _ in range(len(queue)):
                state = queue.popleft()

                if state == target:
                    return moves

                zero = state.index("0")

                for nxt in neighbors[zero]:
                    chars = list(state)
                    chars[zero], chars[nxt] = chars[nxt], chars[zero]
                    next_state = "".join(chars)

                    if next_state in visited:
                        continue

                    visited.add(next_state)
                    queue.append(next_state)

            moves += 1

        return -1

Code Explanation

We flatten the board:

start = "".join(str(value) for row in board for value in row)

This turns the 2 x 3 board into a six-character string.

The solved board is:

target = "123450"

If the board is already solved:

if start == target:
    return 0

we return immediately.

The neighbors map tells which positions can be swapped with 0.

BFS starts with:

queue = deque([start])
visited = {start}
moves = 0

For each state, find where 0 is:

zero = state.index("0")

Then generate every legal next state by swapping characters:

chars = list(state)
chars[zero], chars[nxt] = chars[nxt], chars[zero]
next_state = "".join(chars)

If this state was already seen, skip it.

Otherwise, add it to BFS:

visited.add(next_state)
queue.append(next_state)

After each BFS level, increment the move count:

moves += 1

If the search finishes without finding the target:

return -1

Testing

def run_tests():
    s = Solution()

    assert s.slidingPuzzle([[1, 2, 3], [4, 0, 5]]) == 1
    assert s.slidingPuzzle([[1, 2, 3], [5, 4, 0]]) == -1
    assert s.slidingPuzzle([[4, 1, 2], [5, 0, 3]]) == 5
    assert s.slidingPuzzle([[1, 2, 3], [4, 5, 0]]) == 0
    assert s.slidingPuzzle([[3, 2, 4], [1, 5, 0]]) == 14

    print("all tests passed")

run_tests()

Test meaning: