In this tutorial, we 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“.
View the tutorial on YouTube
Read also
Tutorials on Pathfinding and a WebGL Playground for experimenting pathfinding.
Play The 8 Puzzle Game
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, introduced and popularised by Noyes Palmer Chapman in the 1870s, is a scaled-down version of the more famous 15-puzzle, featuring a 3-by-3 grid with eight numbered square blocks and one empty square.
The aim of the puzzle is to rearrange the blocks into a specific sequence, typically with the empty square positioned either at the start or end of the sequence. Blocks can be moved horizontally or vertically into the empty square to achieve the desired arrangement.
The A* pathfinding algorithm is commonly used for grid-based pathfinding tasks. However, in general, any pathfinding algorithm, including A*, can be applied to solve graph-based problems. In this tutorial, we will utilise the A* pathfinding algorithm to solve the 8-puzzle.
Before we can solve the 8 puzzle problem, we will need to model the problem. But what do we mean by “Modelling the Problem”?
In general terms, modelling a problem is the process of formulating the problem using precisely defined, well-understood components and logic to reach a solution. In computer science, proper modelling is essential for applying algorithmic design techniques to any real-world problem.
You might be working on a system that simulates air traffic in and around an airport, optimising the dispatch of delivery vans for an e-commerce application, or searching for patterns in a large image dataset. To solve such problems, you will use modelling techniques to represent the problem using rigorously defined abstract structures such as graphs, trees, permutations, sets, and so on.
For our 8 puzzle problem, let’s see how we can model the problem. Let’s take a random state of the 8 puzzle problem as shown in the diagram below. We can either slide tile 5 down, slide 4 right, or slide 2 left to create three variant states from this random state.
These three states will produce subsequent more states (2 for the first, 2 for the second and 2 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 represents the largest possible N-puzzle that can be completely solved. While it is straightforward, it presents a substantial problem space. Larger variants like the 15-puzzle exist but cannot be entirely solved. This complexity classifies the N by N extension of the 8-puzzle as an “N-P” hard problem.
The 8-puzzle encompasses 9 factorial possible tile permutation states. Among these states, every second permutation is solvable. Therefore, there are a total of 9 factorial divided by 2 (9!/2), which is 181,440 solvable problem states.
Alexander Reinefeld from the Paderborn Center for Parallel Computing, Germany, demonstrated that the average length of all optimal solution paths is approximately 22 moves for any random configuration. Across the 181,440 solvable configurations, there are a total of 500,880 optimal solutions, providing an average solution density of 2.76 solutions per problem, with the range of solutions varying from 1 to 64.
The difficulty in solving the puzzle involves building the potential search tree and determining the most efficient path from the initial state to the goal state. To identify the optimal path, we employ Heuristic Search.
Heuristic Search
Heuristic search is a methodused to solvesearch problems more quickly than traditional methods.It often provides an approximate solution when conventional methods cannot, offering a generalised and approximate approach to problem-solving.
In simple terms, a heuristic search can be likened to a rule of thumb or common-sense knowledge. While the answer isn’t guaranteed to be accurate, it aids in swift decision-making, sacrificing optimality, completeness, accuracy, or precision for speed.
Heuristic searches commonly involve heuristic values.
A heuristic value assigned to a node within the construction graph aims to capture the significance of that node’s value, such as cost or gain. Heuristic search, a form of informed search, utilises this heuristic value to optimise the search.
During each branching step, the search evaluates the heuristic value and selects which branch to pursue by ranking alternatives.
There are various types of heuristic search algorithms, with one notable example being the A-star 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 codefunction 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
To solve the 8-puzzle problem, we need a data structure to represent the puzzle’s tiles, which we will refer to as the puzzle’s “state.” Each state represents a unique combination of tiles, and throughout our solving process, we will need to manage potentially hundreds or thousands of these states. Each distinct tile arrangement in the puzzle corresponds to a node within a tree data structure.
To represent these states, we will use an integer array whose indices correspond to specific tile positions. The values stored at these indices represent the tile numbers. In this one-dimensional array representation, each index is fixed and represents a predefined tile location. This precise representation is crucial for our problem-solving process.
For example, index 0 corresponds to the top-left tile, index 1 to the top-center tile, and so on up to index 8 for the bottom-right tile. The value stored at each index indicates the actual tile number present in that location.
For instance, in a given state, as seen here, index 0 holds the value 2, index 1 holds 3, and index 8 holds 7, indicating the tile numbers in those respective positions. Index 4 holds the empty tile.
By manipulating the values in this array representation, while adhering to the constraint of where the empty tile can move with each action, we can efficiently progress towards reaching the goal state of the puzzle. This approach allows us to efficiently track and navigate through the various configurations of the puzzle during the solving process, making our solution approach highly effective.
Neighbours
Our next objective is to construct the graph of neighbours for the 8-puzzle problem. This involves determining possible moves, or neighbour indices, for each of the 9 tile indices.
For example, starting with tile index 0, the neighbouring indices, where the empty tile can move, are indices 1 and 3.
Similarly, for tile index 1, the neighbours are indices 0, 2, and 4, and so on.
We will summarise this relationship in a list of neighbour indices for each tile index.
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 4. So for index 4, the neighbours are index 1, 3, 5 and 8. 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.
With this mapping in place, we can then easily determine the neighbours for any tile index. For instance, for tile index 6, the neighbours are tile indices 7 and 3. It’s important to note that these indices refer to positions within the array representation of the puzzle state, not the actual values stored in those array elements.
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
- Implement a Generic Pathfinder in Unity using C#
- Create a Jigsaw Puzzle Game in Unity
- Generic Finite State Machine Using C#
- Implement Bezier Curve using C# in Unity
- Create a Jigsaw Tile from an Existing Image
- Create a Jigsaw Board from an Existing Image
- Solving 8 puzzle problem using A* star search
- A Configurable Third-Person Camera in Unity
- Player Controls With Finite State Machine Using C# in Unity
- Finite State Machine Using C# Delegates in Unity
- Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
- Augmented Reality – Fire Effect using Vuforia and Unity
- Implementing a Finite State Machine Using C# in Unity
- Solving 8 puzzle problem using A* star search in C++
- What Are C# Delegates And How To Use Them
- 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
