Solving the 8 puzzle problem using A* (star) algorithm

Share the Post

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.



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

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 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 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 problem 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 8 Puzzle Problem 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 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 8 puzzle problem . 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 StateGoal 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 <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

{

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

}

///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 < _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 SwapWithEmpty(int i0, int i1)

{

int tmp = _state[i1];

_state[i1] = _state[i0];

_state[i0] = 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 < _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”;

}

};

C# Code for State Class

public class State

{

    public int[] Arr

    {

        get;

    }

    public int NumRowsOrCols

    {

        get;

    }

    private int _emptyTileIndex;

    public int GetEmptyTileIndex()

    {

        return _emptyTileIndex;

    }

    public State(int rows_or_cols)

    {

        NumRowsOrCols = rows_or_cols;

        Arr = new int[NumRowsOrCols * NumRowsOrCols];

        for (int i = 0; i < Arr.Length; ++i)

        {

            Arr[i] = i;

        }

        _emptyTileIndex = 0;

    }

    public State(int[] arr)

    {

        NumRowsOrCols = (int)System.Math.Sqrt(arr.Length);

        Arr = new int[NumRowsOrCols * NumRowsOrCols];

        for (int i = 0; i < Arr.Length; ++i)

        {

            Arr[i] = arr[i];

            if (arr[i] == 0) _emptyTileIndex = i;

        }

    }

    public State(State other)

    {

        NumRowsOrCols = other.NumRowsOrCols;

        _emptyTileIndex = other._emptyTileIndex;

        Arr = new int[NumRowsOrCols * NumRowsOrCols];

        other.Arr.CopyTo(Arr, 0);

    }

    public static bool Equals(Tiles.State a, Tiles.State b)

    {

        for (int i = 0; i < a.Arr.Length; i++)

        {

            if (a.Arr[i] != b.Arr[i]) return false;

        }

        return true;

    }

    public int FindEmptyTileIndex()

    {

        for (int i = 0; i < Arr.Length; i++)

            if (Arr[i] == 0) return i;

        return Arr.Length;

    }

    public void Randomize()

    {

        new System.Random(10).Shuffle(Arr);

        for (int i = 0; i < Arr.Length; i++)

        {

            if (Arr[i] == 0) _emptyTileIndex = i;

        }

    }

    public void SwapWithEmpty(int index)

    {

        int tmp = Arr[index];

        Arr[index] = Arr[_emptyTileIndex];

        Arr[_emptyTileIndex] = tmp;

        _emptyTileIndex = index;

    }

};


Neighbours in 8 Puzzle

After State is defined and implemented the next task would be to create the graph of neighbours for the 8 puzzle problem . 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 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 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.

Three randomized states

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.

Design of Neighbours class


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

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.

CreateGraphFor8Puzzle

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

Constructor

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

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.

C++ Code for Neighbours Class

The following section provides the source codes for the class Neighbours. You can copy and paste from this section.

class Neighbours

{

public:

typedef std::map<int, std::vector<int> > IndexNeighbourMap;

IndexNeighbourMap _edges;

Neighbours()

{

CreateGraphFor8Puzzle();

}

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;

}

private:

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

}

};


C# Code for Neighbours

// Neighbours class.

/// this is the class that creates and holds the graph relationship for the 8 puzzle and the empty slot.

/// note that for this simple configuration the 8 puzzle graph is hardcoded.

public class Neighbours

{

    private Dictionary<int, int[]> _edges = new Dictionary<int, int[]>();

    private static Neighbours instance = null;

    public Neighbours()

    {

    }

    public static Neighbours Instance

    {

        get

        {

            if (instance == null)

            {

                instance = new Neighbours();

            }

            return instance;

        }

    }

    public int[] GetNeighbors(int id)

    {

        return _edges[id];

    }

    public void CreateGraphForNPuzzle(int rowsOrCols)

    {

        for(int i = 0; i < rowsOrCols; i++)

        {

            for(int j = 0; j < rowsOrCols; j++)

            {

                int index = i * rowsOrCols + j;

                List<int> li = new List<int>();

                if (i – 1 >= 0) li.Add((i – 1)* rowsOrCols + j);

                if (i + 1 < rowsOrCols) li.Add((i + 1)*rowsOrCols +j);

                if (j – 1 >= 0) li.Add(i*rowsOrCols + j – 1);

                if (j + 1 < rowsOrCols) li.Add(i* rowsOrCols + j + 1);

                _edges[index] = li.ToArray();

            }

        }

    }

};

State Tree for the 8 Puzzle

The state tree is the actual tree that comprises all the valid transitions from one state to another state ultimately reaching to 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 state of the tile for an 8 puzzle.


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 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 an 8 puzzle State as input.

Implementing Node Class in C++

There are a number of 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?

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

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.

C++ Code for Node Class

The following section provides the source codes for the class Node. You can copy and paste from this section.

class Node

{

private:

State _state;

std::shared_ptr<Node> _parent;

int _depth;

public:

Node(const State& state, std::shared_ptr<Node> parent, int depth = 0)

: _state(state)

, _depth(depth)

{

_parent = parent;

}

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”;

}

};

typedef std::shared_ptr<Node> NodePtr;

C# Code for Node

// class Node

/// <summary>

/// A class to hold the State of the 8 puzzle. This is used to create the solution.

/// Node not only holds the state of the 8 puzzle but also the cost associated with the specific state.

/// </summary>

public class Node

{

    public State State

