8 Puzzle with Breadth First Search and C#

8 puzzle is a puzzle has 3x3 squares. It is a sliding puzzle, so to solve it, you have to move the empty square to end or beginning, and align other squares in order (order or alignment may differ among different type of puzzles)

There can be a different solution paths of a 8 Puzzle, but the goal state is determined and always the same.


Today we are going to use C# to write an agent that solves (or try to solve) any unsolved 8 puzzle examples given. In my examples, 8 Puzzle has a goal state which is {1,2,3,4,5,6,7,8,0}. 0 represents the empty square, and since it is 9th element in the array, it would be on the 3rd row and 3rd column on the given example image.

Let's start!

Create a C# Console Application and name it as 8PuzzleBFS.
We create 2 classes: BFS.cs and Node.cs. We will use Program.cs which consists Main procedure as main class that controls the software and algorithm.

• Start with Node.cs. It is going to have the State the Node in. ID of the generated Node which starts with 0 if there is no previous one, and get/set functions. Also, the Move which applied to parent state the generate the successor, and ParentID determines parent.

• In BFS.cs, we will need a function that generates new nodes, a function that checks if the node is in goal state, and a Queue, list for Solution, 

So, Node.cs file consists;

class Node
{
        static int _IdCnt = 0;
        private int[] State;
        private int Id;
        private int ParentId;
        private char Move;
        public Node(int[] State,int ParentId, char Move)
       {}

        public void SetState(int[] State)
       {}

        public int[] GetState()
       {}

        public int GetId()
       {}

        public int GetParentId()
       {}

        public char GetMove()
       {}
}

and BFS.cs has;

class BFS
{
        int[] GoalState = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
        private Queue<Node> Frontier;
        private HashSet<Node> Solution;
        private Node RootNode;

        public BFS(int[] StartState)
        {}

        public void Solve()
        {}

        public IEnumerable<Node> GenerateSuccessor(Node ParentNode)
        {}

        public bool IsGoalState(int[] State)
        {}

        public void WriteSolution()
        {}
}

To run the software; we create an instance of BFS, and give an example, "s";

        static void Main(string[] args)
        {
            int[] s = { 1, 2, 3, 0, 4, 5, 6, 7, 8 };
            BFS _bfs = new BFS(s);
            _bfs.Solve();
        }

Here is the screenshot of running software:

 

Source Files:
BFS.cs
Node.cs
Program.cs