Solving 8 puzzle problem using A* star search

This tutorial will solve the 8 puzzle problem using the A* (star) search algorithm. We will approach the solution by first modelling the problem, building the fundamental blocks and finally applying a solver to solve the puzzle.

Part 1 of this tutorial provides the introduction, the background information and the approach towards the solution from the algorithmic point of view.

Part 2 of this tutorial provides an implementation of the algorithm and the solution using C++ for a console program. Read Part 2, “Solving 8 puzzle problem using A* star search in C++”.

Part 3 of this tutorial provides an implementation of the algorithm and the solution using C# for the Unity project. Read Part 2, “8-Puzzle Problem Using A* in C# and Unity“.

Read also

Tutorials on Pathfinding and a WebGL Playground for experimenting pathfinding.

Download the 8 Puzzle Unlimited App from Google Play.

Part 1 – Introduction

Typically A* (Astar) is used in a grid-based pathfinding problem. However, as a general rule, any pathfinding algorithm (A* included) can be used to solve any graph-based problem. For a very detailed understanding of path-finding, I suggest the brilliant tutorial maintained by Amit on Stanford’s site. In this tutorial, I will not go through the theory of A* pathfinding, but rather, I would implement all necessary functions for A* pathfinding to solve the 8 puzzle problem.

The 8 Puzzle Problem

The 8 puzzle problem is a puzzle that was invented and popularised by Noyes Palmer Chapman in the 1870s. The 8-puzzle is a smaller version of the slightly better-known 15-puzzle. It comprises a 3-by-3 grid with 8 square blocks labelled 1 through 8 and a blank square.

The goal is to rearrange the blocks so that they are in order. The blank tile can sometimes be at the start or the end. The diagram above shows one possible initial configuration and the goal. You are permitted to slide blocks horizontally or vertically into the blank square to reach the goal state.

Before we can solve the 8 puzzle problem, we will need to model the problem. But what is meant by Modelling the Problem?

In generic terms, modelling a problem is the art of formulating the problem at hand in terms of precisely described, well-understood building blocks and logic to reach a solution. In computer science, proper modelling is the key to applying algorithmic design techniques to any real-world problem. Real-world applications involve real-world problems.

You might be working on a system that simulates air traffic in and around an airport, you might be working on optimising the dispatch of delivery vans for an e-commerce application, or you might be working to search through patterns in a large image set. To solve such problems, you will use some modelling techniques to reduce the problem in rigorously defined abstract structures such as graphs, trees, permutations, sets, etc.

For our 8 puzzle problems, let’s see how we can model the problem. Let’s take a random state of the 8 puzzle problem as given in the diagram below. We can either slide tile 8 up, slide 3 right, or slide 6 left to create three variant states from this random state.

These three states will produce subsequent more states (3 for the first, 1 for the second and 1 for the third). This continues until we find the goal state.

We can see that we can transform the various possible states of the 8 puzzle problem into a tree data structure.

The 8 Puzzle Solution Search Space

The 8-puzzle is the largest possible N-puzzle that can be solved entirely. It is simple and yet has a significant problem space. There are larger variants to the same problem type, like the 15-puzzle. But those cannot be solved to completion. This complexity makes the N x N extension of the 8-puzzle an NP-hard problem.

8 puzzle has 9! possible tile permutation states. Out of these, every second permutation state is solvable. Hence, there is a total of 9!/2 = 181,440 solvable problem states.

Alexander Reinefeld from the Paderborn Center for Parallel Computing, Germany, has shown that the average length of all optimal solution paths is about 22 moves for any given random configuration. For the 181440 solvable configurations, there is a total of 500880 optimal solutions. This gives an average solution density of 2.76 per problem, with the minimum and maximum number lying at 1 and 64 solutions.

The problem lies in creating the possible search tree and then traversing the most optimal tree branch that will lead from the start state to the end state.

So, how do we find the most optimal branch of the tree? Enter the Heuristic Search!

Heuristic Search

A Heuristic search is a technique to solve a search problem faster than classical methods. In many cases, it finds an approximate solution when classical methods cannot. It is thus a generalized and approximate strategy for problem-solving.

In layman’s terms, it can be thought of as a rule of thumb, or a common-sense knowledge, where the answer isn’t guaranteed to be correct but helps to reach a decision quickly. It is a shortcut that we take to trade-off either the optimality, the completeness, the accuracy, or the precision for speed.

Heuristic searches are often associated with heuristic values.

A heuristic value of a node in the construction graph attempts to capture the importance of that node’s value, for example, the cost or the gain. Heuristic search is a type of informed search that uses such a heuristic value for optimising the search.

At each branching step, the search evaluates the heuristic value and decides which branch to follow. It does so by ranking alternatives.

There are many different types of heuristic search algorithms. One of them is the A* search algorithm.

The A* Search

A* search is a computer search algorithm that is widely used for pathfinding and graph traversal. In our case of the 8 puzzle problem, we will be using it for optimal graph traversal. A* works by keeping track of all visited nodes and ignoring them for further traversal. At the same time, it also keeps track of all the nodes that are yet to be explored and chooses one with the least cost to be further explored.

This simple mechanism allows us to find the most optimal tree branch that will lead us from the start state to the end state.

The Heuristic Value (Cost Function) of an 8 Puzzle State

The heuristic value of an 8 puzzle state is a combination of two values. It is often called the cost function f.

