Sliding Puzzle

Sliding Puzzle turns a tiny board game into a graph problem. The trick that makes it click: stop thinking about tiles and start thinking about states. Every arrangement of the board is one node in a graph, and a single move is an edge. Finding the fewest moves is then just shortest path on an unweighted graph — which is exactly what BFS does.

The slow way first

You might try to be clever about which tile to slide next — some greedy rule that pushes tiles toward home. But sliding puzzles are full of traps: the move that looks best can force you to undo three others. Any greedy or depth-first dive can wander forever and still miss the shortest solution.

The question to ask: what does shortest path on a graph need? Each board is a node, each legal move is an edge of weight 1, and we want the closest goal node. The textbook answer for shortest path with unit edges is breadth-first search.

The idea: BFS over board strings

Flatten the 2x3 grid into a 6-character string, like "412503". Strings are easy to hash, so they make perfect graph keys. The blank 0 can only swap with the cells next to it, and on a fixed 2x3 grid those neighbors never change — so we precompute an adjacency list by index: position 0 touches {1, 3}, position 1 touches {0, 2, 4}, and so on.

BFS explores all states one move away, then all states two moves away, and so on. Because it expands in distance order, the first time it pops the goal string is guaranteed to be along a shortest path. A seen set keeps us from revisiting states, which makes the search finite.

Walk through it

Step through the animation. The board starts as "412503" with the blank at index 4. We pop it, find the blank, and swap it with each neighbor index to generate new strings, each at distance 1. Unseen states get marked and queued. Layer by layer the frontier grows until a popped state equals "123450" — the goal — at distance 13.

Pseudocode

start = flatten board into a 6-char string
goal  = "123450"
seen  = {start}
queue = [(start, 0)]
adj   = neighbor indices for each of the 6 positions
while queue is not empty:
    state, dist = pop front of queue
    if state == goal:
        return dist
    z = index of "0" in state
    for n in adj[z]:
        nxt = state with positions z and n swapped
        if nxt not in seen:
            mark nxt seen and queue (nxt, dist + 1)
return -1

The Python solution

def sliding_puzzle(board):
    start = "".join(str(n) for row in board for n in row)
    goal = "123450"
    seen = {start}
    queue = [(start, 0)]
    adj = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
    while queue:
        state, dist = queue.pop(0)
        if state == goal:
            return dist
        z = state.index("0")
        for n in adj[z]:
            nxt = swap(state, z, n)
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, dist + 1))
    return -1

• start flattens the 2x3 grid into one string — our first graph node.
• seen and queue seed the BFS; the queue holds (state, distance) pairs.
• adj is the precomputed adjacency list: which indices the blank can swap with from each position.
• Line 8 pops the front of the queue — popping the front is what makes this breadth-first.
• Line 9 is the goal test; the first pop that matches is the shortest answer.
• z = state.index("0") locates the blank, and lines 11-16 generate every neighbor state and enqueue the unseen ones at dist + 1.

Complexity

There are only 6! = 720 possible boards on a 2x3 grid, so the whole state space is tiny and BFS sweeps it almost instantly. The cost is bounded by the number of reachable arrangements, not by anything exponential in the move count.

When this pattern shows up

Practice