Page 3 – The Puzzle State

This tutorial is divided into 5 pages.

• Page 1: The first page of the tutorial introduces the 8-Puzzle game and its integration with A* pathfinding in Unity. It covers the problem’s history, its complexity, and heuristic search methods like A*. It also explains the puzzle’s state representation and neighbor construction for pathfinding, providing foundational knowledge for implementing and solving the 8-Puzzle.
• Page 2: The second of the tutorial guides you through creating a new Unity 3D project named “8-Puzzle”. It details setting up the main camera, importing assets, and configuring a tile prefab. You create a puzzle board frame using cubes with wood textures and set up a basic UI with four buttons and two text fields for randomization, image cycling, resetting, and solving the puzzle using A*.
• Page 3: The third covers the implementation of the PuzzleState class for the 8-puzzle game in C#. This class represents a unique puzzle state with an array of tile indices and includes constructors, equality checks, a hash code generator, and methods for finding the empty tile, swapping tiles, and calculating Manhattan cost. Additionally, it details creating neighbor indices for grid cells and generating neighboring puzzle states by moving the empty tile.
• Page 4: In the fourth page, we implement the Path Finder using the three commonly used path finding algorithms, viz., the Dijkstra, the A* and the Gree-best-first search algorithms.
• Page 5: In the fifth page, we apply the A* Path Finder to solve our 8-Puzzle game. We also create the necessary functionality to interactively play the game using the basic UI created in Page 2.

Contact me

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

View the tutorial on YouTube.

• Read also 2D Grid-Based Pathfinding Using C# and Unity
• Read also Graph-Based Pathfinding Using C# in Unity
• Read also Solving 8 puzzle problem using A* star search in C++

The Puzzle State Class

Design of the State class

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

• Implement a class called State that will represent a unique combination of tiles. While implementing the class, do think about the range of functionality and behaviour that this class can and should expose.
• Implement a constructor or multiple constructors.
• Implement a function that will return the index of the empty tile.

Implementing Puzzle State Class in C#

public class PuzzleState : IEquatable<PuzzleState>
Code language: C# (cs)

• PuzzleState is a public class that implements the IEquatable<PuzzleState> interface. This interface allows instances of PuzzleState to be compared for equality.

public int[] Arr { get; private set; } = new int[9];
public int EmptyTileIndex { get; private set; }
Code language: C# (cs)

• Arr: This property represents the current arrangement of the puzzle. It is an array of integers with a length of 9, corresponding to a 3×3 puzzle grid. This property has a private setter, meaning it can only be set within the class.
• EmptyTileIndex: This property represents the index of the empty tile (or space) in the puzzle grid. It also has a private setter.

Constructor

We provide a few constructors for flexibility.

public PuzzleState()
{
    Arr = Enumerable.Range(0, Arr.Length).ToArray();
    EmptyTileIndex = Arr.Length - 1;
}
Code language: C# (cs)

• This is the default constructor of PuzzleState.
• It initializes Arr to contain integers from 0 to 8 (representing the puzzle tiles) using Enumerable.Range. These values correspond to a solved state of the puzzle where the tiles are in order.
• It sets EmptyTileIndex to Arr.Length - 1, which is 8 (the index of the last tile in a 3×3 puzzle).

Copy Constructor

public PuzzleState(PuzzleState other)
{
    other.Arr.CopyTo(Arr, 0);
    EmptyTileIndex = other.EmptyTileIndex;
}
Code language: C# (cs)

• This is a copy constructor for PuzzleState, which creates a copy of another PuzzleState object (other).
• It copies the contents of other.Arr (the puzzle arrangement of other) to Arr of the current object, effectively creating a deep copy of the puzzle state.
• It sets EmptyTileIndex to match the EmptyTileIndex of the other object, ensuring that the empty tile index is correctly maintained in the copied state.

Equals

public bool Equals(PuzzleState other)
{
    return other != null && Arr.SequenceEqual(other.Arr);
}
Code language: C# (cs)

• This method overrides the Equals method from the IEquatable<PuzzleState> interface.
• It checks if other is not null and if the Arr property of the current PuzzleState object (this) is equal to the Arr property of the other PuzzleState object using SequenceEqual.
• SequenceEqual checks if two sequences are equal by comparing their elements.