f = h + g

h gives how far the goal node is and g the number of nodes traversed from the start node to the current node. For h, we will use the Manhattan distance, and for g, we will use the depth of the current node.

For our A* search, we will use the sum of Manhattan distance and the current depth of the node as the total cost.

Manhattan distance

The Manhattan distance heuristic is used for its simplicity and ability to estimate the number of moves required to bring a given puzzle state to the solution state. Manhattan distance is computed by the sum of the distances of each tile from where it should belong.

// pseudo code
function manhattan_distance(node, goal) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return dx + dyCode language: JavaScript (javascript)

For example, the Manhattan distance between “213540678” and “123456780” is 9 and between “647850321” and “123456780” is 21.

The diagram below shows the Manhattan cost for a specific tiles configuration.

Software Design for Solving 8 Puzzle Problem

In the following section, I will start creating the building blocks for the puzzle solution and finally try to join them to reach the solution.

State

The first step towards solving the 8 puzzle problem will require a data type to represent the tiles on the puzzle. I will call this the State of the puzzle. A state is a unique combination of tiles.

During our process of solving, we will need to store hundreds of perhaps thousands of tile states. Each combination of tiles in the puzzle will be a unique state. Each unique state of the tiles will represent a Node in the tree data structure.

I will use an integer array to represent a state. The array indices will refer to a tile location, whereas the value in that index will represent the tile number. Look at the diagram below. In this diagram, a unique state of the tile is shown on the left. On the right, an array representation is shown to store the tile information.

Thus, we see that we can represent any state of the 8 puzzle problem by using a one-dimensional array. The indices of the array, which cannot change, represent the fixed location of the tiles. In our case, we have assumed that array index 0 represents the top-left tile, index 1 as top-centre tile, index 2 as top-right tile and so on until index 8 as the bottom-right tile. The value stored in each index will represent the actual number (or picture) on the tile. For example, in the above case, we have index 0 having tile 0 (or the empty tile), index 1 having tile 3 and until index 8 with tile 2.

We can thus see that we can arrive at the goal state by manipulating the values on the array, with the constraint of where the empty tile slides into for each move.

Neighbours

After State is defined, our next task would be to create the graph of neighbours for the 8 puzzle problem.

We have defined the state in the previous section. Now we will define the neighbours based on where the empty tile is. We will do this for each of the 9 tile indices.

So let’s start with tile index 0. For every index, we will need to store the neighbours (in other words, the indices where the empty tile can move) as a collection of indices.

index = 0, {1, 3}
index = 1, {0, 2, 4};
index = 2, {1, 5};
index = 3, {4, 0, 6};
index = 4, {3, 5, 1, 7};
index = 5, {4, 2, 8};
index = 6, {7, 3};
index = 7, {6, 8, 4};
index = 8, {7, 5};

Looking at the above list, we can now access the neighbours for any tile index. For example, for tile index 6, the neighbours are tile indices 7 and 3.

For the first figure below, we have our empty tile in index 0. So for index 0, the neighbours are index 1 and 3. Please note that I am referring to the index of the array and not the actual value of that element in that index of the array. In the first figure below, index 1 is 3, and index 3 is 4. Neighbours, in this case, are index 1 and index 3.

Similarly, for the state represented by the second figure, the empty tile index is 2. Neighbours, in this case, are 1 and 5. For the third state, represented by the third figure, the empty index is 1, and neighbours are 0, 2 and 4. We can thus form a dictionary (or map) of neighbours for each of the 9 indices.

Node (or the State Tree)

The state tree is the actual tree that comprises all the valid transitions from one state to another state, ultimately reaching the final goal (if the solution exists).

In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes – source Wikipedia.

Each tree element we call Node will comprise one specific tile for an 8 puzzle for this problem.

Solver for 8 Puzzle

Finally, we look at the Solver framework. The Solver should be able to solve the puzzle based on the A* algorithm. The solver will be implemented simply as a main console function in C++ and a Coroutine in the Unity C# version. The solver class will construct the tree, visit the next best node and collect nodes for the solution until the solution is finally found.

Read Part 2 of the tutorial “Solving 8 puzzle problem using A* star search in C++.”

Read Part 3 of the tutorial “8-Puzzle Problem Using A* in C# and Unity.“

Read My Other Tutorials

1. Implement a Generic Pathfinder in Unity using C#
2. Create a Jigsaw Puzzle Game in Unity
3. Generic Finite State Machine Using C#
4. Implement Bezier Curve using C# in Unity
5. Create a Jigsaw Tile from an Existing Image
6. Create a Jigsaw Board from an Existing Image
7. Solving 8 puzzle problem using A* star search
8. A Configurable Third-Person Camera in Unity
9. Player Controls With Finite State Machine Using C# in Unity
10. Finite State Machine Using C# Delegates in Unity
11. Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
12. Augmented Reality – Fire Effect using Vuforia and Unity
13. Implementing a Finite State Machine Using C# in Unity
14. Solving 8 puzzle problem using A* star search in C++
15. What Are C# Delegates And How To Use Them
16. How to Generate Mazes Using Depth-First Algorithm

Shamim Akhtar

A  committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. The past is something that you cannot undo. The future is something that you can build.

I enjoy coding, developing games and writing tutorials. Visit my GitHub to see the projects I am working on right now.
Educator | Developer | Mentor