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

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

Share it

Introduction

In this tutorial, we will solve the 8 puzzle problem using A* (star) search or pathfinding algorithm. We will then implement the game using Unity and solve a random state of the puzzle.



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.

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

Before we can solve the puzzle we will need to model the problem. But what is meant by Modelling the Problem?

In generic terms, modelling a problem is the art of formulating the problem at hand in terms of precisely described, well-understood building blocks and logic to reach a solution. In computer science, proper modelling is the key to applying algorithmic design techniques to any real-world problems. Real-world applications involve real-world problems.

You might be working on a system that simulates air traffic in and around an airport, you might be working on optimizing the dispatch of delivery vans for an e-commerce application, or you might be working to search through patterns in a large image set. To solve such problems you will use some sort of modelling techniques to reduce the problem in terms of rigorously defined abstract structures such as graphs, trees, permutations, sets and so on.

For our 8 puzzle problem let’s see how we can model the problem. Let’s take a random state of the 8 puzzle as given in the diagram below. From this state, we can either slide tile 8 up, slide tile 3 right or slide tile 6 left.

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

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 blocks for the puzzle solution and then finally try to join them together to reach the solution.

The 8 Puzzle 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.

8 Puzzle State

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

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

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

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.


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?

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

    public int GetManhattanCost()
    {
        int cost = 0;
        for (int i = 0; i < Arr.Length; ++i)
        {
            int v = Arr[i];
            if (v == 0) continue;

            // actual index of v should be v-1
            v = v - 1;
            int gx = v % NumRowsOrCols;
            int gy = v / NumRowsOrCols;

            int x = i % NumRowsOrCols;
            int y = i / NumRowsOrCols;

            int mancost = System.Math.Abs(x - gx) + 
                                                     System.Math.Abs(y - gy);
            cost += mancost;
        }
        return cost;
    }
};

Neighbours in 8 Puzzle

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.

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

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 now access the neighbours for any tile index. For example for tile index 6 the neighbours are tile indices 7 and 3.

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?

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 will comprise the state of the tile.

Tree of nodes for an 8 puzzle problem.

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.

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

A Star 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. 

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.

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

// 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;
    }
}
tree

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.

C# Code for Solver Function

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

Check out my post on C# Delegates and Unity

Download all the Script files and Unity Assets from here.


Share it

Leave a Reply

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