public override bool Equals(object obj) => Equals(obj as PuzzleState);
Code language: C# (cs)

• This method overrides the Equals method of the object class.
• It casts the obj parameter to PuzzleState using the as operator and then calls the Equals(PuzzleState) method we defined above to perform the equality check.

GetHashCode

public override int GetHashCode()
{
    int hc = Arr.Length;
    foreach (int val in Arr)
    {
        hc = unchecked(hc * 314159 + val);
    }
    return hc;
}
Code language: C# (cs)

• This method overrides the GetHashCode method from the object class.
• It calculates a hash code (hc) based on the content of the Arr array.
• It initializes hc with Arr.Length, which provides a basic starting point for the hash code.
• It then iterates through each element (val) in Arr, updating hc using a hashing algorithm (hc * 314159 + val).
• The unchecked keyword is used to suppress overflow-checking for arithmetic operations. This is safe because overflow in this context will not affect the correctness of the hash code (due to wrapping behavior).
• Finally, it returns the computed hash code hc.

FindEmptyTileIndex

public void FindEmptyTileIndex()
{
    EmptyTileIndex = Array.IndexOf(Arr, Arr.Length - 1);
}
Code language: C# (cs)

• This method is used to find the index of the empty tile (represented by the value Arr.Length - 1) in the Arr array.
• Array.IndexOf(Arr, Arr.Length - 1) is used to search for the first occurrence of the value Arr.Length - 1 (which is equivalent to the last index of the array Arr) within the Arr array.
• The index of the empty tile is then stored in the EmptyTileIndex property of the PuzzleState object.

SwapWithEmpty

The SwapWithEmpty is the function used whenever we slide the empty tile. By sliding the empty tile to an adjacent position, we are swapping the values of the index of the empty tile with the value of the adjacent tile.

public void SwapWithEmpty(int index)
{
    (Arr[index], Arr[EmptyTileIndex]) = (Arr[EmptyTileIndex], Arr[index]);
    EmptyTileIndex = index;
}
Code language: C# (cs)

• This method is used to swap the tile at the specified index with the empty tile.
• It performs the swap using C# 7 tuple syntax combined with array indexing:
  • (Arr[index], Arr[EmptyTileIndex]) = (Arr[EmptyTileIndex], Arr[index]);
    • Here, (Arr[index], Arr[EmptyTileIndex]) represents the tuple containing the values to be swapped.
    • (Arr[EmptyTileIndex], Arr[index]) represents the tuple containing the new values after the swap.
  • This syntax allows for simultaneous assignment of values, effectively swapping the elements at index and EmptyTileIndex.
• After the swap, EmptyTileIndex is updated to index, reflecting the new position of the empty tile after the swap.

Manhattan Cost

    public int GetManhattanCost()
    {
        int rowsOrCols = 3;
        int cost = 0;

        for(int i = 0; i < Arr.Length; i++)
        {
            int v = Arr[i];
            if (v == Arr.Length - 1) continue;

            int gx = v % rowsOrCols;
            int gy = v / rowsOrCols;

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

            int mancost = System.Math.Abs(x - gx) + System.Math.Abs(y - gy);
            cost += mancost;
        }
        return cost;
    }
Code language: C# (cs)

• The GetManhattanCost() method calculates the total Manhattan distance for a given puzzle state represented by the Arr array, assuming it represents a 3×3 grid of tiles. It iterates through each tile’s value (v) in the array, excluding the empty tile (represented by Arr.Length - 1).
• For each tile, it calculates its current position (x, y) in the grid based on its index in the array and computes its goal position (gx, gy) in the solved configuration.
• The Manhattan distance between the current position and the goal position (mancost) is calculated as the sum of the absolute differences in their x-coordinates and y-coordinates (|x - gx| + |y - gy|).
• This distance is then added to the total cost (cost), which represents the overall Manhattan distance for the puzzle state.

The method returns this total cost, which is used in puzzle-solving algorithms like A* search to estimate the distance from the current state to the goal state based on heuristic information.

static private Dictionary<int, List<int>> edges = new Dictionary<int, List<int>>();
Code language: C# (cs)

• This line initializes a static edges dictionary where the key is an integer representing a grid index, and the value is a list of integers representing the indices of neighboring cells.

Create Neighbour Indices

