# Solving 8 puzzle problem using A* star search in C++

In this tutorial, we will solve the 8-puzzle problem using A* star search in C++. This tutorial is Part 2 of the tutorial series on Solving 8 puzzle problem using A* search.

Contact me

Find the GitHub repository of this tutorial at https://github.com/shamim-akhtar/8puzzle.

Part 1 of this tutorial provides the introduction, the background information and the approach towards the solution from the algorithmic point of view. Read Part 1, “Solving an 8-puzzle problem using A* star search.”

Part 2 of this tutorial provides an implementation of the algorithms and the solution using C++ for a console program.

Part 3 of this tutorial implements the solution in C# and solves the 8-puzzle problem using Unity.

## Part 2 – Solving 8 puzzle problem in C++

In this section, we will implement solving the 8-puzzle problem in C++. We will now go ahead and implement the state data structure in C++.

Please ensure that you read Part 1 of this tutorial to get a thorough understanding of the basics.

### Design of the State class

Our objective will be to implement a State class that will represent the 8-puzzle state. This class will hold the index array that makes up the given state.

• Implement a class called State that will represent a unique combination of tiles. While implementing the class do think about the range of functionality and behaviour that this class can and should expose.
• 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.

### 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 the 8-puzzle problem, this value is 3.

#### Constructors

The constructors for the C++ class is given below. We have implemented three constructors. These are

1. an explicit default constructor that takes in the number of rows or columns,
2. the constructor that takes in the num of rows or columns and an initial state of the array and
3. a copy constructor.
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.size(); ++i)
{
_state[i] = 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;
}Code language: C++ (cpp)

#### Operators

The operator for the State class is given below. We have implemented the assignment, equal to and not equal to operators.

///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);
}Code language: C++ (cpp)

#### FindEmptyTileIndex

This function returns the index of the empty tile for any given state of an 8 puzzle.

/// find the index of the empty slot
inline int FindEmptyTileIndex() const
{
for (unsigned int i = 0; i < _state.size(); ++i)
if (_state[i] == 0) return i;
return (int)_state.size();
}Code language: C++ (cpp)

#### 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.

///swap the values of the indices
inline void SwapWithEmpty(int i0, int i1)
{
int tmp = _state[i1];
_state[i1] = _state[i0];
_state[i0] = tmp;
}Code language: C++ (cpp)

#### Manhattan Cost

inline int GetManhattanCost(const State& st)
{
int cost = 0;
const IntArray& state = st.GetArray();
unsigned int rows_or_cols = st.GetNumRowsOrCols();
for (unsigned int i = 0; i < state.size(); ++i)
{
int v = state[i];
if (v == 0) continue;
// actual index of v should be v-1
v = v - 1;
int gx = v % rows_or_cols;
int gy = v / rows_or_cols;
int x = i % rows_or_cols;
int y = i / rows_or_cols;
int mancost = abs(x - gx) + abs(y - gy);
cost += mancost;
int z = 0;
}
return cost;
}Code language: C++ (cpp)

#### Hamming Cost

inline int GetHammingCost(const State& st)
{
int cost = 0;
const IntArray& state = st.GetArray();
for (unsigned int i = 0; i < state.size(); ++i)
{
if (state[i] == 0) continue;
if (state[i] != i + 1) cost += 1;
}
return cost;
}Code language: C++ (cpp)

#### Other Helper Methods

The other helper methods include the Randomize function that randomizes the state of the puzzle.

/// Randomize the 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());
}Code language: C++ (cpp)

The Get and Set methods for getting and setting the index array of the state.

inline const IntArray& GetArray() const
{
return _state;
}
void SetArray(const IntArray& arr)
{
_state = arr;;
}Code language: C++ (cpp)

The print method for printing the state to an output stream. This is useful for debugging and/or showing output for the state.

void print(std::ostream& str, bool flat = false) const
{
for (unsigned int i = 0; i < _rows_or_cols; ++i)
{
for (unsigned int j = 0; j < _rows_or_cols; ++j)
{
unsigned int index = i * _rows_or_cols + j;
if (flat)
{
str << _state[index];
}
else
{
str << _state[index] << " ";
}
}
if (!flat)
{
str << "\n";
}
}
str << "\n";
}Code language: C++ (cpp)

### Design of the Neighbours class

Our objective will be to implement a Neighbours class that will contain the list of array indices for all possible neighbour configurations. We will then implement a class called Neighbours that will provide a list or an array of neighbours to the empty tile index.

• Implement a constructor or multiple constructors
• Implement a function that will create the neighbours for an 8 puzzle game.
• Try to make the class generic so that it can be adaptable for a larger tile project too.
• Any other functions that you can think of?

