Solving the 8 puzzle problem using A* (star) algorithm
In this tutorial, we will solve the 8 puzzle problem using A* (star) search or pathfinding algorithm. Besides, the primary algorithm (A*), we will also use breadth-first, depth-first and greedy best-first search algorithms to find a solution for the 8 puzzle problem. We will approach the solution by first modelling the problem, then by building the fundamental blocks and finally applying a solver to solve the puzzle.
Read Also: How to Generate Mazes Using Depth-First Algorithm
This tutorial will provide the solution both from the algorithmic perspective as well as by providing the implementation of the algorithms using C++ for a console program and C# for Unity scripting. Finally, we will implement an 8 puzzle game using Unity and solve a random state of the puzzle by applying the A* algorithm.
Click to Play the Unity Game
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 in his Stanford’s site. In this tutorial I am not going to 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 is a puzzle that was invented and popularized 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 with the blank sometimes at the start or at the end. The diagram above shows one possible initial configuration and the goal. To reach the goal state you are permitted to slide blocks horizontally or vertically into the blank square.
Before we can solve the puzzle 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 problems. 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 optimizing 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 sort of modelling techniques to reduce the problem in terms of 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 as given in the diagram below. From this random state, we can either slide tile 8 up, slide tile 3 right or slide tile 6 left to create three variant states.
Each of these three states will produce subsequent more states (3 for the first, 1 for the second and 1 for the third) and so on. This continues until we find the goal state. Hence, we can see that we can transform the various possible states of the 8 puzzle problem into a tree data structure.
In the following section, I will start creating the building blocks for the puzzle solution and then finally try to join them together to reach the solution.
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 the 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 integer array to represent a state. The indices of the array 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 by using a one-dimensional array we can represent any state of the puzzle. 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 of these indices 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 so on until index 8 with tile 2.
Points to Ponder
Can we implement the state using a 2-dimensional array?How will you represent the tile indices using a 2-dimensional array?Can you try out a few examples using a 2-dimensional array?
We can thus see that by manipulating the values on the array, with the constraint of where the empty tile slides into for each move, we can arrive at the goal state.
Goal state index array
Design of State class
Implement a class called State that will represent a unique combination of tiles. While implementing the class think about the range of functionality and behaviour that this class should expose. Give it a try before you look at the code.Implement a constructor or multiple constructors.Implement a copy constructor (if using C++)Implement a function that will return the index of the empty tile.Implement a function that will randomize the tiles to create a unique configuration of the puzzle.Any other functions that you can think of?
Implementing State Class in C++
The class State comprises two variables (a) the integer array that defines the index array to represent the state and (b) the number of rows or cols. For 8 puzzle problem, this value is 3.
Constructors
The constructors for the C++ class is given below. We have implemented three constructors, viz., the (a) explicit default constructor that takes in the num_rows_or_cols, (b) the constructor that takes in the num_rows_or_cols and an initial state of the array and (c) a copy constructor.
Operators
The operator for the State class is given below. We have implemented the assignment, equal to and not equal to operators.
FindEmptyTileIndex
This function returns the index of the empty tile for any given state of an 8 puzzle.
SwapWithEmpty
This is the function that will be used whenever we slide the empty tile. By sliding the empty tile to an adjacent position we are essentially swapping the values of the index of the empty tile with the value of the adjacent tile.
Other Helper Methods
The other helper methods include the Randomize function that randomizes the state of the puzzle.
The Get and Set methods for getting and setting the index array of the state.
The print method for printing the state to an output stream. This is useful for debugging and/or showing output for the state.
C++ Code for State Class
The following section provides the source codes for the class State. You can copy and paste from this section.
#include
#include
#include
#include
#include
//! A typedef of a normal integer array using std::vector for convenience
typedef std::vector IntArray;
///class State
///A class to hold the state of the puzzle.
///The state is represented by a simple one dimensional array of integers.
///The value of o represents empty slot.
class State
{
private:
IntArray _state;
unsigned int _rows_or_cols;
public:
///
explicit State(unsigned int rows_or_cols)
: _rows_or_cols(rows_or_cols)
{
_state.resize(_rows_or_cols*_rows_or_cols);
for (unsigned int i = 0; i {
_state = i;
}
}
State(unsigned int rows_or_cols, const IntArray& arr)
: _rows_or_cols(rows_or_cols)
{
assert(arr.size() == _rows_or_cols * _rows_or_cols);
_state = arr;
}
///copy constructor
State(const State& other)
{
_rows_or_cols = other._rows_or_cols;
_state = other._state;
}
///assignment operator
State& operator = (const State& other)
{
if (this != &other)
{
_rows_or_cols = other._rows_or_cols;
_state = other._state;
}
return *this;
}
///equal to operator. This will check item by item.
friend bool operator == (const State& a, const State& b)
{
return (a._state == b._state);
}
///not equal to operator. This will check item by item.
friend bool operator != (const State& a, const State& b)
{
return (a._state != b._state);
}
/// find the index of the empty slot
inline int FindEmptyTileIndex() const
{
for (int i = 0; i if (_state == 0) return i;
return (int)_state.size();
}
/// Randomize teh state.
///NOTE: Not all Randomized states are solvable.
///Need to implement a method to find whether a state is solvable or not.
inline void Randomize()
{
std::random_shuffle(_state.begin(), _state.end());
}
///swap the values of the indices
inline void SwapWithEmpty(int i0, int i1)
{
int tmp = _state;
_state = _state;
_state = tmp;
}
inline const IntArray& GetArray() const
{
return _state;
}
void SetArray(const IntArray& arr)
{
_state = arr;;
}
inline unsigned int GetNumRowsOrCols() const
{
return _rows_or_cols;
}
void print(std::ostream& str, bool flat = false) const
{
for (unsigned int i = 0; i {
for (unsigned int j = 0; j {
unsigned int index = i * _rows_or_cols + j;
if (flat)
{
str
GetState() == _goal)
{
_solved = true;
return;
}
int zero = current->GetState().FindEmptyTileIndex();
const IntArray& neighbours = graph.GetNeighbours(zero);
for (int next : neighbours)
{
State state = current->GetState();
state.SwapWithEmpty(zero, next);
if (!isInArray(state, _closedlist))
{
NodePtr n(new Node(state, current, current->GetDepth() + 1));
_openlist.push_back(n);
static int s_lineNum = 1;
n->print(std::cout, s_lineNum++);
//_closedlist.push_back(n);
}
}
}
private:
typedef std::vector NodeList;
NodeList _openlist;
NodeList _closedlist;
const State& _goal;
bool _solved;
Type _type;
};
C# Code for Solver
// The A Star search alogorithm implementation for solving 8 puzzle problem.
// This is implemented as a coroutine for Unity.
public IEnumerator SearchUsingAStar(State start, State goal)
{
PriorityQueue openlist = new PriorityQueue();
List closedlist = new List();
Node root = new Node(start, 0, null);
root.Parent = null;
openlist.Add(root);
closedlist.Add(root);
while (openlist.Count > 0 && !_solved)
{
Node current = openlist.GetAndRemoveTop();
if (State.Equals(current.State, goal))
{
// fil the solution.
Node s = current;
do
{
_solution.Add(s);
s = s.Parent;
} while (s != null);
Debug.Log("Solution found.." + "Total moves needed = " + _solution.Count);
_solved = true;
_solving = false;
_solutionIndex = _solution.Count;
break;
}
int zero = current.State.FindEmptyTileIndex();
int neighbours = Neighbours.Instance.GetNeighbors(zero);
foreach (int next in neighbours)
{
State state = new State(current.State);
//state.SwapWithEmpty(next);
SwapTiles(next, state, false);
if (!IsStateInList(state, closedlist))
{
Node n = new Node(state, current.Depth + 1);
n.Parent = current;
openlist.Add(n);
closedlist.Add(n);
//n.Print(++s_lineNum);
}
}
yield return new WaitForEndOfFrame();
}
_layout.SetState(_solution.State);
}
The main() Driver Program
This is the main driver program for the C++ version. For Unity version please continue reading. The main program starts with a start state, a goal state and the type of algorithm. It then goes into a loop of finding the solution by expanding the tree until the problem is solved.
C++ Code for the Main
int main(int argc, char* argv)
{
Neighbours g;
State goal(3, std::vector{ 1, 2, 3, 4, 5, 6, 7, 8, 0 });
//State start(3, std::vector{ 1, 6, 2, 0, 4, 3, 7, 5, 8 });
State start(3, std::vector{ 3, 7, 8, 2, 0, 6, 4, 5, 1 });
std::shared_ptr node;
Solver solver(start, goal, Solver::ASTAR);
if (!solver.isSolvable())
{
std::cout GetParent();
} while (s != NULL);
// print the solution.
std::cout
Read the full article
