This tutorial will solve the 8-puzzle problem using A* in C# and demonstrate the application in Unity.
This tutorial is Part 2 of my tutorial series on Pathfinding Using C# in Unity. Here I apply the generic pathfinder to solve the 8-puzzle problem.
We will approach the solution by first modelling the problem, building the fundamental blocks and applying our generic pathfinder to solve the puzzle.
Contact me
Find the GitHub repository of this tutorial at https://github.com/shamim-akhtar/tutorial-pathfinding/tree/part-2-8-puzzle.
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++
Download and play the 8 Puzzle game from Google Play.
Our last tutorial, Implement a Generic Pathfinder in Unity using C#, implemented a generic pathfinder in Unity using C#. This tutorial will use that generic pathfinder and apply it to an 8-puzzle game. We will demonstrate how our generic pathfinder not only works on a 2d grid-based system but also solves an 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 to make them in order, with the blank sometimes at the start or the end. The diagram above shows one possible initial configuration and the goal. You are permitted to slide blocks horizontally or vertically into the blank square to reach the goal state.
Before we can solve the 8-puzzle problem, we will need to model the problem. But what is meant by Modelling the Problem?
In generic terms, modelling a problem is the art of formulating the issue at hand in terms of precisely described, well-understood building blocks and logic to reach a solution. Proper modelling is the key to applying algorithmic design techniques to any real-world problem in computer science. 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 optimising 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 modelling techniques to reduce the pain in rigorously defined abstract structures such as graphs, trees, permutations, sets, etc.
Modelling 8-Puzzle
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. We can slide tile 8 up, slide tile 3 right or slide tile 6, and create three variant states from this random state.
Each of these three states will produce subsequent states (3 for first, 1 for second and 1 for third), which continues until we find the goal state.
We can see that we can transform the various possible states of the 8-puzzle problem into a tree data structure.
The 8-Puzzle Solution Search Space
The 8-puzzle is the largest possible N-puzzle that can be solved entirely. It is simple and yet has an ample problem space. There are more significant variants to the same problem type, like the 15-puzzle. But those become increasingly difficult to solve to completion. This increasing difficulty makes the N x N extension of the 8-puzzle an NP-hard problem.
8-puzzle has 9! possible tile permutation states. Out of these, every second permutation state is solvable. Hence, there is a total of 9!/2 = 181,440 solvable problem states.
Alexander Reinefeld from the Paderborn Center for Parallel Computing, Germany, has shown that the average length of all optimal solution paths is about 22 moves for any given random configuration. For the 181440 solvable configurations, there are 500880 optimal solutions, thus providing an average solution density of 2.76 per problem, with the minimum and maximum number lying at 1 and 64.
The problem lies in creating the possible search tree and traversing the most optimal tree branch from the start state to the end state.
So, how do we find the most optimal branch of the tree? Enter the Heuristic Search!
Heuristic Search
A Heuristic search is a technique to solve a search problem faster than classical methods. In many cases, it finds an approximate solution when classical methods cannot. It is thus a generalised and approximate strategy for problem-solving.
In layman’s terms, we can think of it as a rule of thumb, or a common-sense knowledge, where the answer isn’t guaranteed to be correct but helps to reach a decision quickly. We take a shortcut to trade-off either the optimality, the completeness, the accuracy, or the precision for speed.
Heuristic searches are often associated with heuristic values.
A heuristic value of a node in the construction graph attempts to capture the importance of that node’s value, for example, the cost or the gain. Heuristic search is a type of informed search that uses such a heuristic value for optimising the search.
The search evaluates the heuristic value at each branching step and decides which branch to follow. It does so by ranking alternatives.
The A* Search
A* search is a computer search algorithm widely used for pathfinding and graph traversal. In our case of the 8-puzzle problem, we will use it for optimal graph traversal.
The Cost Function of an 8-Puzzle State
The cost value of an 8-puzzle state is a combination of two values. It is often called the cost function f.
f = h + g
where h the heuristic cost gives how far the goal node is, and g is the number of nodes traversed from the start node to the current node. For h, we will use the Manhattan distance, and for g, we will use the depth of the current node.
For our A* search, we will use the sum of the Manhattan distance and the current depth of the node as the total cost.
Manhattan distance
We use the Manhattan distance heuristic for its simplicity and ability to estimate the number of moves required to bring a given puzzle state to the solution state. We compute this distance by the sum of the lengths of each tile from where it should belong.
function manhattan_distance(node, goal) =
dx = abs(node.x - goal.x)
dy = abs(node.y - goal.y)
return dx + dy</pre>
Code language: JavaScript (javascript)For example, the Manhattan distance between “213540678” and “123456780” is 9 and between “647850321” and “123456780” is 21.
The diagram below shows the Manhattan cost for a specific tiles configuration.
8-Puzzle Problem Using A* in C#
This section will implement solving the 8-puzzle problem in C#. We will now go ahead and implement the state data structure in C#.
The Puzzle State
The first step toward solving the 8-puzzle problem will require a data type to represent the tiles on the puzzle. I will call this the State of the puzzle. A state is a unique combination of tiles.
During our process of solving, we will need to store hundreds of perhaps thousands of tile states. Each combination of tiles in the puzzle will be in a unique state. Each state of the tiles will represent a Node in the tree data structure.
I will use an integer array to represent a state. The array indices will refer to a tile location, whereas the value in that index will represent the tile number. Look at the diagram below. This diagram shows a unique state puzzle on the left and the right, the array representation to store the tile information.
Thus, we see that we can represent any state of the 8-puzzle problem by using a one-dimensional array. The indices of the collection, which cannot change, define the fixed location of the tiles. We have assumed that array index 0 represents the top-left tile, index 1 as the top-centre tile, index 2 as the top-right tile and so on until index 8 is the bottom-right tile. The value stored in each index will represent the actual number (or picture) on the tile. For example, in the above case, we have index 0 having tile 0 (or the empty tile), index 1 having tile 3 and until index 8 with tile 2.
We can thus see that we can arrive at the goal state by manipulating the values on the array, with the constraint of where the empty tile slides into for each move.
Design of the State class
Our objective will be to implement a State class that will represent the 8-puzzle state. This class will hold the index array that 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 State Class in C#
The class State comprises two variables (a) the integer array that defines the index array to represent the state and (b) the number of rows or cols. For the 8-puzzle problem, this value is 3.
// The integer array representing the internal state
// of the puzzle.
public int[] Arr
{
get;
private set;
}
// The number of rows or columns of the puzzle.
public int NumRowsOrCols
{
get;
}
// A private variable to store the empty
// tile index.
private int mEmptyTileIndex;
// Get the empty tile index
public int GetEmptyTileIndex()
{
return mEmptyTileIndex;
}
Code language: C# (cs)Constructors
We provide a few constructors for flexibility.
// Constructor.
public PuzzleState(int rows_or_cols)
{
NumRowsOrCols = rows_or_cols;
Arr = new int[NumRowsOrCols * NumRowsOrCols];
for (int i = 0; i < Arr.Length; ++i)
{
Arr[i] = i;
}
mEmptyTileIndex = Arr.Length - 1;
}
// Construct from an integer array of state.
public PuzzleState(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] == (Arr.Length - 1)) mEmptyTileIndex = i;
}
}
// Construct from another state.
public PuzzleState(PuzzleState other)
{
NumRowsOrCols = other.NumRowsOrCols;
mEmptyTileIndex = other.mEmptyTileIndex;
Arr = new int[NumRowsOrCols * NumRowsOrCols];
other.Arr.CopyTo(Arr, 0);
}
Code language: C# (cs)Checking Equality of States
// To check if two states are equal.
public static bool Equals(
PuzzleState a,
PuzzleState b)
{
for (int i = 0; i < a.Arr.Length; i++)
{
if (a.Arr[i] != b.Arr[i]) return false;
}
return true;
}
public bool Equals(PuzzleState other)
{
if (other is null)
return false;
return Equals(this, other);
}
public override bool Equals(object obj) =>
Equals(obj as PuzzleState);
public override int GetHashCode()
{
int hc = Arr.Length;
foreach (int val in Arr)
{
hc = unchecked(hc * 314159 + val);
}
return hc;
}
Code language: C# (cs)FindEmptyTileIndex
This function returns the index of the empty tile for any given state of an 8-puzzle.
public int FindEmptyTileIndex()
{
for (int i = 0; i < Arr.Length; i++)
if (Arr[i] == Arr.Length - 1) return i;
return Arr.Length;
}
Code language: C# (cs)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)
{
int tmp = Arr[index];
Arr[index] = Arr[mEmptyTileIndex];
Arr[mEmptyTileIndex] = tmp;
mEmptyTileIndex = index;
}
Code language: C# (cs)Manhattan Cost
public int GetManhattanCost()
{
int cost = 0;
for (int i = 0; i < Arr.Length; ++i)
{
int v = Arr[i];
if (v == Arr.Length - 1) continue;
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;
}
Code language: C# (cs)Neighbours
After State is defined, our next task would be to create the graph of neighbours for the 8 puzzle problem.
We have defined the state in the previous section. Now we will describe 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};We can now access the neighbours for any tile index by looking at the above list. 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. Note that I am referring to the index of the array and not the actual value of that element in that index of the array. In the first figure below, index 1 is 3, and 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.
For our implementation in C#, we will create a new class called PuzzleMap (just like GameMap). Would you please create a new C# class and name it PuzzleMap?
private 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);
}
mEdges[index] = li;
}
}
}
Code language: C# (cs)Node (or the State Tree)
The state tree is the actual tree that comprises all the valid transitions from one state to another state, ultimately reaching the final goal (if the solution exists).
In computer science, a tree is a widely used abstract data type (ADT)—or data structure implementing this ADT—that simulates a hierarchical tree structure, with a root value and subtrees of children with a parent node, represented as a set of linked nodes – source Wikipedia.
We have already implemented our Node in the previous tutorial. Implement a Generic Pathfinder in Unity using C#. Remember that the Node that we implemented previously is abstract. For our 8-puzzle, we will implement the concrete class named PuzzleNode that will derive from Node<PuzzleState>.
Why?
Because, in this problem, we are creating a tree of the PuzzleState. So each node in this tree must comprise the value PuzzleState.
public class PuzzleNode : Node<PuzzleState>
{
private PuzzleMap mPuzzleMap;
public PuzzleNode(PuzzleState value) : base(value)
{
}
public PuzzleNode(PuzzleMap puzzleMap, PuzzleState value) : base(value)
{
mPuzzleMap = puzzleMap;
}
public override List<Node<PuzzleState>> GetNeighbours()
{
return mPuzzleMap.GetNeighbours(this);
}
}
Code language: C# (cs)We add the method GetNeighbours with the input parameter of PuzzleNode in PuzzleMap.
public List<Node<PuzzleState>> GetNeighbours(PuzzleNode loc)
{
List<Node<PuzzleState>> neighbours = new List<Node<PuzzleState>>();
int zero = loc.Value.GetEmptyTileIndex();
List<int> intArray = GetNeighbors(zero);
for (int i = 0; i < intArray.Count; ++i)
{
PuzzleNode state = new PuzzleNode(this, new PuzzleState(loc.Value));
state.Value.SwapWithEmpty(intArray[i]);
neighbours.Add(state);
}
return neighbours;
}
Code language: C# (cs)We will also add the delegate functions to calculate the heuristic and Node Traversal costs in the PuzzleMap class.
#region Static functions for calculating the Manhattan cost
public static float GetManhattanCost(PuzzleState a, PuzzleState b)
{
// NOTE: We do not use a variable goal state. For 8 puzzle
// the goal state is predefined to be same.
// See PuzzleState for more information.
return a.GetManhattanCost();
}
public static float GetCostBetweenTwoCells(PuzzleState a, PuzzleState b)
{
// The cost of movement from 1 cell to the next is always 1.
return 1.0f;
}
#endregion
Code language: C# (cs)You can see that the above calls are just proxies, and they internally call the PuzzleState method to get the Manhattan cost. The node traversal cost is always 1.
We can now use our generic pathfinder to find the solution for a randomised 8-puzzle. How do we prove it? We can write a console program in C# and demonstrate it.
However, we like Unity so much that we want to show the 8-puzzle problem-solving in Unity.
Unity Project for Solving the 8-Puzzle Problem
So, create a Unity project and start implementing the actual demonstration in Unity.
If you have not already implemented Part 1 of the tutorial, please get the code from my GitHub page https://github.com/shamim-akhtar/tutorial-pathfinding/tree/part-1-pathfinder.
Open the Unity project. Please create a new scene and name it Demo_8puzzlePathFinding. Add an empty game object and call it Tiles.
Tiles
Please create a new folder in Resources/Images and name it Puzzle. Download the following images and put them in the Puzzle folder.
Create 9 sprites and child them to Tiles game object as shown below.
Please keep all the sprites in the same position as shown below.
Please create a sprite for the background. You can use yellow_100.jpg for the background. Set the Transform component as shown below.
Puzzle State Visualization
Please create a new empty game object and name it PuzzleState_Viz. We will use this game object to display our puzzle state by rearranging the tiles.
Create 9 empty game objects with PuzzleState_Viz as a parent, as shown below.
Name these empty game objects as shown above (viz., Loc_00, Loc_01, …, Loc_22. These empty game objects will form the actual locations for the tiles at runtime. Set the positions of these empty game objects (through the Inspector) as:
Loc_00 -> (-1,1,0)
Loc_01 -> (0,1,0)
Loc_02 -> (1,1,9)
Loc_10 -> (-1,0,0)
Loc_11 -> (0,0,0)
Loc_12 -> (1,0,0)
Loc_20 -> (-1,-1,0)
Loc_21 -> (0,-1,0)
Loc_22 -> (1,-1,0)Select the PuzzleState_Viz, go to the Inspector and add a new script component. Name it PuzzleState_Viz.
Double-click the PuzzleState_Viz script component and open it in Visual Studio (or any other favourite IDE). Add the following variables as public.
[Tooltip("Associate the tiles into this array")]
public GameObject[] mTiles;
[Tooltip("Associate the location transforms into this array")]
public Transform[] mTileLocations;
Code language: C# (cs)Associate the tiles, and the location transforms with the above two public arrays in Unity Editor (shown below).
You could also get the location transforms within the script as GetChild, but I prefer to set it through the Editor.
Add a new method that sets the tiles to the respective transforms’ positions based on the indices of the array.
public void SetPuzzleState(PuzzleState state)
{
for (int i = 0; i < state.Arr.Length; ++i)
{
mTiles[state.Arr[i]].transform.position =
mTileLocations[i].position;
}
}
Code language: C# (cs)Add a Coroutine that shows an animated effect of moving a tile from one position to another.
public IEnumerator Coroutine_MoveOverSeconds(
GameObject objectToMove,
Vector3 end,
float seconds)
{
float elapsedTime = 0;
Vector3 startingPos = objectToMove.transform.position;
while (elapsedTime < seconds)
{
objectToMove.transform.position = Vector3.Lerp(
startingPos, end,
(elapsedTime / seconds));
elapsedTime += Time.deltaTime;
yield return new WaitForEndOfFrame();
}
objectToMove.transform.position = end;
}
Code language: C# (cs)Amend the Start method as follows:
void Start()
{
// Create a new PuzzleState and set it.
PuzzleState state = new PuzzleState(3);
SetPuzzleState(state);
}
Code language: C# (cs)Create a method that sets a puzzle’s state.
public void SetPuzzleState(PuzzleState state, float duration)
{
for (int i = 0; i < state.Arr.Length; ++i)
{
StartCoroutine(Coroutine_MoveOverSeconds(
mTiles[state.Arr[i]],
mTileLocations[i].position,
duration));
}
}
Code language: C# (cs)Puzzle Solver Visualization
In this section, we will create our puzzle solver visualisation. Create an empty game object and name it PuzzleSolver_Viz. Select this PuzzleSolver_Viz game object and from the Inspector, add a new script component. Name the script as PuzzleSolver_Viz.
Double-click and open the PuzzleSolver_Viz script in your favourite IDE.
Add the following variables.
public PuzzleState_Viz mPuzzleStateViz;
private PuzzleNode mCurrentState;
private PuzzleNode mGoalState;
private AStarPathFinder<PuzzleState> mAstarSolver =
new AStarPathFinder<PuzzleState>();
private PuzzleMap mPuzzle = new PuzzleMap(3);
Code language: C# (cs)The highlighted lines 6-7 above show that we have created an AStarPathFinder class with PuzzleNode. You can try with the other two pathfinders as well, viz., the DijkstraPathFinder or the GreedyPathFinder.
Create a Coroutine to randomise the puzzle.
IEnumerator Coroutine_Randomize(int depth)
{
int i = 0;
while (i < depth)
{
List<Node<PuzzleState>> neighbours =
mPuzzle.GetNeighbours(mCurrentState);
// get a random neignbour.
int rn = Random.Range(0, neighbours.Count);
mCurrentState.Value.SwapWithEmpty(
neighbours[rn].Value.GetEmptyTileIndex());
i++;
mPuzzleStateViz.SetPuzzleState(mCurrentState.Value);
yield return null;
}
}
public void Randomize(int depth = 50)
{
StartCoroutine(Coroutine_Randomize(depth));
}
Code language: C# (cs)In the above code, you will see that we are randomising the puzzle by making several moves from the solved state. In essence, we are creating a shuffled state by making moves from the solved state, thus guaranteeing a solution.
Amend the Start method as follows:
void Start()
{
mCurrentState = new PuzzleNode(mPuzzle, new PuzzleState(3));
mGoalState = new PuzzleNode(mPuzzle, new PuzzleState(3));
mAstarSolver.NodeTraversalCost = PuzzleMap.GetCostBetweenTwoCells;
mAstarSolver.HeuristicCost = PuzzleMap.GetManhattanCost;
}
Code language: C# (cs)Create a new Coroutine to solve the puzzle.
IEnumerator Coroutine_Solve()
{
// Keep calling step as long as the pathfinder's status
// is RUNNING.
while (mAstarSolver.Status == PathFinderStatus.RUNNING)
{
mAstarSolver.Step();
yield return null;
}
// SUCCESS.
// Show the solution in a smooth way.
if (mAstarSolver.Status == PathFinderStatus.SUCCESS)
{
Debug.Log("Found solution. Displaying solution now");
StartCoroutine(ShowSolution());
}
// FAILURE
// Failed finding path.
if (mAstarSolver.Status == PathFinderStatus.FAILURE)
{
Debug.Log("Failure");
}
}
Code language: C# (cs)Create a Coroutine that shows the solution after the puzzle is solved.
IEnumerator ShowSolution()
{
List<PuzzleState> reverseSolution =
new List<PuzzleState>();
PathFinder<PuzzleState>.PathFinderNode node =
mAstarSolver.CurrentNode;
while (node != null)
{
reverseSolution.Add(node.Location.Value);
node = node.Parent;
}
if (reverseSolution.Count > 0)
{
mPuzzleStateViz.SetPuzzleState(
reverseSolution[reverseSolution.Count - 1]);
if (reverseSolution.Count > 2)
{
for (int i = reverseSolution.Count - 2; i >= 0; i -= 1)
{
mPuzzleStateViz.SetPuzzleState(reverseSolution[i], 0.5f);
yield return new WaitForSeconds(1.0f);
}
}
}
}
Code language: C# (cs)Finally, add some key inputs to shuffle the puzzle and solve the puzzle. We will use the KeyCode.R to shuffle (randomise) the puzzle and the KeyCode.Space to solve the puzzle.
void Update()
{
// Solve the puzzle and immediately show
// the solution.
if (Input.GetKeyDown(KeyCode.Space))
{
mPuzzleStateViz.SetPuzzleState(mCurrentState.Value);
mAstarSolver.Initialize(mCurrentState, mGoalState);
Solve();
}
// Randomize the puzzle.
if (Input.GetKeyDown(KeyCode.R))
{
Randomize();
}
}
Code language: C# (cs)Click Play in the Unity Editor and run the game. Use the ‘r’ key to randomise the puzzle and use the ‘space’ key to solve and show the solution. Try it out. Below is a video of the solution from my computer.
Download the 8 Puzzle Unlimited App from Google Play.
Read My Other Tutorials
- Implement a Generic Pathfinder in Unity using C#
- Create a Jigsaw Puzzle Game in Unity
- Generic Finite State Machine Using C#
- Implement Bezier Curve using C# in Unity
- Create a Jigsaw Tile from an Existing Image
- Create a Jigsaw Board from an Existing Image
- Solving 8 puzzle problem using A* star search
- A Configurable Third-Person Camera in Unity
- Player Controls With Finite State Machine Using C# in Unity
- Finite State Machine Using C# Delegates in Unity
- Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
- Augmented Reality – Fire Effect using Vuforia and Unity
- Implementing a Finite State Machine Using C# in Unity
- Solving 8 puzzle problem using A* star search in C++
- What Are C# Delegates And How To Use Them
- How to Generate Mazes Using Depth-First Algorithm
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
There is missing code contructor, mEdges and GetNeighbors in PuzzleMap sir
Hi Bladin,
The codes are all there. You should be able to see in the PuzzleMap section. Below extracted from the post.
public List> GetNeighbours(PuzzleNode loc)
{
List> neighbours = new List>();
int zero = loc.Value.GetEmptyTileIndex();
List intArray = GetNeighbors(zero);
for (int i = 0; i < intArray.Count; ++i) { PuzzleNode state = new PuzzleNode(this, new PuzzleState(loc.Value)); state.Value.SwapWithEmpty(intArray[i]); neighbours.Add(state); } return neighbours; }