The 8-Puzzle Problem is a thing they throw at you when you study Artificial Intelligence. It’s a great little problem for learning to understand search trees and shortest path algorithms with heuristics. Traveling from Breadth-First Search, via Depth First Search we mostly end up with the A* Algorithm using a Manhattan Distance Heuristic to effectively solve this problem. This article shows how to do this in C#.

You can download this code from the Remondo/EightPuzzleProblem repository on GitHub

Solving the 8-puzzle requires to get the familiar square board with eight numbered tiles from a given start-state to the goal state in the least possible steps. Here’s our 8-puzzle start and goal state example:

To solve this problem we need an algorithm that searches through a tree of possible steps and is smart enough to provide a solution in a reasonably small amount of time. This is where the A* Algorithm comes into play. It’s often called a pathfinder algorithm and is widely used in robotics, gaming, navigation, you name it, to find the shortest path to a known goal.

For more in depth information here’s a comprehensive introduction on the A* Algorithm.

In our case we need to create an A* search method that takes a start and goal state and returns the solution node (with the desired goal state) in the path. From this goal node we can travel via its parent node the shortest path back to the start node. So our example 8-puzzle here would translate to something like this in code:

var start = new EightPuzzleNode { Tiles = new[] { 4, 1, 2, 0, 8, 7, 6, 3, 5 } }; var goal = new EightPuzzleNode { Tiles = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 0 } }; INode result = pathFinder.Execute(start, goal);

Now let’s get to work… first we need a search node.

## The Search Node

We need to find a path of connected nodes to the goal by using the A* Algorithm. Let’s create an interface to specify what our node looks like. It consists of three value members, one pointer to a parent node and one comparison method.

