8puzzle

Solving the 8 puzzle problem using A * and other algorithms

1. Introduction

In this tutorial, we will solve the 8 puzzle problem using a variety of algorithms, from breadth-first search to depth-first search and from greedy best-first search to A* search. We will then implement these algorithms in C++ and C#, test out the results and finally implement the A* search algorithm in Unity as a game. This is going to be a long tutorial. You may skip sections and jump directly into sections that are more relevant to you.

2. 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.
Random Initial
Final Goal
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 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 terms of rigorously defined abstract structures such as graphs, trees, permutations, sets and so on.


For our 8 puzzle problem lets 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 state, we can either slide tile 8 up, slide tile 3 right or slide tile 6 left.

Thus giving three more states. Now 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 block for the puzzle solution and the finally try to join them together to reach the solution.

3.1 State

The first step towards solving the puzzle 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.

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 of each of these indices will represent the actual number 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
  1. Can we implement the state using a 2-dimensional array?
  2. How will you represent the tile indices using a 2-dimensional array?
  3. Can you try out a few examples using a 2-dimensional array?

Implementation of State

To implement State we will need to define the properties and the functions of the object.

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?

//! A typedef of a normal integer array using std::vector for convenience
typedef std::vector<int> 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
{
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.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;
	}

	inline const IntArray& getArray() const
	{
		return _state;
	}

	void setArray(const IntArray& arr)
	{
		_state = arr;;
	}

	///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 findZeroIndex() const
	{
		for (int i = 0; i < _state.size(); ++i)
			if (_state[i] == 0) return i;

		return _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 swap_index(int i0, int i1)
	{
		int tmp = _state[i1];
		_state[i1] = _state[i0];
		_state[i0] = tmp;
	}

	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";
	}

private:
	IntArray _state;
	unsigned int _rows_or_cols;
};

3.2 Neighbours

After State is defined and implemented the next task would be to create the graph of neighbours. We have defined the state in the previous section. We have also implemented State using a one-dimensional array. 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 index 0 we will need to store the neighbours (in other words the indices where the empty tile can move). 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 the value at 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.
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 access the neighbours for any tile index. For example for tile index 6 the neighbours are tile indices 7 and 3.

Implementation of Neighbours

Implement a class called Neighbours that will provide a list or an array of indices which are neighbours to the empty tile index. Give it a try before you look at the code.

  • 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?

class Neighbours
{
public:
	typedef std::map <int, std::vector<int> > IndexNeighbourMap;
	IndexNeighbourMap _edges;
 
	Neighbours()
	{
		CreateGraphFor8Puzzle();
	}
 
	const std::vector& getNeighbors(int id) const
	{
		IndexNeighbourMap::const_iterator itr(_edges.find(id));
		if (itr != _edges.end()) return itr->second;
		static std::vector s;
		return s;
	}
 
private:
	void CreateGraphFor8Puzzle()
	{
		/*
		0 1 2
		3 4 5
		6 7 8
		*/
		_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}));
	}
};

3.3 State Tree