### Implementing Neighbour Class in C++

For C++ implementation, we store the neighbours in an std:: map. Note that there are multiple ways of implementing this. In the C++ version, I have shown one way, and then in the Unity and C# version, I will show another way of implementation.

typedef std::map<int, std::vector<int> > IndexNeighbourMap;
IndexNeighbourMap _edges;Code language: C++ (cpp)

#### CreateGraphFor8Puzzle

The CreateGraphFor8Puzzle function is called during the construction of the Neighbours class. The map is created and stored in the class.

void CreateGraphFor8Puzzle()
{
_edges.insert(std::make_pair(0, std::vector<int>{1, 3}));
_edges.insert(std::make_pair(1, std::vector<int>{0, 2, 4}));
_edges.insert(std::make_pair(2, std::vector<int>{1, 5}));
_edges.insert(std::make_pair(3, std::vector<int>{4, 0, 6}));
_edges.insert(std::make_pair(4, std::vector<int>{3, 5, 1, 7}));
_edges.insert(std::make_pair(5, std::vector<int>{4, 2, 8}));
_edges.insert(std::make_pair(6, std::vector<int>{7, 3}));
_edges.insert(std::make_pair(7, std::vector<int>{6, 8, 4}));
_edges.insert(std::make_pair(8, std::vector<int>{7, 5}));
}Code language: C++ (cpp)

#### Constructor

The constructor for the Neighbour class just calls the CreateGraphFor8Puzzle to generate the neighbour map and store it.

Neighbours()
{
CreateGraphFor8Puzzle();
}Code language: C++ (cpp)

#### GetNeighbours

The GetNeighbours function returns an array (std::vector) of integer indices to the neighbours. The input for this function is the index to the empty tile.

const std::vector<int>& GetNeighbours(int id) const
{
IndexNeighbourMap::const_iterator itr(_edges.find(id));
if (itr != _edges.end()) return itr->second;
static std::vector<int> s;
return s;
}Code language: C++ (cpp)

### Design of Node class

Design and implement a Node class for an 8 puzzle game that represents each element of the tree. You will also need to traverse the tree, either bottom-up or top-down, to go through the moves that lead to the solution.

• Design and implement a Node class
• The Node class should have a reference to its parent (and/or children) for traversal of the tree.
• The constructor of the Node should be able to take an instance of an 8 puzzle State as input.

### Implementing Node Class in C++

There are several ways of implementing a Node of a tree. In our implementation, the Node object just keeps a pointer to its parent (instead of having a list or an array of pointers to its children). Why is it so? Think about it and write in the comments 🙂

Besides a pointer to its parent, a Node also contains the depth at which the node exists and the state of the 8 puzzle tiles that the Node represents.

State _state;
std::shared_ptr<Node> _parent;
int _depth;Code language: C++ (cpp)

#### Constructor

The constructor for the Node class takes in the current state, the pointer to the parent (note that we are using std::shared_ptr for proper reference counting) and the current depth.

#### Other Helper Functions

All other functions for this Node class are helper functions. These include various Get/Set methods and the print method.

void SetParent(Node* node)
{
_parent.reset(node);
}
void SetParent(std::shared_ptr<Node> node)
{
_parent = node;
}
std::shared_ptr<Node> GetParent()
{
return _parent;
}
const std::shared_ptr<Node> GetParent() const
{
return _parent;
}
const State& GetState() const
{
return _state;
}
int GetDepth() const
{
return _depth;
}Code language: C++ (cpp)
void print(std::ostream& out, int lineNum) const
{
out << lineNum << " - Node { ";
for (unsigned int i = 0; i < _state.GetArray().size(); ++i)
{
out << _state.GetArray()[i];
}
out << " | D: " << _depth;
out << " }" << "\n";
}Code language: C++ (cpp)

### Design of Solver Class

#### Openlist

Openlist is a data structure that holds all the nodes (formed from states) that need to be explored or visited. It is a collection of all generated nodes that were neighbours of expanded nodes.

The solver will return the best node to traverse next from the open list. Openlist nodes can be sorted based on the cost, the level of depth or by their parents.

Any node that had already been visited will be removed from the open list and added onto a new list called closed list. For the A* algorithm, we always get the Node with the lowest cost. Remember that we still did not define how to calculate the cost. But that is not important now. What is important is to develop a data structure that will handle the open list.

#### PriorityQueue for openlist

In computer science, a priority queue is an abstract data type, similar to a regular queue or stack data structure, but where additionally each element has a “priority” (or cost) associated with it. An element with high priority (or lowest cost) is served before an element with low priority (or higher cost) in a priority queue.

#### C++ Code for Priority Queue