namespace EightPuzzleGame { public interface INode { float F { get; set; } // total of G + H float G { get; set; } // Cost of the path until now float H { get; set; } // Heurstic - estimated costs to goalnode INode Parent { get; set; } bool HasEqualState(INode node); } }

So what do we have here:

**The ‘G’ value**

contains the costs from the start node to the current node. For example if we have traveled six steps from the start node to get to this node the value is six.**The ‘H’ value**

contains the estimated costs from this node to the goal. We use a heuristic function for this. For example if the total of tiles that are in the wrong spot is five then the H value is five.**The ‘F’ value**

contains the sum of the G and H value. We use this value to determine the possible best step to take from the current node given a set of successor nodes.**The ‘Parent’**

contains a pointer to previous node in the path. If it is null, we are at the start of our path.**HasEqualState**

returns true if the state is exactly equal to the compare node. For example if the tiles in the 8-Puzzle game are in the exact same spot on both nodes.

From this interface we create an implementation of a node to use for solving our 8-puzzle problem. We use a simple array of integers to store our puzzle tiles. This gives us the opportunity to use the LINQ SequenceEqual method to compare tile states. It also has a EmptyTileIndex property that stores the index of the empty tiles. We need this for our value calculations described later in this post.

using System.Linq; namespace EightPuzzleGame { public class EightPuzzleNode : INode { private int _emptyTileIndex; public EightPuzzleNode() { _emptyTileIndex = -1; } public int[] Tiles { get; set; } public int EmptyTileIndex { get { if (_emptyTileIndex == -1) _emptyTileIndex = GetEmptyTilePosition(this); return _emptyTileIndex; } } #region INode Members public float F { get; set; } public float G { get; set; } public float H { get; set; } public INode Parent { get; set; } public bool HasEqualState(INode node) { var testNode = node as EightPuzzleNode; return testNode != null && Tiles.SequenceEqual(testNode.Tiles); } #endregion private static int GetEmptyTilePosition(EightPuzzleNode node) { int emptyTilePos = -1; for (int i = 0; i < 9; i++) { if (node.Tiles[i] == 0) { emptyTilePos = i; break; } } return emptyTilePos; } } }

Great! We have a construct to store an 8-puzzle state, a pointer to its predecessor node in the path and the calculated F, G and H values. But how do we calculate these values?

## The A* Algorithm Pseudo Code

Let’s look at some pseudo code, borrowed from Rajiv Eranki’s page at MIT, first before we dive into the technical its and bits of the algorithm.

#region pseudocode // A* Algorithm // --------------------------------------------------------------------------- // -initialize the open list // -initialize the closed list // put the starting node on the open list (you can leave its f at zero) // // while the open list is not empty // find the node with the least f on the open list, call it "q" // pop q off the open list // generate q's 8 successors and set their parents to q // for each successor // if successor is the goal, stop the search // successor.g = q.g + distance between successor and q // successor.h = distance from goal to successor // successor.f = successor.g + successor.h // // if a node with the same position as successor is in the OPEN list // which has a lower f than successor, skip this successor // if a node with the same position as successor is in the CLOSED list // which has a lower f than successor, skip this successor // otherwise, add the node to the open list // end // push q on the closed list // end // --------------------------------------------------------------------------- #endregion

For the A* Algorithm to function properly we need an open list with nodes yet to consider within our path, sorted by the lowest F-value (simply G + H). Besides that we have a closed list with nodes already tried. We also need to be able to calculate the G-value, H-value and F-value of a node and generate successor nodes. This is a list of all possible nodes/steps we can take after our current node.

For the open and closed lists we just use a generic List of INode. For the open list this is not the fastest collection type but it’ll do the trick for now. The G-value, H-value and successornode generator are all functions injected into the A* Algorithm to do their job. For this we use the Strategy Pattern. Let’s take a look at these strategies.

## The G-value calculator

The G-value is a very simple strategy in our case. The Execute method takes the G-value of a node and adds a constant CostFactor value to that. The constant value is the cost of one step. In our example this is set by trial and error for the best performance. Here’s the interface:

namespace EightPuzzleGame.Calculators { public interface IGValueCalculator { float Execute(INode node); } }

… and the actual implementation for our 8-puzzle problem.

namespace EightPuzzleGame.Calculators { public class EightPuzzleGValueCalculator : IGValueCalculator { private const float CostFactor = 0.265f; // trial and error based #region IGValueCalculator Members public float Execute(INode node) { return node.G + CostFactor; } #endregion } }

Note that each step or branching level in the path adds a 0.265 cost. We see this baby in action when we discuss the actual A* Algorithm implementation in this post.

## The H-value Calculator

This strategy calculates the estimated cost to the goal node by using a heuristic function. The function calculates some value that expresses the expected distance to the goal. The lower the value the more likely we’ll get there faster.

According to Wikipedia: heuristic refers to experience-based techniques for problem solving, learning, and discovery. Where an exhaustive search is impractical, heuristic methods are used to speed up the process of finding a satisfactory solution. Examples of this method include using a rule of thumb, an educated guess, an intuitive judgment, or common sense.

It’s something we use in every day life quite often. If we don’t know the way to the train station we don’t just walk in a direction hoping to find it. We use our experience to take a best guess by following a rail track or walking towards the center of the city for instance. It’s no guaranty we’ll get there faster though, but chances are we will be. Using experiences this way is what makes us humans intelligent.

The same goes for computer programs, so this H-value strategy can make our search a faster and smarter search. Again no guarantees. Here’s the interface. It takes a current node and the goal node and returns the calculated H-value.

namespace EightPuzzleGame.Calculators { public interface IHValueCalculator { float Execute(INode goalNode, INode node); } }

For the implementation we can use a lot of distance calculations, like counting all tiles in the wrong spot. However we use the Manhattan Distance heuristic, since it is proven to be the fastest with the 8-puzzle problem. It calculates of each tile the number of blocks away from the desired spot. The grand total of all tiles is the H-value. Here’s an example:

The tile with number six is not in the right spot. In fact it is three blocks away from it. In the second image we calculated all individual tiles. When we sum up all the values we get an H-value of 16.0 if we use a CostFactor of exactly 1.0. Our H-value calculator looks like this:

namespace EightPuzzleGame.Calculators { public class EightPuzzleManhattanDistanceCalulator : IHValueCalculator { private const float Costfactor = 1.0f; #region IHValueCalculator Members public float Execute(INode goal, INode node) { float result = 0.0f; var currentNode = node as EightPuzzleNode; var goalNode = goal as EightPuzzleNode; for (int i = 0; i < 9; i++) { if (goalNode == null) continue; int currentNumber = goalNode.Tiles[i]; int currentIndex = FindTileCurrentIndex(currentNumber, currentNode); result = GetDistanceToGoalTileForIndex(result, i, currentIndex); } return result; } #endregion private static float GetDistanceToGoalTileForIndex(float result, int i, int currentIndex) { if (currentIndex == i + 0) return result; if (currentIndex == i + 1 || currentIndex == i + 3) result += Costfactor; else if (currentIndex == i + 2 || currentIndex == i + 4 || currentIndex == i + 6) result += 2 * Costfactor; else if (currentIndex == i + 5 || currentIndex == i + 7) result += 3 * Costfactor; else if (currentIndex == i + result += 4 * Costfactor; return result; } private static int FindTileCurrentIndex(int goalNumber, EightPuzzleNode current) { for (int j = 0; j < 9; j++) { if (current.Tiles[j] == goalNumber) { return j; } } return -1; } } }

On Execute our H-value stratgey finds for each tile the index/position with FindTileCurrentIndex. After that it adds the calculated distance to the result with the (not that clever but sufficient) GetDistanceToGoalTileForIndex method. When all tiles are reviewed against the goal position it returns the cumulative H-value.

## Generating Successor Nodes

The final strategy we need for our A* Algorithm is the successor node generator. It takes a node on Execute and returns a list of successor nodes. Here’s the interface:

using System.Collections.Generic; namespace EightPuzzleGame.SuccessorNodes { public interface ISuccessorNodesGenerator { IEnumerable<INode> Execute(INode node); } }

The successor nodes are all possible next steps without the parent step of the node (then we would go back to a previous state). Here’s a ‘nice’ drawing of three successor node calculations from a given state. The black tile is the empty tile.

Following the red path. In our first step we can choose from four different successors. Next there are two possible candidates left. The last step only generates one successor. In code our successor calculator looks like this:

using System.Collections.Generic; using System.Linq; namespace EightPuzzleGame.SuccessorNodes { public class EightPuzzleSuccessorNodesGenerator : ISuccessorNodesGenerator { #region ISuccessorNodesGenerator Members public IEnumerable<INode> Execute(INode currentNode) { var node = currentNode as EightPuzzleNode; var successorRules = new List<ISuccessorNodesCalculationRule> { new EightPuzzleSuccessorsForEmptyTileZero(), new EightPuzzleSuccessorsForEmptyTileOne(), new EightPuzzleSuccessorsForEmptyTileTwo(), new EightPuzzleSuccessorsForEmptyTileThree(), new EightPuzzleSuccessorsForEmptyTileFour(), new EightPuzzleSuccessorsForEmptyTileFive(), new EightPuzzleSuccessorsForEmptyTileSix(), new EightPuzzleSuccessorsForEmptyTileSeven(), new EightPuzzleSuccessorsForEmptyTileEight() }; return successorRules .Single(r => r.Match(node)) .GetSuccessors(node); } #endregion } }

In this code we try to adhere to the Open / Closed Principle by using the Strategy Pattern again. This time to store and execute the business rules for each position the empty tile can be in. A call to the Match method executes the actual successor generation. So here’s what it looks like in code in case the empty tile is in the center (position four):

using System.Collections.Generic; namespace EightPuzzleGame.SuccessorNodes { public class EightPuzzleSuccessorsForEmptyTileFour : EightPuzzleSuccessorNodesCalculationRuleBase { public override IEnumerable<INode> GetSuccessors(INode node) { var result = new List<INode>(); AddSuccessor((EightPuzzleNode) node, result, 1); AddSuccessor((EightPuzzleNode) node, result, 3); AddSuccessor((EightPuzzleNode) node, result, 5); AddSuccessor((EightPuzzleNode) node, result, 7); return result; } public override bool Match(INode node) { return ((EightPuzzleNode) node).EmptyTileIndex == 4; } } }

The base class for this calculation rule implements the actual AddSuccessor method. This method generates a single successor state, points it to its parent(!) and adds it to the collection of successor nodes if it is not the same state as the parent (since we’ve been there before).

using System.Collections.Generic; using System.Linq; namespace EightPuzzleGame.SuccessorNodes { public class EightPuzzleSuccessorNodesCalculationRuleBase : ISuccessorNodesCalculationRule { #region ISuccessorNodesCalculationRule Members public virtual IEnumerable<INode> GetSuccessors(INode node) { return null; } public virtual bool Match(INode node) { return false; } #endregion protected static void AddSuccessor(EightPuzzleNode node, ICollection<INode> result, int swapTile) { var newState = node.Tiles.Clone() as int[]; if (newState == null) return; newState[node.EmptyTileIndex] = newState[swapTile]; newState[swapTile] = 0; if (!IsEqualToParentState(node.Parent, newState)) result.Add(new EightPuzzleNode {Tiles = newState, Parent = node}); } private static bool IsEqualToParentState(INode node, IEnumerable<int> state) { return node != null && state.SequenceEqual(((EightPuzzleNode) node).Tiles); } } }

## The A* Algorithm

Finally we are ready to implement the last piece of the puzzle; the A* Algorithm called PathFinder. In the constructor we take a Successor Nodes Generator and both G-value and H-value calculators as shown above. If we ever want to use other calculation strategies we can just plug ‘m in. The Execute method is a clean and straightforward implementation of our pseudo A* Algorithm shown above.

using System.Collections.Generic; using System.Linq; using EightPuzzleGame.Calculators; using EightPuzzleGame.SuccessorNodes; namespace EightPuzzleGame { public class PathFinder { private readonly ISuccessorNodesGenerator _successorNodesGenerator; private readonly IGValueCalculator _gValueCalculator; private readonly IHValueCalculator _hValueCalculator; public PathFinder(ISuccessorNodesGenerator successorNodesGenerator, IGValueCalculator gValueCalculator, IHValueCalculator hValueCalculator) { _successorNodesGenerator = successorNodesGenerator; _gValueCalculator = gValueCalculator; _hValueCalculator = hValueCalculator; } public int Cycles { get; private set; } public INode Execute(INode startNode, INode goalNode) { Cycles = 0; var openList = new List<INode> {startNode}; var closedList = new List<INode>(); while (openList.Count > 0) { Cycles++; INode currentNode = GetBestNodeFromOpenList(openList); openList.Remove(currentNode); closedList.Add(currentNode); IEnumerable<INode> successorNodes = _successorNodesGenerator.Execute(currentNode); foreach (INode successorNode in successorNodes) { if (successorNode.HasEqualState(goalNode)) return successorNode; successorNode.G = _gValueCalculator.Execute(currentNode); successorNode.H = _hValueCalculator.Execute(goalNode, successorNode); successorNode.F = successorNode.G + successorNode.H; if (OpenListHasBetterNode(successorNode, openList)) continue; openList.Add(successorNode); } } return null; } private static INode GetBestNodeFromOpenList(IEnumerable<INode> openList) { return openList.OrderBy(n => n.F).First(); } private static bool OpenListHasBetterNode(INode successor, IEnumerable<INode> list) { return list.FirstOrDefault(n => n.G.Equals(successor.G) && n.F < successor.F) != null; } } }

So there it is. We’re finally ready to take it for a spin…

## Solving The 8-Puzzle Tests

We test against three start states; a simple, medium and hard one. When the A* Algorithm comes back with a solution node we traverse back up the path to the start node and print all successive steps with the F, G and H values and store it in our test results.

using System.Collections.Generic; using System.Diagnostics; using System.Linq; using EightPuzzleGame; using EightPuzzleGame.Calculators; using EightPuzzleGame.SuccessorNodes; using Microsoft.VisualStudio.TestTools.UnitTesting; namespace EightPuzzleSolverTests.Model { [TestClass] public class EightPuzzleTests { private static readonly EightPuzzleNode Goal = new EightPuzzleNode {Tiles = new[] {1, 2, 3, 4, 5, 6, 7, 8, 0}}; private PathFinder _pathFinder; [TestInitialize] public void Init() { _pathFinder = new PathFinder( new EightPuzzleSuccessorNodesGenerator(), new EightPuzzleGValueCalculator(), new EightPuzzleManhattanDistanceCalulator()); } [TestMethod] public void GivenSimpleState_ShouldFindSolution() { // arrange var start = new EightPuzzleNode {Tiles = new[] {4, 1, 3, 0, 2, 6, 7, 5, 8}}; // act INode result = _pathFinder.Execute(start, Goal); // assert PrintSolution(_pathFinder, result); Assert.IsTrue(Goal.HasEqualState(result)); } [TestMethod] public void GivenMediumState_ShouldFindSolution() { // arrange var start = new EightPuzzleNode {Tiles = new[] {3, 0, 5, 7, 8, 6, 1, 2, 4}}; // act INode result = _pathFinder.Execute(start, Goal); // assert PrintSolution(_pathFinder, result); Assert.IsTrue(Goal.HasEqualState(result)); } [TestMethod] public void GivenHardestState_ShouldFindSolution() { // arrange var start = new EightPuzzleNode {Tiles = new[] {8, 6, 7, 2, 5, 4, 3, 0, 1}}; // act INode result = _pathFinder.Execute(start, Goal); // assert PrintSolution(_pathFinder, result); Assert.IsTrue(Goal.HasEqualState(result)); } [TestMethod] public void GivenRemondoExampleState_ShouldFindSolution() { // arrange var start = new EightPuzzleNode { Tiles = new[] { 4, 1, 2, 0, 8, 7, 6, 3, 5 } }; // act INode result = _pathFinder.Execute(start, Goal); // assert PrintSolution(_pathFinder, result); Assert.IsTrue(Goal.HasEqualState(result)); } private static void PrintSolution(PathFinder pathFinder, INode result) { int steps = 0; INode node = result; if (node != null) { var stack = new Stack<INode>(); do { stack.Push(node); } while ((node = node.Parent) != null); Debug.WriteLine("8-Puzzle Solved in {0} Cycles", pathFinder.Cycles); Debug.WriteLine("-------------------------------------------"); foreach (EightPuzzleNode solutionNode in stack) { string tiles = solutionNode.Tiles .Aggregate("", (current, i) => current + i.ToString()); Debug.WriteLine("{0:00} - {1} - F: {2:00.0} G: {3:00.0} H: {4:00.0}", steps++, tiles, solutionNode.F, solutionNode.G, solutionNode.H); } } else { Debug.WriteLine("No solution"); } } } }

So our example state can be solved in 17 steps. We only needed 411 search cycles to find the solution. It took the A* Algorithm 0.02 seconds. The four tests under half a second. Those execution times are not bad at all :-)

Thanks For this Article, I Have test the Source code But it can’t be run Currectly, I have Open The .SLN file but it shows me a error “a project with an output type of class library cannot be start directly” . I should Say I have chosen “Eight Puzzle Game” as start up project! Please Help me With this !

Hey Pouyaan,

If you are not running an Express version of Visual Studio you can run the tests with CTRL+R,A. If you do use Express then there is a console application in the solution called EightPuzzleConsole. Try run that and give it the input of a valid start state of the puzzle (e.g. 867254301).

Let me know if it works

i cant run the code i have vs 2012 express Please help me

hallow.

Am new in c# bat i am trying to use your code and follow all the procedures bat i get a problem on when i run it, it didnt show any thing so could you help me.

i get an assignment on that if you could help me.

thanx in advance.

how i can understand it is unsolved

suppose

1 2 3

4 5 6

8 7 0 this is unsolved … how can i check it in my code ?

This feature is not provided in the code, but I guess you can set something like a treshold/maximum to the number of moves.

good job.

Your “GetDistanceToGoalTileForIndex” method is a little messed up. It gives out h-values lower than it should in many cases. This is because it only checks if the currentIndex value is in a “greater” position than i, it doesn’t check if it is in a “lesser” position.

For example:

if (currentIndex == i + 1 || currentIndex == i + 3)

result += Costfactor;

Should actually be:

if (currentIndex == i + 1 || currentIndex == i + 3 || currentIndex == i – 1 || currentIndex == i – 3)

result += Costfactor;

Otherwise if it is checking the distance value for 2 in a case like this

2##

###

###

It would ignore the 2, because the method doesn’t check if it’s in the i-1 position.

Hmm, sounds you could be right. I’m gonna give it some thought this weekend. Thanks for sharing!

Great post, I’m currently working through something similar and I’m using your post as a resource.. finally wrapping my head around it thanks to you. Despite how many places say ‘its easy to understand’ it wasn’t so easy for me at first.

Working through your post so far I’ve noticed two things

* In the example code just before the heading ‘Generating Successor Nodes’ there is a guy with sunglasses hiding in your code

* When you introduce the H value you mention you’ll be counting number of tiles out of place, but you ended up counting the total distance for all tiles

I’ve also got a question.. for calculating the G-cost, the cost factor is set to 0.265f with a comment “trial and error based” – why is this not 1? I’d like to know the story behind it if you remember it.

Thanks again for an excellent post and resource. If you’re interested in what I’m doing I’ll be trying to get this to work with a 4×4 grid with random numbers instead of sequential ones.. a game puzzle inspired me to do it that way. The game generates two random 4×4 grids filled with numbers 1-9 (well, minus one number for a blank space) – one grid is the problem and the other is the expected answer.

Thanks For this Article, how i can do this in php?

Hi

I am looking for 8 puzzle algorithm for the third Heuristic.

With c #

Grateful

Thank for you I tried to write a code for the breadth first search and it was ok but I had many problems in A* and iterative search please can I take a full project as attachment ,thanks a lot for you.