The state tree is the actual tree that comprises all the valid transitions from one state to another state ultimately reaching to the final goad (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 will comprise the state of the tile.

Implementation of State Tree

Design and implement a Node class that represents each element of the tree. You will also need to be able 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 State as input.

class Node
{
public:
	Node(const State& state, std::shared_ptr <Node> parent, int depth = 0)
		: _state(state)
		, _depth(depth)
	{
		_parent = parent;
	}

	inline int getManhattanCost() const
	{
		return _mc;
	}

	inline int getHemmingCost() const
	{
		return _hc;
	}

	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
	{
		/*for (int k = 0; k < _depth; ++k) out << " ";*/
		out << lineNum << " - Node { ";
		for (unsigned int i = 0; i < _state.getArray().size(); ++i)
		{
			out << _state.getArray()[i];
		}
		out << " | D: " << _depth;
		out << " }" << "\n";
	}

private:
	State _state;
	std::shared_ptr <Node>_parent;
	int _depth;
};
Points to ponder
  1. Can we implement the Node in any other way?
  2. Why did I implement Node with only a reference to the parent and not reference to its children?

3.2 Solver

In this section we will concentrate on the Solver framework. We will create a generic class that will handle the solving of the 8 puzzle problem based on a specific algorithm. The Solver class should be able to handle different types of algorithms as inputs (depth-first, breadth-first, astar and greedy-best-first) and should be able to solve the puzzle based on that algorithm. So what is needed for us to be able to create such a class?

Before we delve into the implementation of the class we shall look into some of the data structures that will be needed to tree, visit the next best node and collect nodes for the solution.

Openlist

Openlist is a data structure that holds all the nodes (formed from states) that need to be explored of visited. It is a collection of all generated nodes that were neighbours of expanded nodes. Solver will return the best node to traverse next from the openlist. Openlist nodes can be sorted based on either cost or level of depth or by parent. Any node that had already been visited will be removed from openlist and added onto a new list called closedlist.

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 closedlist helps preventing the search from visiting same nodes again and again.

Implementation of Solver

(1) You will design and implement a Solver class that will use an algorithm  (breadth-first, depth-first, astar or greedy-best-first) search to solve the 8 puzzle problem using the State, Neighbours and Node classes implemented above.

(2) The Solver class will take the initial state, the goal state and the algorithm as inputs.

(3) Since, we did not implement any algorithm yet, so our solver will not work now. However, the basic schema of the functions and program flow should be implemented. Algorithm types should be represented as an enum.

(4) Make sure that the functionality of this Solver class is only to take care of the algorithm and not to be the driver of the program.

(5) The Solver class should minimally have the following functions:

  • IsSolved function that returns true if the puzzle is solved or false otherwise;
  • IsSolvable function that returns true if the puzzle is solvable based on the initial state or false otherwise
  • GetNextNode function that returns the next node to be expanded for the search
  • ExpandNode function to expand the tree by looking into the neighbours for the given node.
class Solver
{
public:
    enum Type
    {
        BREADTH_FIRST = 0,
        DEPTH_FIRST,
        GREEDY_BEST_FIRST,
        ASTAR,
    };

    Solver(const State& start, const State& goal)
        : _goal(goal)
        , _solved(false)
    {
        NodePtr root(new Node(start, 0, 0));
        _openlist.push_back(root);
    }

    virtual ~Solver()
    {
    }

    inline bool isSolved() const
    {
        return _solved;
    }

    inline bool isSolvable() const
    {
        ///TODO
        return true;
    }

    ///Returns next node in the search.
    NodePtr GetNextNode(Type type)
    {
        if (_openlist.empty()) return 0;
        NodePtr current;

        switch (type)
        {
            case ASTAR:
            {
                break;
            }
            case GREEDY_BEST_FIRST:
            {
                break;
            }
            case BREADTH_FIRST:
            {
                break;
            }
            case DEPTH_FIRST:
            {
                break;
            }
        }
        return current;
    }

    // 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().findZeroIndex();
        const IntArray& neighbours = graph.getNeighbors(zero);

        for (int next : neighbours)
        {
            State state = current->getState();
            state.swap_index(zero, next);

            if (!isInArray(state, _closedlist))
            {
                NodePtr n(new Node(state, current, current->getDepth() + 1));
                _openlist.push_back(n);
            }
        }
    }

private:
    typedef std::vector <std::shared_ptr<Node> > NodeList;
    NodeList _openlist;
    NodeList _closedlist;
    const State& _goal;
    bool _solved;
};

3. Solve using Breadth-first search

At this point in time, we have most of the building blocks ready to try our first approach to solve the problem. Although it would be rudimentary, a brute force approach, yet we can reach a solution.

Points to ponder
  1. Discuss the possible ways that we can solve this problem??
  2. What do you mean by brute force approach??
Breadth-first search is an algorithm for traversing or searching tree or graph data structures. It uses the opposite strategy as a depth-first search, which instead explores the highest-depth nodes first before being forced to backtrack and expand shallower nodes. For our case, we will be building the tree at the same time as we are looking for the solution (or goal state). We will start at the root node (i.e. the node that contains the initial state), add the nodes that can be formed by moving the empty tile to its neighbouring tiles, in other words expanding the node, (based on the getNeighbours from Neighbours class), and then traverse those tiles sequentially. Since it is breadth-first we will explore all the nodes at the same level before diving into the next level of nodes. We refer sometimes as visiting siblings before visiting children nodes.

Now let’s look at how we can design and implement a breadth-first search for our 8 puzzle game so that we are able to find the solution given an initial state.

Implementation of breadth-first search for 8 puzzle game

(1) You will design and implement a the breadth-first algorithm into the Solver class.

(2) Think of what changes are required to be made into the Solver class in order to support breadth-first search.



    ///Returns next node in the search.
    NodePtr GetNextNode(Type type)
    {
        if (_openlist.empty()) return 0;
        NodePtr current;

        switch (type)
        {
            case ASTAR:
            {
                break;
            }
            case GREEDY_BEST_FIRST:
            {
                break;
            }
            case BREADTH_FIRST:
            {
                //for breadth-first we simply get the first element from the openlist.
                current = _openlist[0];
                _openlist.erase(_openlist.begin());
                _closedlist.push_back(current);
            }
            case DEPTH_FIRST:
            {
                break;
            }
        }
        return current;
    }

 