For C++, we can directly use std::priority_queue as the data structure. However, to maintain a common framework for all other algorithms to work, I will use std::vector for both open lists and closed lists and maintain different sort operators to facilitate the priority queue implementation.

class CompareFunctorForGreedyBestFirst
{
public:
bool operator()(
const std::shared_ptr<Node>& n1,
const std::shared_ptr<Node>& n2) const
{
const State& state1 = n1->GetState();
int cost1 = GetManhattanCost(state1) + GetHammingCost(state1);
const State& state2 = n2->GetState();
int cost2 = GetManhattanCost(state2) + GetHammingCost(state2);
return cost1 < cost2;
}
};
class CompareFunctorForAStar
{
public:
bool operator()(
const std::shared_ptr<Node>& n1,
const std::shared_ptr<Node>& n2) const
{
const State& state1 = n1->GetState();
int cost1 = GetManhattanCost(state1) + GetHammingCost(state1) + n1->GetDepth();
const State& state2 = n2->GetState();
int cost2 = GetManhattanCost(state2) + GetHammingCost(state2) + n2->GetDepth();
return cost1 < cost2;
}
};Code language: C++ (cpp)

The above two search operators are used to find the minimum value of the open list elements based on the type of algorithm.

NodeList::iterator current_itr(std::min_element(
_openlist.begin(),
_openlist.end(),
CompareFunctorForAStar()));Code language: C++ (cpp)
NodeList::iterator current_itr(std::min_element(
_openlist.begin(),
_openlist.end(),
CompareFunctorForGreedyBestFirst()));Code language: C++ (cpp)

#### Closedlist

The closed list is a collection of all expanded nodes. This means that these nodes have already been visited or explored. Adding already explored nodes in a closed list helps prevent the search from visiting the same nodes repeatedly.

• You will design and implement a Solver function that will use an A* search to solve the 8 puzzle problem using the State, Neighbours and Node classes implemented above.
• The Solver function will take the initial state, the goal state as inputs.

### Implementing Solver Class in C++

The Solver class is the heart of the program. This is the class that will find a solution based on the algorithm that you choose.

#### Variables

The variables for this class are the open list, the closed list, the goal state, a boolean flag to check whether or not the puzzle is solved, and the type of algorithm to be used.

typedef std::vector<NodePtr > NodeList;
NodeList _openlist;
NodeList _closedlist;
const State& _goal;
bool _solved;
Type _type;Code language: C++ (cpp)

#### Enum for Algorithm Types

We keep the type of algorithm to be used for the solver as an enum type.

enum Type
{
DEPTH_FIRST = 0,
GREEDY_BEST_FIRST,
ASTAR,
};Code language: C++ (cpp)

#### Constructor

The constructor for the Solver class takes in an initial state of the puzzle, the goal state of the puzzle, and the type of algorithm to be used.

Solver(const State& start, const State& goal, Type type = Type::ASTAR)
: _goal(goal)
, _solved(false)
, _type(type)
{
NodePtr root(new Node(start, 0, 0));
_openlist.push_back(root);
}Code language: C++ (cpp)

In the constructor, we create a new Node from the start state. This node is then pushed onto the open list.

#### ExpandNode

ExpandNode is the function that expands the tree by looking into the neighbours for a given node.

// expand the graph by looking into the neighbours for the given node.
void ExpandNode(NodePtr current, const Neighbours& graph)
{
if (current->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);
}
}
}Code language: C++ (cpp)

The ExpandNode function will add a neighbour of the current node (remember that each node has a state associated) and add it to the open list if the node is not present in the closed list.

#### GetNextNode

GetNextNode function returns the next node to be searched based on the type of algorithm used.

##### ASTAR
case ASTAR:
{
NodeList::iterator current_itr(std::min_element(
_openlist.begin(),
_openlist.end(),
CompareFunctorForAStar()));
if (current_itr == _openlist.end()) return 0;
//copy the value first to a shared pointer and then erase from the open list.
current = *current_itr;
// now erase from the open list.
_openlist.erase(current_itr);
_closedlist.push_back(current);
break;
}Code language: C++ (cpp)

#### IsInArray

inline bool isInArray(const State& state, const std::vector<std::shared_ptr<Node> >& values)
{
unsigned int i = 0;
for (; i < values.size(); ++i)
{
if (state == values[i]->GetState())
return true;
}
return false;
}Code language: C++ (cpp)

#### IsSolvable

static bool isSolvable(const State& state)
{
int inv_count = 0;
const IntArray arr = state.GetArray();
for (unsigned int i = 0; i < arr.size() - 1; i++)
for (unsigned int j = i + 1; j < arr.size(); j++)
// Value 0 is used for empty space
if (arr[j] && arr[i] && arr[i] > arr[j])
inv_count++;
return (inv_count % 2 == 0);
}Code language: C++ (cpp)

