Knight's tour using DFS Java

Question

I'm trying to implement Knight's tour.

I've been working on(more like planning) it for almost good 2~3hours now. and I still haven't made any progress. I seem to be unable to find the starting point..

below is the basic dfs method which I have to modify to knight's tour version.

class StackK
{
private final int MAX_VERTS = 25;
private int[] st;
private int top;
// ------------------------------------------------------------
public boolean isFull()
{return (top == MAX_VERTS-1);}
// ------------------------------------------------------------
public StackK()           // constructor
  {
  st = new int[MAX_VERTS];    // make array
  top = -1;
  }
// ------------------------------------------------------------
public void push(int j)   // put item on stack
  { st[++top] = j; }
// ------------------------------------------------------------
public int pop()          // take item off stack
  { return st[top--]; }
// ------------------------------------------------------------
public int peek()         // peek at top of stack
  { return st[top]; }
// ------------------------------------------------------------
public boolean isEmpty()  // true if nothing on stack
  { return (top == -1); }
// ------------------------------------------------------------
}  // end class StackK

class VertexK
{
public char label;        // label (e.g. 'A')
public boolean wasVisited;
// ------------------------------------------------------------
public VertexK(char lab)   // constructor
  {
  label = lab;
  wasVisited = false;
  }
// ------------------------------------------------------------
}   // end class VertexK

class GraphK
{
private final int MAX_VERTS = 5;
private VertexK VertexKList[]; // list of vertices
private int adjMat[][];      // adjacency matrix
private int nVerts;          // current number of vertices
private StackK theStack;
// ------------------------------------------------------------
 public GraphK()               // constructor
  {
  VertexKList = new VertexK[MAX_VERTS];
                                      // adjacency matrix
  adjMat = new int[MAX_VERTS][MAX_VERTS];
  nVerts = 0;
  for(int y=0; y<MAX_VERTS; y++)      // set adjacency
     for(int x=0; x<MAX_VERTS; x++)   //    matrix to 0
        adjMat[x][y] = 0;
  theStack = new StackK();
  for(int i=0;i<MAX_VERTS;i++)
       addVertex((char)('A'+i));

  }


// ------------------------------------------------------------
public void move(int row, int col)
{

}
// ------------------------------------------------------------
public void addVertex(char lab)
   {
   VertexKList[nVerts++] = new VertexK(lab);
   }
// ------------------------------------------------------------
public void addEdge(int start, int end)
  {
  adjMat[start][end] = 1;
  }

 // ------------------------------------------------------------
public void displayVertexK(int v)
  {
  System.out.print(VertexKList[v].label);
  }


 // ------------------------------------------------------------

public void dfs()  // depth-first search
  {                                 
  VertexKList[0].wasVisited = true;  
  displayVertexK(0);                 
  theStack.push(0);

  displayAdj();


  while( !theStack.isEmpty() )      
     {

     int v = getAdjUnvisitedVertexK( theStack.peek() );
     if(v == -1)                    
        theStack.pop();
     else                           
        {
        VertexKList[v].wasVisited = true;  
        displayVertexK(v);                 
        theStack.push(v);                
        }
     }  // end while

  // stack is empty, so we're done
  for(int j=0; j<nVerts; j++)          // reset flags
     VertexKList[j].wasVisited = false;
  }  // end dfs

 // ------------------------------------------------------------
// returns an unvisited VertexK adj to v
public int getAdjUnvisitedVertexK(int v)
  {
  for(int j=0; j<nVerts; j++)
     if(adjMat[v][j]==1 && VertexKList[j].wasVisited==false)
        return j;
  return -1;
  }  // end getAdjUnvisitedVertexK()
// ------------------------------------------------------------
public void displayAdj()
{
   for(int i=0;i<nVerts;i++){
       for(int k=0;k<nVerts;k++)
           System.out.print(adjMat[i][k]);
   System.out.println("");
   }
}
 // ------------------------------------------------------------
}  // end class GraphK

public class KnightApp
{
public static void main(String[] args)
  {
  GraphK k = new GraphK();

  k.displayAdj();


  }  // end main()
}  // end class DFSApp

I chose to make the board size 5x5 for simplicity. I have googled it and looked some of the solutions and most of them didn't make sense to me. How can I make use of the DFS method? I think I could somewhat implement it if were to use recursion without using DFS. However, I have no idea, not even where to start with DFS.

Can anyone give me some guidance on where to start? I'm not asking for a solution, just need a place to start

Thank you in advance.

Answer 1

Depth first search as such is a general strategy for enumeration of the nodes of a graph; it can be implemented recursively or iteratively supported by a user-defined stack. The graph to search can be encoded explicitly, which is usually done when the approach is explained.

Hoever, in your case, the graph (which is some kind of decision tree of a game) does not need to be encoded explicitly; new successor nodes can be generated by selecting a feasible move, representing the new state on a global state (representing the board), and after recursive evaluation undo the move to proceed with the next feasible move. Using this approach, backtracking can be implemented via recursion.