Implement the main driver function to test out solving the 8 puzzle problem using breadth-first search.

******* codes for State, Node, Solver *********

// driver function to test breadth-first


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);
    if (!solver.isSolvable())
    {
        std::cout << "Puzzle state is unsolvable..!\n";
        return 0;
    }
    int count = 0;
    while (!solver.isSolved())
    {
        node = solver.GetNextNode(Solver::BREADTH_FIRST);
        solver.ExpandNode(node, g);
        count++;
    }

    // accumulate the nodes for the solution.
    std::vector<std::shared_ptr > 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;
}

4. Solve using A* search

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

4.1 The Heuristics

If you remember, our implementation of Solver class has a function called GetNext Node. This function returns the most optimal node from the openlist. For A* implementation, this function should return the node with least cost.

So what is cost?

In order for a computer to solve an 8 puzzle game, it has to differentiate between a good move and a bad move. Using heuristics we can determine which one is a better move than the other.

So, as long as we sort our openlist based on a heuristic value we can order our search of new nodes in an optimal way.

A simple heuristic function could be the total number of tiles that are out of place. Another could be to take into consideration how far away the out of place tiles are from their correct position (called Manhattan distances).

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 not only for its simplicity but also for 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.

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


Points to ponder

Can you device our how you would implement Manhattan distance for a State?
Let’s add GetManhattanDistance into State class.
inline int getManhattanCost()
{
    int cost = 0;
    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;
}
Then we modify the Node class to be able to store the Manhattan distance for its state and return on demand.
class Node
{
public:
    Node(const State& state, std::shared_ptr<Node> parent, int depth = 0)
        : _state(state)
        , _depth(depth)
    {
        _parent = parent;
        _mc = _state.getManhattanCost();
        _hc = _state.gethammingCost();
    }

******

private:
	State _state;
	std::shared_ptr <Node> _parent;

	int _mc;
};
Now we implement the comparison operator for Node.
class CompareFunctorForAStar
{
public:
    bool operator()(
        const std::shared_ptr< Node>& n1,
        const std::shared_ptr< Node>& n2) const
    {
        return (n1->getManhattanCost() + n1->getDepth() + n1->getHemmingCost()) <
            (n2->getManhattanCost() + n2->getDepth() + n2->getHemmingCost());
    }
};
Finally we implement the ASTAR algorithm logic in the Solver GetNextNode method.
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;
}

5. Complete Code

Attached below is the complete working code for C++ (Github) using the breadth-first, A* and greedy-best-first searches.

#include <vector>
#include <random>
#include <map>
#include <iostream>
#include <cassert>

//! A typedef of a normal integer array using 
//std::vector for convenience
typedef std::vector<int> 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
{
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.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;
    }

    inline const IntArray& getArray() const
    {
        return _state;
    }

    void setArray(const IntArray & arr)
    {
        _state = arr;;
    }

    ///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 findZeroIndex() const
    {
        for (int i = 0; i < (int)_state.size(); ++i)
            if (_state[i] == 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 swap_index(int i0, int i1)
    {
        int tmp = _state[i1];
        _state[i1] = _state[i0];
        _state[i0] = tmp;
    }

    inline int gethammingCost()
    {
        int cost = 0;
        for (unsigned int i = 0; i < _state.size(); ++i)
        {
            if (_state[i] == 0) continue;
            if (_state[i] != i + 1) cost += 1;
        }
        return cost;
    }

    inline int getManhattanCost()
    {
        int cost = 0;
        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;
    }

    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";
    }

private:
    IntArray _state;
    unsigned int _rows_or_cols;
};

class Node
{
public:
    Node(const State& state, std::shared_ptr<Node> parent, int depth = 0)
        : _state(state)
        , _depth(depth)
    {
        _parent = parent;
        _mc = _state.getManhattanCost();
        _hc = _state.gethammingCost();
    }

    inline int getManhattanCost() const
    {
        return _mc;
    }

    inline int getHemmingCost() const
    {
        return _hc;
    }

    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
    {
        /*for (int k = 0; k < _depth; ++k) out << " ";*/
        out << lineNum << " - Node { ";
        for (unsigned int i = 0; i < _state.getArray().size(); ++i)
        {
            out << _state.getArray()[i];
        }
        out << " | D: " << _depth << ", MD: " << _mc;
        out << " }" << "\n";
    }

private:
    State _state;
    std::shared_ptr<Node> _parent;

    int _mc;
    int _hc;
    int _depth;
};