### The main() Driver Program

This is the main driver program for the C++ version. For the 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 it is solved.

int main(int argc, char* argv[])
{
srand(time(0));
Neighbours g;
State goal(3, std::vector<int>{ 1, 2, 3, 4, 5, 6, 7, 8, 0 });
//State start(3, std::vector<int>{ 1, 6, 2, 0, 4, 3, 7, 5, 8 });
State start(3);// , std::vector<int>{ 2, 1, 3, 4, 5, 6, 7, 8, 0 });
start.Randomize();
while (!Solver::isSolvable(start))
{
start.print(std::cout);
std::cout << "Puzzle state is unsolvable..! Creating another configuration.\n";
start.Randomize();
}
std::cout << "Start State:\n";
start.print(std::cout);
std::cout << "Solving puzzle...\n";
std::shared_ptr<Node> node;
Solver solver(start, goal, Solver::ASTAR);
int count = 0;
while (!solver.isSolved())
{
node = solver.GetNextNode();
solver.ExpandNode(node, g);
count++;
}
// accumulate the nodes for the solution.
std::vector<NodePtr > solution;
NodePtr s = node;
do
{
solution.push_back(s);
s = s->GetParent();
} while (s != NULL);
// print the solution.
std::cout << "The puzle can be solved in " << solution.size() - 1 << " steps. Solution below\n";
for (int i = (int)solution.size() - 1; i >= 0; i--)
{
solution[i]->GetState().print(std::cout, false);
}
std::cout << "\n";
return 0;
}Code language: C++ (cpp)

If you find any errors or have any inputs, please do feel free to drop me a comment. You can download the CPP file.

Tutorials on Pathfinding and a WebGL Playground for experimenting pathfinding.

References

https://www.redblobgames.com/pathfinding/a-star/introduction.html

https://en.wikipedia.org/wiki/A*_search_algorithm

## 22 thoughts on “Solving 8 puzzle problem using A* star search in C++”

1. Hi! Could it be that the function isInArray is not defined? I’m trying to compile the code and it seems it’s missing.

Thank you!

1. Hi Carlos

Thanks for pointing that out. It seems that I did not copy the code of this specific function. I have updated the post with the code for isInArray. Please check it out.

Thanks!

2. Hi Shamim Akhtar,
Thiis is really a nice page to understand the both 8-puzzle and A* search alogo.
I see isSolvable() function is missed. I hope you forgot to paste the implementation here. Could you please add the implementation of isSolvable function so that I can run and understand the program behaviour.

1. Hi Rajesh

Thanks, and it’s great that you enjoyed the article. I will update the article with IsSolvable function as well as for GetHammingCost.
In this article, a random state is generated by making N number of random moves from the solved state thus producing a solvable configuration every time. But, yes, to create a more generic random state we will need to have a IsSolvable function.

3. Hello, nice to meet you.

I’m learning how to solve the 8-puzzle by A* algorithm now.

But I don’t know why isSolvable() can determine the puzzle can be solved.
isSolvable() only check the (arr[0],arr[1])(arr[0],arr[2])(arr[1],arr[2]) in array.
Why these three element can determine the puzzle have a solution?

In fact when I input the
State start(3, vector{1, 2, 3, 4, 5, 0, 7, 6, 8});

This program begin infinite loop.

And when I use other website to test this case.
I got the answer is unsolvable puzzle.
https://aaaaagold.github.io/miscellanea/html/mn-puzzle.html

Travis

1. Hi Travis,

Thanks for pointing that out the bug. It should be arr.size() rather that state.GetNumRowsOrCols()
It is amended now. State start(3, vector{1, 2, 3, 4, 5, 0, 7, 6, 8}); is indeed unsolvable.

4. Hi! What version of C++ does your code require? It doesn’t seem to work in c++ 11

1. It should work. May I know what is the error message that you are seeing?

5. Hey! Someone recommended and shared this tutorial and I came to look it over. I’m definitely loving the information. I’m bookmarked and tweeted this to my followers! Terrific blog and amazing style and design.

6. Amazing post. Detailed and quality writing. I am following your other tutorials as wel.

7. Awesome! It’s a remarkable piece of writing, I have got a much clearer idea about it from the tutorial.

1. Hi,
Could you please explain the problem that you are trying to solve in detail? I did not exactly understand it.

In member function ‘NodePtr Solver::GetNextNode()’:
run.cpp:328:29: error: ‘min_element’ was not declared in this scope
CompareFunctorForAStar()));

1. Sorry for the late reply. Did you manage to solve the issue?