Solving Sliding Puzzles using Python and BFS Search

Sliding puzzles, also known as tile puzzles, have been a popular pastime for generations. These puzzles consist of a set of tiles (each with a fragment of an image, or a number) that are placed on a grid, with one empty space. The goal is to rearrange the tiles to form a specific pattern, such as a picture or a sequence of numbers.

While these puzzles may seem simple at first, they can be quite challenging and require a good deal of logical thinking to solve. Fortunately, with the help of Python, we can easily write a program to solve these puzzles automatically. In this post, I’ll explore solving sliding puzzles using the BFS algorithm. I will also provide sample code and explanations to help you get started with your own sliding puzzle solver implementations.

Modeling the Game

The first step towards solving this game is modeling it. In this sense, “modeling” means telling the computer how to represent a board in a way that it can understand.

Since the board itself is a grid, it intuitively makes sense to represent the board as a matrix, or a lists of lists. However, due to the way Python represents lists (they are lists of pointers), it would cause unnecessary cache misses when accessing elements of the matrix. Instead, using a string makes more sense as it is a contiguous block in memory. In my code, I have modeled the board as a single string. Here’s an example of how my representation scheme works:

Essentially, we map each sub-sequence of numbers to a row in the puzzle. The period represents the empty space in the puzzle. The trickier part here is accessing specific elements of the puzzle and manipulating it. Let’s say we wanted to access the variable which would be at (1,2) in a matrix representation of this board (it would be 6). Since we know the size is 3, we can access element (1 * 3) + 2 = element 5 in the string, which is 6. So the generalized formula for accessing an element with the string representation of the board is (row * size) + column.

The other key part of modeling the game is generating all possible descendants of a board state. This is important when we get to the search algorithms step, because we need to know all possible permutations of any given intermediate board to eventually find the one which leads us to the goal. Descendants, or children, can be generated by swapping the empty tile with any tile vertically or horizontally adjacent to it. For example, given the above board, the children would be "12345.786" and "123467.8", by swapping up and left, respectively.

Modeling/Miscellaneous Code

The first piece of code is a method to get the children of any given board, as long as the side length of the board is given.

def get_children(str, size):
    mat = to_mat(str, size) # convert string representation to matrix
    children = []

    for (i, row) in enumerate(mat): # nested loop to find coordinates of the empty space
        for (j, val) in enumerate(row):
            if val == '.':
                di, dj = i, j
                break

    # horizontal swapping
    if dj == 0:  # swap with right neighbour
        children.append(swap(di, dj, di, dj + 1, mat, size))
    elif dj == len(mat[0]) - 1:
        # swap with left neighbour
        children.append(swap(di, dj, di, dj - 1, mat, size))
    else:
          # swap with both neigubours
        children.append(swap(di, dj, di, dj + 1, mat, size))
        children.append(swap(di, dj, di, dj - 1, mat, size))

    # vertical swapping
    if di == 0:  # swap with below neighbour
        children.append(swap(di, dj, di + 1, dj, mat, size))
    elif di == len(mat[0]) - 1:
        # swap with above
        children.append(swap(di, dj, di - 1, dj, mat, size))
    else:
          # swap with both neighbors
        children.append(swap(di, dj, di + 1, dj, mat, size))
        children.append(swap(di, dj, di - 1, dj, mat, size))
    return children

Essentially, what this code does is checks if the empty space can be shifted, or swapped with a space adjacent to it. If it can, it appends a new, changed board to the children list.

Notice I haven’t defined to_mat and swap yet! Here are the implementations for those two functions:

def to_mat(str, size):
    mat = []
    for i in range(size):
        mat.append([])
        for j in range(size):
            mat[-1].append(str[i * size + j])
    return mat

This function first creates an empty array, and then keeps on appending new rows and filling them with elements from the string representation.

def swap(sourcei, sourcej, desti, destj, mat, size):
    source = mat[sourcei][sourcej]
    dest = mat[desti][destj]
    mat[sourcei][sourcej] = dest
    mat[desti][destj] = source
    toRet =  to_str(mat)
    # swap back
    mat[sourcei][sourcej] = source
    mat[desti][destj] = dest
    return toRet

The swap function takes in the coordinates of the source and destination, along with a matrix representation of the board and its size, as arguments. First source and dest are defined as the elements currently in the source and destination positions. Then, since we already have the indices of the source and destination, we can simply reassign them without needing a temporary variable.

That’s basically all we need on the modeling side of things, so now onto actually solving the puzzle!

BFS (Breadth-First Search)

BFS is one of the simplest search algorithms: an algorithm that can be used to determine a set of steps to get from a pre-determined start and goal state. It uses a queue to keep track of boards it has not yet explored, and a set to keep track of boards it has already tried (so that it doesn’t try exploring the same board state twice). The pseudocode for the algorithm looks like this:

1. Create a queue and insert the initial state
2. Initialize a set of all visited nodes and add the initial state in it, marking it as visited
3. Repeat the following until the queue is empty:
   1. Remove the first vertex from the queue (popping from the left)
   2. Mark that vertex as visited by adding it to the visited set
   3. Insert all of the children of the current node who we have not visited before into the queue.

One feature of BFS search is that it will always find the optimal (shortest) path between the start and destination. On the other hand, DFS (Depth-First Search) a variant of this algorithm which uses a stack instead of a queue, explores each subtree to its maximum depth, meaning that it can get “lost” exploring subtrees which don’t contain the goal.

This is my Python implementation of BFS search for sliding puzzles:

def bfs(start, goal, size): 
    fringe = deque() # need to import at beginning - "from collections import deque"
    visited = set()
    fringe.append((start, 0))
    visited.add(start)
    while len(fringe) > 0: # while the queue is not empty
        v, _l = fringe.popleft() # remove from queue, is current node
        if v == goal: # we are done if true!
            return v, _l
        for child in get_children(v, size): # iterate over every child of current
            if child not in visited:
                fringe.append((child, _l + 1)) # add one to the depth of current
                visited.add(child)

Stepping through this code:

1. First, the variable fringe is instantiated, which is a deque (double-ended queue). Essentially, this means it can be used as a stack or a queue.
2. Next, we instantiate visited which is a set.
3. We then add the inital state to the queue and visited set.
4. Inside of the while loop:
   1. First, pop out the leftmost element in the fringe. Since we are using it as a queue, popping from the left results in the first element inserted being removed (FIFO). If we had used “.pop()” instead, it would behave like a stack, and actually perform depth-first search instead!
   2. Next, we check if the current state is equivalent to the goal, and if it is, we return the goal and the number of steps required to get there (the depth).
   3. After that, we iterate over every child of the current state and check if we have seen it before by looking it up in the visited set. If we haven’t seen this state yet, we add it to the queue and visited set.

Now that we have the search algorithm logic, we just need a main() method to actually run our BFS search logic! Here is an example. Of course, this code can be changed to read from a text file, or command line arguments.

if __name__ == "__main__":
    size = 3
    start = "863.54217"
    goal = "12345678."

    _found, level = bfs(start, goal, size)

And that’s it! Stay tuned for more posts about solving sliding puzzles with different algorithms!