typedef std::shared_ptr<Node> NodePtr;

class Neighbours
{
public:
    typedef std::map<int, std::vector<int> > IndexNeighbourMap;
    IndexNeighbourMap _edges;

    Neighbours()
    {
        CreateGraphFor8Puzzle();
    }

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

private:
    void CreateGraphFor8Puzzle()
    {
        /*
        0 1 2
        3 4 5
        6 7 8
        */
        _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 }));
    }
};

inline int random_range(int min, int max)
{
    //int output = min + (rand() * (int)(max - min) / RAND_MAX);
    //return output;

    static std::random_device rd; // only used once to initialise (seed) engine
    std::mt19937 rng(rd()); // random-number engine used (Mersenne-Twister in this case)
    std::uniform_int_distribution<int> uni(min, max); // guaranteed unbiased

    auto random_integer = uni(rng);
    return random_integer;
}

///Helper function that enables the creation of a random solvable state.
inline void createRandomSolvableState(unsigned int depth,
    const Neighbours& graph, State& state)
{
    for (unsigned int i = 0; i < depth; ++i)
    {
        int zero = state.findZeroIndex();
        const IntArray& neighbours = graph.getNeighbors(zero);
        // get a random neignbour.
        int index = random_range(0, (int)neighbours.size() - 1);
        state.swap_index(zero, neighbours[index]);
        //state.print(std::cout);
    }
}

class CompareFunctorForGreedyBestFirst
{
public:
    bool operator()(
        const std::shared_ptr< Node>& n1,
        const std::shared_ptr< Node>& n2) const
    {
        return (n1->getManhattanCost() + n1->getHemmingCost()) <
            (n2->getManhattanCost() + n2->getHemmingCost());
    }
};

class CompareFunctorForAStar
{
public:
    bool operator()(
        const std::shared_ptr< Node>& n1,
        const std::shared_ptr< Node>& n2) const
    {
        return (n1->getManhattanCost() + n1->getDepth() + n1->getHemmingCost()) <
            (n2->getManhattanCost() + n2->getDepth() + n2->getHemmingCost());
    }
};

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

class Solver
{
public:
    enum Type
    {
        DEPTH_FIRST = 0,
        BREADTH_FIRST,
        GREEDY_BEST_FIRST,
        ASTAR,
    };

    Solver(const State& start, const State& goal)
        : _goal(goal)
        , _solved(false)
    {
        NodePtr root(new Node(start, 0, 0));
        _openlist.push_back(root);
        //_closedlist.push_back(root);
    }

    virtual ~Solver()
    {
    }

    inline bool isSolved() const
    {
        return _solved;
    }

    inline bool isSolvable() const
    {
        ///TODO
        return true;
    }

    ///Returns next node in the search.
    //template osg::ref_ptr GetNextNode(Compare cmp)
    NodePtr GetNextNode(Type type = Type::ASTAR)
    {
        if (_openlist.empty()) return 0;
        NodePtr current;

        switch (type)
        {
        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;
        }
        case GREEDY_BEST_FIRST:
        {
            NodeList::iterator current_itr(
                std::min_element(_openlist.begin(), _openlist.end(),
                    CompareFunctorForGreedyBestFirst())
            );

            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;
        }
        case BREADTH_FIRST:
        {
            current = _openlist[0];
            _openlist.erase(_openlist.begin());
            _closedlist.push_back(current);

            break;
        }
        case DEPTH_FIRST:
            std::cout << "DEPTH_FIRST not implemented\n";
            break;
        }
        return current;
    }

    // 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().findZeroIndex();
        const IntArray& neighbours = graph.getNeighbors(zero);

        for (int next : neighbours)
        {
            State state = current->getState();
            state.swap_index(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<std::shared_ptr<Node> > NodeList;
    NodeList _openlist;
    NodeList _closedlist;
    const State& _goal;
    bool _solved;
};

int main(int argc, char* argv[])
{
    Neighbours g;

    State goal(3, std::vector<int>{ 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<int>{ 3, 7, 8, 2, 0, 6, 4, 5, 1 });

    std::shared_ptr<Node> node;
    Solver solver(start, goal);
    if (!solver.isSolvable())
    {
        std::cout << "Puzzle state is unsolvable..!\n";
        return 0;
    }
    int count = 0;
    while (!solver.isSolved())
    {
        node = solver.GetNextNode(Solver::ASTAR);
        solver.ExpandNode(node, g);
        count++;
    }

    // accumulate the nodes for the solution.
    std::vector<std::shared_ptr<Node> > 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;
}

Unity code and working game is in progress and will be posted soon.

Leave a Reply

Your email address will not be published. Required fields are marked *