public static void CreateNeighbourIndices(int rowsOrCols = 3)
{
    for(int i = 0; i < rowsOrCols; i++)
    {
        for(int j = 0; j < rowsOrCols; j++)
        {
            int index = i * rowsOrCols + j;
            List<int> neighbourIndices = new List<int>();

            // Add top neighbour
            if (i - 1 >= 0) neighbourIndices.Add((i - 1) * rowsOrCols + j); 
            // Add bottom neighbour
            if (i + 1 < rowsOrCols) neighbourIndices.Add((i + 1) * rowsOrCols + j);
            //  Add left neighbour 
            if (j - 1 >= 0) neighbourIndices.Add(i * rowsOrCols + j - 1);
             // Add right neighbour
            if (j + 1 < rowsOrCols) neighbourIndices.Add(i * rowsOrCols + j + 1);
            // Assign list of neighbor indices to current index in edges dictionary
            edges[index] = neighbourIndices;
        }
    }
}
Code language: C# (cs)

• This method generates and populates the edges dictionary with neighboring indices for each cell in a grid of size rowsOrCols by rowsOrCols.
• It uses nested loops to iterate through each cell (i, j) in the grid.
• For each cell, it calculates the linear index (index) based on its row (i) and column (j) within the grid.
• It creates a new list neighbourIndices to hold the indices of neighboring cells for the current cell.
• It checks and adds neighboring indices to neighbourIndices based on boundary conditions:
  • Adds the index of the cell directly above (i - 1) if it exists (i - 1 >= 0).
  • Adds the index of the cell directly below (i + 1) if it exists (i + 1 < rowsOrCols).
  • Adds the index of the cell to the left (j - 1) if it exists (j - 1 >= 0).
  • Adds the index of the cell to the right (j + 1) if it exists (j + 1 < rowsOrCols).
• Finally, it assigns neighbourIndices to the index in the edges dictionary, mapping each grid index to its list of neighbouring indices.

Get Neighbour Indices

public static List<int> GetNeighbourIndices(int id)
{
    return edges[id];
}
Code language: C# (cs)

• This method is used to retrieve a list of neighboring indices for a given id (index) from the edges dictionary.
• It takes an id as input, which represents a grid index.
• It returns the list of neighboring indices associated with the provided id from the edges dictionary.
• This method is essential for obtaining the neighboring indices of a specific grid cell, which is used for tasks like finding valid moves or exploring neighboring states.

Get Neighbour of Empty Tile

public static List<PuzzleState> GetNeighbourOfEmpty(PuzzleState state)
{
    List<PuzzleState> neighbours = new List<PuzzleState>();
    int empty = state.EmptyTileIndex;

    List<int> neighbourIndices = GetNeighbourIndices(empty);

    foreach (var neighbourIndex in neighbourIndices)
    {
        PuzzleState new_state = new PuzzleState(state);
        new_state.SwapWithEmpty(neighbourIndex);
        neighbours.Add(new_state);
    }

    return neighbours;
}
Code language: C# (cs)

• This method generates a list of neighboring PuzzleState instances by moving the empty tile (represented by EmptyTileIndex in the state) to each valid neighboring position.
• It starts by initializing an empty list neighbours to hold the neighboring puzzle states.
• It retrieves the list of neighboring indices (neighbourIndices) for the empty tile’s current position (empty) using the GetNeighbourIndices method.
• It then iterates over each neighbourIndex in neighbourIndices.
  • For each neighboring index, it creates a new copy (new_state) of the current state using the PuzzleState copy constructor (new PuzzleState(state)).
  • It then swaps the empty tile (EmptyTileIndex) with the tile at neighbourIndex using the SwapWithEmpty method of the new_state.
  • The resulting new_state represents a neighboring puzzle state after making a valid move.
  • The new_state is added to the neighbours list.
• Finally, it returns the list neighbours, which contains all valid neighbouring puzzle states generated by moving the empty tile to its neighbouring positions.

In the next page we will implement the Path Finder using three well known search algorithms, viz., the Djikstra, the A* and the Greedy best first search algorithms.

Shamim Akhtar

A  committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. The past is something that you cannot undo. The future is something that you can build.

I enjoy coding, developing games and writing tutorials. Visit my GitHub to see the projects I am working on right now.
Educator | Developer | Mentor