8 Puzzle with Depth First Search and C#

Depth-First search is just like Breadth-First as I mentioned (in Turkish though). Only difference is we use Stack instead of Queue for Frontier, which makes the create new successors over an over, over same branch until seeing a leaf node, which doesn't exist in 8-Puzzle example, because there is always one move to do (at least), in any situation.







So let's start!
You will need same functions mentioned at Breadth-First example; you have to change Frontier and it's functions for Stack, Node.cs will remain same, you can reach it with this address: Node.cs.

Your main will initialize DFS for this example;

        static void Main(string[] args)
        {
            int[] ex = { 1, 2, 3, 0, 4, 5, 6, 7, 8 };
            DFS_dfs = new DFS(ex);
            _dfs.Solve();
        }

DFS.cs file will have;
private Stack<Node> Frontier  instead of private Queue<Node> Frontier.

It will contain;


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

        public DFS(int[] StartState)
        {}

        public void Solve()
        {}

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

        public bool IsGoalState(int[] State)
        {}

        public void WriteSolution()
        {}
}


The only change is in Solve function; to add an item to a Stack you use Push command instead of Enqueue which used in Queues, just like Pop command for Dequeue.

Solve function will be;

1.         public void Solve()
2.         {
3.             Node ActiveNode = RootNode;
4.             bool IsSolved = false;
5.             while (!IsGoalState(ActiveNode.GetState()))
6.             {
7.                 Solution.Add(ActiveNode);
8.                 foreach(Node successor in GenerateSuccessor(ActiveNode))
9.                 {
10.                     Frontier.Push(successor);
11.                     if (IsGoalState(successor.GetState()))
12.                     {
13.                         IsSolved = true;
14.                         Solution.Add(successor);
15.                         break;
16.                     }
17.                 }
18.                 if (IsSolved)
19.                     break;
21.                 ActiveNode = Frontier.Pop();
22.             }
23.             WriteSolution();
24.         }

It is not fast as BFS, and generally you don't get much result in 8-Puzzle problems with Depth First Search, because it just create successors over a branch, if that branch doesn't bring us to the solution, we might never find it. So, DFS is not complete.

Source Files:
DFS.cs
Node.cs
Program.cs