Sliding Puzzle

From LeetCode:

A 2x3 puzzle board has tiles numbered 1 to 5 and an empty square represented by 0. A move consists of swapping 0 with an adjacent number. The puzzle is solved when [[1, 2, 3], [4, 5, 0]] is achieved. Given a puzzle configuration, return the least number of moves required to solve it.

Note: If it is impossible for the puzzle to be solved, return -1.

Input:  [[1, 2, 3], [4, 0, 5]]
Output: 1 # Swap 0 and 5.

Input:  [[1, 2, 3], [5, 4, 0]]
Output: -1 # No number of moves can solve the puzzle. 

In the last technical article of this series, we’ll be examining a graph problem that uses breadth-first search (BFS) to find its answer. Thus far, we’ve used a substantial amount of depth-first search (DFS) and we’ve explored what shortest path algorithms can help us achieve. Let’s quickly review the fundamentals of BFS.

Breadth-First Search

BFS, like DFS, begins from a single node and expands to cover the rest of the graph. The difference is that BFS processes sets of nodes at a time. Each of these sets of nodes can be thought of as a frontier that’s “x” bounds away from our source node.

parent = { src: None }
frontier = [src]

def BFS():
    while frontier:
        # Next set of nodes to be processed
        next_frontier = []

        for u in frontier:
            if u == dest:
                return True

            for v in nodes[u].edges:
                if v not in parent:
                    parent[v] = u 
                    next_frontier.append(v)

        frontier = next_frontier

    return False

def reconstruct_path():
    path = [dest]
    while path[-1] is not src:
        path.append(parent[path[-1]])
    return path[::-1]


if BFS():
    return reconstruct_path()

• We maintain a parent map so that when we find our destination node, we can reconstruct the path that led to it.
• We use frontier arrays to the track the nodes at each frontier, but appending newly seen nodes to a single queue works fine too.
• BFS is highly suitable for finding shortest paths on graphs that don’t have edge weights.
• The algorithm runs in O(|V| + |E|) time.

Board States

In the context of this problem, every tiling configuration can be regarded as a distinct node, with the destination node being [[1, 2, 3], [4, 5, 0]].

What makes this problem a little tricky is the fact that we’re dealing with matrices instead of primitives values. We can’t add matrices to a set without the help of some kind of hashing function. Fortunately, given that the board’s size is relatively small (2x3), we can represent board states as strings. We’ll concatenate the top three values with the bottom three ones, such that [[1, 2, 3], [4, 5, 0]] simply becomes "123450".

# board = [[1, 2, 3], [4, 5, 0]]
board = [[str(x) for x in row] for row in board]
board = ''.join(board[0]) + ''.join(board[1])
# board = "123450"

In the event that we’re faced with a variant of this problem that provides us with a larger grid (e.g. 4x4), we can consider hashing the matrix into a tuple of tuples:

board = tuple([tuple(row) for row in board])

Predefining Adjacent Positions

Typically, with problems that involve movement in grids / matrices, it’s a good idea to predefine the related indices. In Trapping Rain Water (2D), we predefined index-based delta values using a SHIFT constant. We’ll do something similar here by hardcoding the valid swap positions for each index on the board:

NEXT = {
    0: (1, 3),
    1: (0, 2, 4),
    2: (1, 5),
    3: (0, 4),
    4: (1, 3, 5),
    5: (2, 4)
}

The rest becomes relatively straightforward. We’ll tweak the vanilla BFS() algorithm we outlined above to something more suitable to our use case:

frontier = [board]
seen = set([board])
moves = 0

while frontier:
    next_frontier = []

    for b in frontier:
        if b == "123450":
            return moves

        i = b.index('0')
        for j in NEXT[i]:
            A = list(b)
            A[i], A[j] = A[j], A[i]
            nb = ''.join(A)
            if nb not in seen:
                seen.add(nb)
                next_frontier.append(nb)

    frontier = next_frontier
    moves += 1

We maintain a moves counter that increments whenever we explore new frontier in order to keep track of the number of moves we’ve made. In addition, note that we use a seen set rather than a parent map since there’s no need for us to trace the sequence of moves that led us to "123450".

Given that our input size is fixed to 2x3, there isn’t really a meaningful way for us to describe the time and space complexity of our solution relative to some parameter n.

With that, we’ve solved the Sliding Puzzle problem 🧩🧩.

Full Solution

NEXT = {
    0: (1, 3),
    1: (0, 2, 4),
    2: (1, 5),
    3: (0, 4),
    4: (1, 3, 5),
    5: (2, 4)
}

def sliding_puzzle(self, board):
    board = [[str(x) for x in row] for row in board]
    board = ''.join(board[0]) + ''.join(board[1])
    frontier = [board]
    seen = set([board])
    moves = 0

    while frontier:
        next_frontier = []

        for b in frontier:
            if b == "123450":
                return moves

            i = b.index('0')
            for j in NEXT[i]:
                A = list(b)
                A[i], A[j] = A[j], A[i]
                nb = ''.join(A)
                if nb not in seen:
                    seen.add(nb)
                    next_frontier.append(nb)

        frontier = next_frontier
        moves += 1

    return -1