    {

        get;

    }

    public Node Parent

    {

        get;

        set;

    }

    public int Cost

    {

        get;

    }

    public int Depth

    {

        get;

    }

    public Node(State state, int depth = 0, Node parent = null)

    {

        State = state;

        Cost = /*_state.GethammingCost() + */State.GetManhattanCost() + depth;

        Parent = parent;

        Depth = depth;

    }

    // comparison operator based on the cost of the nodes. 

    // This can be used for sorting nodes based on the cost of 

    // the state that it holds.

    public static bool operator >(Node n1, Node n2)

    {

        return n1.Cost > n2.Cost;

    }

    public static bool operator <(Node n1, Node n2)

    {

        return n1.Cost < n2.Cost;

    }

    // print the node into the Debug log.

    public void Print(int lineNum)

    {

        StringWriter str = new StringWriter();

        str.Write(lineNum + ” – “);

        str.Write(“Node { “);

        for (int i = 0; i < State.Arr.Length; ++i)

        {

            str.Write(State.Arr[i]);

        }

        str.Write(” | D: ” + Depth + “, MD: ” + Cost + ” }”);

        //Debug.Log(str.ToString());

    }

};

Solver for 8 Puzzle

In this section, we will concentrate on the Solver framework. The Solver should be able to solve the puzzle based on A* algorithm. However, for the C++ code, we will create a framework that will handle multiple algorithms for solving the puzzle. These include the depth-first search, breadth-first search, the greedy best-first search and finally the A* search.

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

Cost Function

So what is cost function?

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 and cost function

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.

Hamming distance and cost function

Hamming distance is simply the number of misplaced tiles for a specific 8 puzzle state.

The diagram below (referenced from Princeton archive) shows the Hamming and Manhattan cost for a specific tiles configuration.

https://www.cs.princeton.edu/courses/archive/spr18/cos226/assignments/8puzzle/index.html

C++ Implementation of Hamming and Manhattan 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;

}

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;

}


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 openlist. Openlist nodes can be sorted based on either cost or level of depth or by their parents.

Any node that had already been visited will be removed from openlist and added onto a new list called closedlist. For 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 openlist.

PriorityQueue for openlist

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

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 openlist and closedlist 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 openlist elements based on the type of algorithm.

C# Code for Priority Queue

For C# we implement a new class called PriorityQueue that does the sorting based on the cost function.

// A rudimentary PriorityQueue implementation.

// it does not cater for performance or efficiency.

public class PriorityQueue

{

    // The items and priorities.

    List<Node> _nodes = new List<Node>();

    // Return the number of items in the queue.

    public int Count

    {

        get

        {

            return _nodes.Count;

        }

    }

    // Add an item to the queue.

    public void Add(Node n)

    {

        _nodes.Add(n);

    }

    // Get the item with the highest priority (in our case the lowest cost)

    public Node GetAndRemoveTop()

    {

        // Find the hightest priority.

        int best_index = 0;

        int best_priority = _nodes[0].Cost;

        for (int i = 1; i < _nodes.Count; i++)

        {

            if (best_priority > _nodes[i].Cost)

            {

                best_priority = _nodes[i].Cost;

                best_index = i;

            }

        }

        Node n = _nodes[best_index];

        _nodes.RemoveAt(best_index);

        return n;

    }

}

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 to prevent the search from visiting the same nodes again and again.

Design of Solver function

  • 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 ate the openlist, the closedlist, the goal state, a boolean flag to check that stores whether or not the puzzle is solved and the type of algorithm to be used.

Enum for Algorithm Types

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

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.

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

ExpandNode

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

Check out my post on  How to Generate Mazes Using Depth-First Algorithm

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

GetNextNode

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

ASTAR
GREEDY_BEST_FIRST
BREADTH_FIRST
DEPTH_FIRST

C++ Code for Solver

The following section provides the source codes for the class Solver. You can copy and paste from this section.

class Solver

{

public:

enum Type

{

DEPTH_FIRST = 0,

BREADTH_FIRST,

GREEDY_BEST_FIRST,

ASTAR,

};

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);

}

virtual ~Solver()

{

}

inline bool isSolved() const

{

return _solved;

}

inline bool isSolvable() const

{

///TODO

return true;

}

///Returns next node in the search.

//template<class Compare> osg::ref_ptr<Node> GetNextNode(Compare cmp)

NodePtr GetNextNode()

{

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:

//current = _openlist[0];

NodeList::iterator current_itr(_openlist.begin());

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;

}

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().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<NodePtr > 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<Node> closedlist = new List<Node>();

    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[0].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<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>{ 3, 7, 8, 2, 0, 6, 4, 5, 1 });

std::shared_ptr<Node> node;

Solver solver(start, goal, Solver::ASTAR);

if (!solver.isSolvable())

{

std::cout << “Puzzle state is unsolvable..!\n”;

return 0;

}

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;

}

Read Also: What Are C# Delegates And How To Use Them

If you find any errors or if you have any inputs then please do feel free to drop me a comment. You can download the Unity files from the link below. I have not explained the steps of creating the Unity project. If anyone needs me to write a detailed tutorial on the Unity project then please do let me know.

Download all the Script files and Unity Assets from here.

2 thoughts on “Solving the 8 puzzle problem using A* (star) algorithm”

  1. Pingback: What Are C# Delegates And How To Use Them - edusing

  2. Pingback: How to Generate Mazes Using Depth-First Algorithm - edusing

Leave a Reply

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