Exploring Graph Search Algorithms Using the 8 Puzzle Game

10 min readFeb 28, 2024

After a few months of contemplation, I’ve decided to return to writing articles. With my enrollment in the Master’s Degree program at Universidade da Maia, I’m surrounded by nice projects that can be good articles. Let’s hope I don’t wait another six months before my next piece — LOL.

Now, let’s dive into the topic at hand. Today, we’ll explore how to leverage graphs to conquer a straightforward game. But first, some context: In the realm of Artificial Intelligence, graph search algorithms are essential tools, guiding us through complex networks to solve various challenges efficiently. One such challenge, often used to test these algorithms, is the notorious 8 puzzle game. In this article, we’ll delve into the theory behind different graph search strategies, explore their practical implementation, and analyze their performance metrics — all through the lens of the 8 puzzle game. So, get ready for an insightful journey into the world of problem-solving with graphs!

8 Puzzle Game

Firstly, the 8 puzzle game is a classic puzzle game consisting of a 3x3 grid with eight numbered tiles and one empty space. The goal of the game is to rearrange the tiles by sliding them horizontally or vertically into the empty space until they are ordered sequentially. Players can only move tiles into the empty space, and the challenge lies in finding the optimal sequence of moves to reach the desired arrangement of tiles. Given its inherent structure, the 8 puzzle game serves as an excellent benchmark for implementing graph algorithms, providing a tangible link between gaming scenarios and graph theory applications.

Introduction

A graph search problem arises when we need to explore or navigate through a complex network of connections between different elements, such as nodes and relationships in a graph — and the 8 puzzle game suits here. These algorithms start from a specific node in the graph and traverse relationships until reaching the destination, aiming to discover the shortest paths. These methods are widely applicable in finding optimal routes, logistic planning, and more.

There are two main approaches to graph search: uninformed search and informed search. Uninformed search algorithms operate without any knowledge of the goal state, while informed search algorithms incorporate information about the progress towards the goal.

Uninformed Search Strategies

Breadth-First Search (BFS): Explores nodes level by level, considering all neighboring nodes before moving deeper into the graph. It guarantees finding the shortest path in unweighted graphs.

Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. It may not find the shortest path and can get stuck in infinite loops but is useful for topological ordering in directed acyclic graphs (DAGs).

Informed Search Strategies

A:* Search combines the advantages of BFS and greedy best-first search by considering both the cost to reach the current node and the estimated cost to reach the goal. It is more informed and efficient than greedy best-first search. In other words, it assesses the distance traveled so far in the algorithm and the remaining distance to the goal. Additionally, it employs a priority queue, always selecting the path with the lowest combined cost (traversal cost plus estimated remaining cost). Also, this algorithm uses a heuristic, which is a method used to estimate the cost or distance from a given state to the goal state. For instance, the Manhattan Distance heuristic is commonly employed in the 8 puzzle game to measure the distance between the current state and the goal state. This heuristic calculates the sum of the vertical and horizontal distances between each tile’s current position and its goal position. By providing this estimate, the heuristic guides the search algorithms in making informed decisions about which states to explore next, ultimately leading to more efficient and effective solutions.

Implementation Details

Every piece of code shown here is available on GitHub: https://github.com/ygordefraga/search-algorithms-eight-puzzle.

All applications start with the same data structure, which is a matrix. This matrix is essentially a list of lists that serves as the input for our application, displaying the initial configuration of the puzzle. For example:

[[3, 4, 2],
 [5, 1, 7],
 [6, 0, 8]]

Additionally, we have another matrix representing the goal state that we aim to achieve. In this goal state, the 0 is located in the center, with the first row starting at position (0, 0):

[[1, 2, 3],
 [8, 0, 4],
 [7, 6, 5]]

Before discussing the algorithm, let’s consider how we can make moves in the puzzle. Initially, we need to identify the position of the empty space (represented by 0). Then, we check if moving left, right, down, or up is possible. This logic remains consistent regardless of the algorithm being used (whether it’s BFS, DFS, or A*).

The function responsible for generating possible moves is named makeDescendants. It takes a state variable (which is a matrix representing the current configuration) as input and returns a list of matrices representing the possible moves. For the initial state provided, the only possible moves are left, up, and right because the empty space is located in row 3, column 2.

Based on the provided code and rules for making moves in the 8 puzzle game, we can define the conditions for each type of move for the empty space:

For the following simulation, I will be using this state (because all movements are possible).

[[1, 2, 3],
 [8, 0, 4],
 [7, 6, 5]]

Up: This move is only possible when the row index of the empty space (0) is greater than 0, indicating that the empty space is not in the top row. In our case, it needs to be 1 or 2 since the rows are indexed from 0 to 2. If this condition is met, we subtract 1 from the empty_row variable to represent the upward movement.

[[1, 0, 3],
 [8, 2, 4],
 [7, 6, 5]]

Down: This move is only possible when the row index of the empty space (0) is less than 2, indicating that the empty space is not in the bottom row. In our case, it needs to be 0 or 1 since the rows are indexed from 0 to 2. If this condition is met, we increment the empty_row variable by 1 to represent the downward movement.

