Solving the 8-Puzzle problem using the A* (star) algorithm
The original article was published in Faramira.
Read the Unity and C# version of the tutorial on Faramira
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++”.
Read Also: Implementing Player Controls With Finite State Machine Using C# in Unity
Read Also: A Configurable Third-Person Camera in Unity
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 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 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 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 rigorously defined abstract structures such as graphs, trees, permutations, sets and so on.
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 tile 3 right or slide tile 6 left to create three variant states from this random state.
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.
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 completely solved. It is simple and yet has a large problem space. There are larger variants to the same problem type, like the 15-puzzle. But those cannot be solved to completion. This 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 branch of the tree 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 exactly correct but helps to reach a decision quickly. It is a kind of 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 optimizing 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 its ability to estimate the number of moves required to bring a given puzzle state to the solution state. Manhattan distance is simply 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 + dyFor 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 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 until index 8 with tile 2.
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.
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 the value at 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.
For this problem, each tree element we call Node will comprise one specific tile for an 8-puzzle.
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 console main function in C++ and as 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.
Part 2 — Solving the 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 actually makes up the given state.
- 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 can 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
- an explicit default constructor that takes in the number of rows or columns,
- the constructor that takes in the num of rows or columns and an initial state of the array and
- 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;
}
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);
}
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();
}
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;
}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;
}
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;
}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());
}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;;
}
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";
}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;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}));
}Constructor
The constructor for the Neighbour class just calls the CreateGraphFor8Puzzle to generate the neighbour map and store it.
Neighbours()
{
CreateGraphFor8Puzzle();
}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;
}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 reference its parent (and/or children) for the traversal of the tree.
- The Node constructor 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;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.
Node(const State& state, std::shared_ptr<Node> parent, int depth = 0)
: _state(state)
, _depth(depth)
{
_parent = parent;
}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;
}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";
}
Design of Solver Class
Open list
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 a 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 open list
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;
}
};
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()));NodeList::iterator current_itr(std::min_element(
_openlist.begin(),
_openlist.end(),
CompareFunctorForGreedyBestFirst()));
Closed list
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;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,
BREADTH_FIRST,
GREEDY_BEST_FIRST,
ASTAR,
};Constructor
The constructor for the Solver class simply 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);
}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);
//static int s_lineNum = 1;
//n->print(std::cout, s_lineNum++);
//_closedlist.push_back(n);
}
}
}
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;
}
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;
}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);
}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 });
State start(3, std::vector<int>{ 1, 2, 3, 4, 5, 0, 7, 6, 8});
//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;
}If you find any errors or have any inputs, please do feel free to drop me a comment. You can download the CPP file.
This article first appeared on Faramira.
Educator/Developer/Blogger/Mentor — motivating, guiding and helping young adults into their transition to Industry.
