Solve the Maze by DFS (Depth First Search)

In maze traversal, we must have to traverse deeper as soon as possible through the selected particular path until we reach the dead end. When we are on the way in that path, if it closed then we must have to back track to previous state to select another path. For this reasons, this traversal very similar to the DFS algorithm.

Strategy for exploring Maze:

1.  To convert given maze to a graph mark each intersection, corner and dead end (vertex) visited.
2.  We mark each corridor (edge) as traversed.
3.  We keep track of the path back to the entrance (start vertex) by means of a rope. (recursion stack)

According to above all reasons, DFS (Depth First Search) algorithm very similar to a classic strategy for exploring a maze.

Implementation in C#

Graph.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Maze_traversal
{
    class Graph
    {
        private int maxVertex;
        private Vertex[] vList;
        private int[ , ] adjacencyMatrix;
        private int currentVertices;
        private Stack stack;

        public Graph(int numofVertex) {
            maxVertex = numofVertex;
            vList = new Vertex[maxVertex]; //Store the list of vertices
            adjacencyMatrix = new int[maxVertex,maxVertex];
            currentVertices = 0;//Index for the vList
            for (int i = 0; i < maxVertex; i++) {//Initialize the matrix to zero
                for (int j = 0; j < maxVertex; j++) {
                    adjacencyMatrix[i , j] = 0;
                }
            }
            stack = new Stack(maxVertex);//Create the stack
        }
        //Add vertices to the array
        public void setVertex(char label) {
            vList[currentVertices++] = new Vertex(label);
        }
        //Add edges between vertices
        public void setEdge(int row, int column) {
            adjacencyMatrix[row, column] = 1;
            adjacencyMatrix[column, row] = 1;
        }
        //Display the vertex
        public void showVertex(int index) {
            Console.Write(vList[index].identifier);
        }

        public void dfs(int source) {
            vList[source].flag = true;//mark it and begin at vertex 0
            showVertex(source);
            stack.Push(source);//Push on to the top of the stack
            traverse();
        }
        //Traverse through the path from the source to destination
        public void traverse() {
            while (!stack.isEmpty())
            {
                //Take adjacency vertices for corresponding visited vertex
                int unvisitVertex = getunvisitedVertex(stack.Top());
                if (unvisitVertex == -1)//No more unvisited vertex then pop it
                    stack.Pop();
                else
                {
                    //Else add to the top of the stack
                    Console.Write(" -> ");
                    vList[unvisitVertex].flag = true;
                    showVertex(unvisitVertex);
                    stack.Push(unvisitVertex);
                }
            }
            //Reset flags if stack is empty
            for (int i = 0; i < currentVertices; i++)
            {
                vList[i].flag = false;
            }
        }
        //Get the un-visited adjacency vertices
        public int getunvisitedVertex(int i) {
            for (int j = 0; j < currentVertices; j++)
                if (adjacencyMatrix[i, j] == 1 && vList[j].flag == false)
                    return j;
            return -1;
        }
    }
}

mazeApp.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Maze_traversal
{
    class mazeApp
    {
        public static void Main(String[] args)
        {
            Readfile r = new Readfile(); //Create an object from the Readfile class    
            r.openFile();//Open the text file to read
            List<char> dataSet = new List<char>(r.readFile());//Take the graph nodes' content.
            r.closeFile();//End of the file reading

            Graph maze = new Graph(dataSet.Count);
            //Add vertices to the graph
            for (int j = 0; j < dataSet.Count; j++)
            {
                //Console.WriteLine(dataSet[j]);
                maze.setVertex(dataSet[j]);
            }
            int[] position = r.graphPosition();
            //Add Connection between vertices (edges)
            for (int j = 0; j < position.Length; j+=2)
            {
                //Console.WriteLine(position[j]);
                maze.setEdge(position[j],position[j+1]);
            }

            Console.WriteLine("........................MAZE TRAVERSAL...................\n");
       
            while (true)
            {
                Console.Write("\nInitialize the source node for DFS :");
                string userInput = Console.ReadLine();//Take the user input
                Console.WriteLine();
                char source;
                if (userInput == "exit")//Check whether user input is exit
                {
                    Console.WriteLine("\n.........................................................\n");
                    Console.WriteLine("\nExit from the system successfully................\n");
                    Environment.Exit(0);
                }
                bool parsed = char.TryParse(userInput, out source);//Parsed the user input to character
                if (!parsed)
                {
                    Console.WriteLine("WARNING : Could not parse '{0}' to character........", userInput);
                }
                else
                {
                    if (dataSet.Contains(source))//Check whether sorce node contains the graph
                    {
                        maze.dfs(dataSet.IndexOf(source));//Executes the DFS Algorithm
                    }
                    else
                        Console.WriteLine("\nWARNING : Character '{0}' does not exists in the Graph........", source);
                }
                Console.WriteLine("");
            }
        }
    }
}

Readfile.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace Maze_traversal
{
    class Readfile
    {
        StreamReader buff = null;
        List<string> v = new List<string>();//Store the file data
        List<char> dataSet = new List<char>();//Extract the characters and store it
        public void openFile()
        {
            try
            {
                buff = new StreamReader("Graph.txt");//Open the file to read
            }
            catch (Exception ex)
            {
                Console.WriteLine("File can't open : " + ex);
            }
        }
        //Read content of the file
        public List<char> readFile()
        {
            try
            {
                string s = buff.ReadLine();
                while (s != null)
                {
                    v.Add(s);//Add each element to the list
                    s = buff.ReadLine();//Read next line
                }
            }
            catch (NullReferenceException ex)
            {
                Console.WriteLine(ex);
            }
           //Initialize the character variable to 'n'
            char character='n';
      
            for (int j = 0; j < v.Count; j++)
            {
                for (int i = 0; i < v[j].Length; i++)
                {
                    character = v[j][i];//Extract the characters from string list v
               
                    if (!dataSet.Contains(character)) //Check whether character exists in dataSet array
                    {
                        dataSet.Add(character);//Characters add to the dataSet array
                    }
                }
            }
            return dataSet;//Return the int array
        }
        //Take the adjacancy matrix positions
        public int[] graphPosition() {
            int[] position = new int[2 * v.Count];//Store the positions of graph
            int counter=0;
            for (int j = 0; j < v.Count; j++)
            {
                for (int i = 0; i < v[j].Length; i++)
                {
                    position[counter] = dataSet.IndexOf(v[j][i]);//(G,H)=>(0,1),(G,D)=>(0,2)....like that
                    counter++;
                }
            }
                return position;
        }
        //Close File after the reading completed
        public void closeFile()
        {
            try
            {
                buff.Close();//Close the file
            }
            catch (NullReferenceException ex)
            {
                Console.WriteLine(ex);
            }
        }
    }
}

Stack.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Maze_traversal
{
    class Stack
    {
       private int[] array;
       private int tos;

       public Stack(int size)//Initialize the Stack (Constructor for the Stack class)
        {
            array = new int[size]; //Build the array of Stack
            tos = -1;
        }

       public void Push(int key) //Insert a key into the Stack
       {
           array[++tos] = key;
       }

       public int Pop() //Delete a key from the top of the stack
       {
           return array[tos--];
       }

       public int Top()//Peek the top value
       {
           return array[tos];
       }

       public bool isEmpty()//Check whether the stack is empty
       {
           return (tos == -1);
       }
    }
}

Vertex.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Maze_traversal
{
    class Vertex
    {
        public char identifier;//Label of the node
        public bool flag;//Check whether it was visited

        public Vertex(char label) {
            this.identifier = label;
            this.flag = false;
        }
    }
}

Graph.txt file