[[1, 2, 3],
 [8, 6, 4],
 [7, 0, 5]]

Left: This move is possible when the column index of the empty space (0) is greater than 0, indicating that the empty space is not in the leftmost column. In other words, the empty space has room to move to the left. If this condition is met, we subtract 1 from the empty_col to represent the move to the left.

[[1, 2, 3],
 [0, 8, 4],
 [7, 6, 5]]

Right: This move is possible when the column index of the empty space (0) is less than 2, indicating that the empty space is not in the rightmost column. In our case, it needs to be 0 or 1 since the columns are indexed from 0 to 2. If this condition is met, we increment the empty_col variable by 1 to represent the move to the right.

[[1, 2, 3],
 [8, 4, 0],
 [7, 6, 5]]

By implementing these conditions, we ensure that each move is valid within the constraints of the puzzle grid. The move itself is achieved by creating a copy of the current state and shifting the positions using the empty_row and empty_col variables.

Now that this idea is clear, we explore all options and algorithms. Let’s explore the implementation of each algorithm, remembering that each one of them starts with the :

BFS Implementation

As previously mentioned, BFS works level by level and does not delve as deeply as it could. To accomplish this, it employs a queue data structure. Why a queue? Because in a queue, elements are always appended to the end and popped from the left, adhering to a first-in, first-out order. In the context of BFS, when generating new states from the current state, each of them is added to the queue in sequence. This ensures that the entire level of states is added before moving to deeper levels, maintaining the breadth-first search strategy.

So, in other words. The algorithm will iterate over the queue until we find a result or the queue is empty. There are some important variables, like the queue itself, using the lib deque which provides efficient insertion and deletion operations at both ends, also a set to keep the explored states that we visited, and some metric variables.

A set is a collection of unique elements, and it is a mutable data structure. In this example, we will transform the matrices of the game into tuples and then add them to the set of explored states. Why does that make sense? Because you can think of a tuple as representing rows in a database, and a set as a collection of unique rows where you can keep adding them. Meanwhile, the tuples (rows) will remain immutable.

In the iteration, we initially retrieve the leftmost state in the queue, which is the first one to be added. Immediately afterward, the algorithm checks if the extracted state is the goal state. If it is, the algorithm prints out the depth at which the state was found, the number of generated nodes, and the maximum size that the queue reached. If not, the algorithm continues, adding the current state to the set of explored states.

Next, we invoke the same function that was tested earlier, the one responsible for generating possible moves given a state. If the state is not already in the queue or has not been explored yet, it gets appended to the end of the queue, maintaining the order. The diagram below illustrates why this process adheres to BFS (Breadth-First Search): as we extract all possible moves from a state, each of these new states is added to the queue, and they are processed in the order they were added, mirroring the level-by-level processing characteristic of BFS.

DFS Implementation

It utilizes a stack data structure for exploration, simultaneously keeping track of visited states and performance metrics. Similar to BFS, it generates descendants in a comparable manner. However, the distinguishing factor lies in its stack manipulation. Upon adding new states to the stack, it adopts a right-popping approach during iteration. This implies that the most recently added state will be the first to be removed.

In such scenarios, reaching greater depths becomes considerably easier compared to others. As our algorithm continuously generates children, it’s likely that states 1 and 2 will either take significantly longer to process or might not be processed at all, remaining indefinitely within the stack. Also, it may not find the shortest path due to its nature of exploring deeply before backtracking, which can lead to non-optimal solutions.

A*

This algorithm operates similarly to the ones described below; however, it includes the calculation of the Manhattan heuristic and the sorting of the queue based on the lowest distance, which is a combination of the total distance traveled (depth) and the Manhattan distance. The Manhattan distance is determined by computing the sum of horizontal and vertical distances between each tile’s current position and its target position.

It iterates over two ranges, checking if the value is nonzero, then calls another function with the goal state and value to determine the correct position for that value in the state. Once the correct and current positions are obtained, the differences are calculated and summed to compute the total distance.

After determining the distance, we store it in the queue alongside the depth, and immediately after insertion, we sort the queue by the sum of these two attributes and the id to avoid dropping any value because the distance is the same. This ensures that the next selected item from the queue is closer to reaching the goal, with the Manhattan distance ideally being zero.

Here, the diagram illustrates the order in which the algorithm will calculate it. You can observe that states 2 and 3 have the same value (1+16). However, state 2 will be prioritized.

Results and Performance Metrics

The screenshots below contain the initial state, goal state, and some metrics related to the execution.

BFS guarantees optimal solutions, but it can be memory-intensive. This implementation is considered complete, meaning it will find a solution if one exists. It took approximately 95 seconds to complete, with the state being found at a depth of 23, which is the optimal solution.

On the other hand, DFS offers faster solutions but may not always be optimal. It took approximately 23 seconds to complete, with the state being found at a depth of 63901, which is certainly not the optimal solution.