Sliding Puzzle: BFS on Board States

You are given a 2x3 board with tiles numbered 1 through 5, plus one empty space represented by 0. On each move, you can swap the 0 with any adjacent tile (up, down, left, right). Return the minimum number of moves to reach the solved state [[1,2,3],[4,5,0]], or -1 if the puzzle is unsolvable.

This is LeetCode 773: Sliding Puzzle, and it is a classic example of BFS on a state-space graph. The key insight is that every possible board configuration is a node, every valid tile swap is an edge, and "minimum moves" is just "shortest path in an unweighted graph."

Why this problem matters

Sliding puzzles show up in interviews because they test whether you can think beyond traditional graph structures. There is no adjacency list handed to you. Instead, you have to realize that the graph is implicit: each board layout is a state, and each tile swap transitions you to a neighboring state. Once you make that mental leap, the problem reduces to a standard BFS shortest-path search.

This pattern, BFS on an implicit state graph, appears across many problems. Word Ladder transforms words one letter at a time. Open the Lock rotates digits on a combination lock. In all of these, the "graph" is never given explicitly. You generate neighbors on the fly and let BFS find the shortest path.

The 2x3 board also keeps the state space small enough to brute-force with BFS. There are at most 6! = 720 distinct board configurations. BFS can explore all of them in microseconds, making it the ideal approach.

The approach: BFS on board states

The strategy is to flatten the 2x3 board into a string (like "123405") so you can store it in a visited set. Starting from the initial configuration, BFS generates all possible next states by finding where the 0 is, then swapping it with each valid neighbor. Each level of BFS represents one more move.

The neighbor relationships for a 2x3 board are fixed. Position 0 can swap with positions 1 and 3. Position 1 can swap with positions 0, 2, and 4. You can precompute these adjacency lists once and reuse them for every state.

from collections import deque

def sliding_puzzle(board: list[list[int]]) -> int:
    target = "123450"
    start = "".join(str(n) for row in board for n in row)

    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],
    }

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

    while queue:
        state, moves = queue.popleft()

        zero_idx = state.index("0")

        for neighbor in neighbors[zero_idx]:
            chars = list(state)
            chars[zero_idx], chars[neighbor] = chars[neighbor], chars[zero_idx]
            new_state = "".join(chars)

            if new_state == target:
                return moves + 1

            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, moves + 1))

    return -1

Step-by-step walkthrough

Each BFS level adds one move. At level 0, you have the starting board. At level 1, you have every board reachable by swapping the 0 once. The visited set prevents you from revisiting configurations you have already seen, which keeps the search from running in circles.

For the simple example [[1,2,3],[4,0,5]], BFS finds the goal in just one move: swap the 0 with the 5. For harder starting positions like [[4,1,2],[5,0,3]], BFS may need to explore several levels before reaching the target. The worst case for a 2x3 board is 20 moves.

The string representation "123405" is crucial. It gives you a hashable key for the visited set and makes state comparison trivial. Each state takes O(6) space to store, and generating neighbors involves a constant number of character swaps.

from collections import deque

def sliding_puzzle(board: list[list[int]]) -> int:
    target = "123450"
    start = "".join(str(n) for row in board for n in row)

    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],
    }

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

    while queue:
        state, moves = queue.popleft()

        zero_idx = state.index("0")

        for neighbor in neighbors[zero_idx]:
            chars = list(state)
            chars[zero_idx], chars[neighbor] = chars[neighbor], chars[zero_idx]
            new_state = "".join(chars)

            if new_state == target:
                return moves + 1

            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, moves + 1))

    return -1

Complexity analysis

For a 2x3 board, m*n = 6, so there are at most 6! = 720 possible states. BFS visits each state at most once. For each state, finding the zero position and generating neighbors takes O(6) work. The total time is O(720 * 6) = O(4320), which is effectively constant. The space is O(720) for the visited set and queue. Even for larger boards, the factorial growth means BFS is only practical when the board is small.

Edge cases to watch for

• Already solved: If the input board is [[1,2,3],[4,5,0]], return 0 immediately. No moves needed.
• Unsolvable configuration: Not all permutations of tiles are reachable from every starting position. If BFS exhausts the queue without finding the target, return -1.
• Zero in a corner: When 0 is at position 0, 2, 3, or 5, it has only 2 neighbors instead of 3. The precomputed neighbor map handles this automatically.
• Multiple shortest paths: BFS may find the target through different sequences of moves. All shortest paths have the same length, and BFS is guaranteed to return the correct minimum.

The building blocks

This problem combines two core patterns:

BFS shortest path on an implicit graph. You never build an adjacency list. Instead, you generate neighbors on the fly by swapping the 0 with adjacent tiles. The same BFS template works for Open the Lock, Word Ladder, and any "minimum moves" problem.

State serialization. Converting the 2D board to a flat string gives you a hashable, comparable representation of each state. This is a common technique whenever BFS operates on complex data structures like grids, matrices, or multi-dimensional configurations.

From understanding to recall

You have seen how BFS on a state graph solves the sliding puzzle: flatten the board to a string, precompute the neighbor positions, and run BFS until you hit the target. The logic is clear when you read through it. But in an interview, you need to write the neighbor map, the swap logic, and the BFS loop from memory without hesitation.

Spaced repetition bridges that gap. CodeBricks drills the BFS-on-implicit-graph building block and the state-serialization pattern independently. You type each piece from scratch at increasing intervals until the code flows automatically. When a state-space BFS problem appears in your interview, you do not pause to figure out how to represent states or generate neighbors. You just write it.

Related posts

• Open the Lock - Another BFS shortest path on an implicit state graph, where lock combinations are nodes and single-digit turns are edges
• Word Ladder - BFS on word transformations, showing how implicit graphs arise from string mutations
• Number of Islands - Grid BFS/DFS traversal demonstrating neighbor generation on 2D structures