Knight’s tour depth-first search infinite loop

I’m trying to solve the knight’s tour problem using a depth-first search algorithm. The algorithm seems te be looping whenever it has two choices that both result in a dead end. I understand that this is caused because the algorithm resets the ‘wasVisited’ boolean to false again whenever a dead end is found but i simply don’t know how to fix it.

Here’s the code i have so far:

  public void dfs() { 
    vertexList[0].wasVisited = true;
    theStack.push(0);
    System.out.println("Visited: 0");

    while (!theStack.isEmpty()) {
        int v = getAdjUnvisitedVertex(theStack.peek());
        if (v == -1) {
            vertexList[lastVisited].wasVisited = false;
            theStack.pop();
            System.out.println("Go back to: " + theStack.peek());
        } else {
            vertexList[v].wasVisited = true;
            lastVisited = v;
            System.out.println("Visited: " + v);
            theStack.push(v);
        }
    }

    for (int j = 0; j < nVerts; j++) {
        vertexList[j].wasVisited = false;
    }

}

public int getAdjUnvisitedVertex(int v) {
    for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
            if (j != lastVisited) {
                return j;
            }
        }
    }
    return -1;
}

Thanks in advance :).

Edit:

Here’s the updated code and a bit the output:

    public void dfs() {
    vertexList[0].wasVisited = true;
    theStack.push(0);
    System.out.println("Visited: 0");

    while (!theStack.isEmpty()) {
        int v = getAdjUnvisitedVertex(theStack.peek());
        if (v == -1) {
            vertexList[lastVisited].wasVisited = false;
            theStack.pop();
            System.out.println("Go back to: " + theStack.peek());
            int backTo = theStack.peek();
            int newDestination = getNextAdjVertex(backTo, lastVisited);
            lastVisited = newDestination;
            while (newDestination == -1) {
                theStack.pop();
                backTo = theStack.peek();
                System.out.println("Go back to: " + backTo);
                newDestination = getNextAdjVertex(backTo, lastVisited);
                lastVisited = newDestination;
                if (newDestination != -1) {
                    vertexList[newDestination].wasVisited = false;
                }
            }
            System.out.println("New Destination " + newDestination);
            vertexList[newDestination].wasVisited = true;
            lastVisited = newDestination;
            System.out.println("Visited: " + newDestination);
            theStack.push(newDestination);
        } else {
            vertexList[v].wasVisited = true;
            lastVisited = v;
            System.out.println("Visited: " + v);
            theStack.push(v);
        }
    }

    for (int j = 0; j < nVerts; j++) {
        vertexList[j].wasVisited = false;
    }

}

public int getNextAdjVertex(int currentVertex, int vertexICameFrom) {
    for (int j = 0; j < nVerts; j++) {
        if (adjMat[currentVertex][j] == 1 && vertexList[j].label != vertexICameFrom && vertexList[j].wasVisited == false) {
            return j;
        }
    }
    return -1;
}

public int getAdjUnvisitedVertex(int v) {
    for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
            if (j != lastVisited) {
                return j;
            }
        }
    }
    return -1;
}

I’m trying to solve this for a 5×5 board so there are 25 verticles (0 – 24). Here’s a bit of the output in which the current problem becomes more clear:

Visited: 0
Visited: 7
Visited: 4
Visited: 13
Visited: 2
Visited: 5
Visited: 12
Visited: 1
Visited: 8
Visited: 11
Visited: 18
Visited: 9
Go back to: 18
New Destination 21
Visited: 21
Visited: 10
Visited: 17
Visited: 6
Visited: 3
Visited: 14
Visited: 23
Visited: 16
Go back to: 23
Go back to: 14
Go back to: 3
Go back to: 6
New Destination 15
Visited: 15
Visited: 22
Visited: 19
Go back to: 22
Go back to: 15
Go back to: 6
Go back to: 17
New Destination 20
Visited: 20
Go back to: 17
New Destination 24
Visited: 24
Go back to: 17
New Destination 20
Visited: 20
Go back to: 17
New Destination 24
Visited: 24

The looping at the end of the output is, ofcourse, not supposed to happen.

Answer

I’m gonna explain this by an example:

A - B - D
    |
    C

When the code gets to node C, it finds no other vertices to go to: v == -1. What happens then, it clears C and goes back to B. That’s all good. But, at B we only know where we came from (the stack contains [A,B]). Now it finds the first unvisited vertex, but that’s C again!

What you need to, when you go up from C to B, then find the next vertex to visit. You need to list all adjacent in order.

int getNextAdjVertex(int currentVertex,int vertexICameFrom) {
  return the first vertex adjacent to currentVertex, bigger than vertexICameFrom
  or -1 if it does not exist
}

if (v == -1) {
  vertexList[lastVisited].wasVisited = false;
  System.out.println("Go back to: " + theStack.peek());
  //going down in the right direction:

  int backTo = theStack.peek();
  int newDestination = getNextAdjVertex(backTo,lastVisited);

  //now same as the else part, a step downward
  vertexList[newDestination].wasVisited = true;
  lastVisited = newDestination;
  System.out.println("Visited: " + newDestination);
  theStack.push(newDestination);
}

There is only one small problem, if newDestination == -1 you need to go up one more level. You’ll have to do that in a loop, going up till there is a unvisited vertex.

---

I think the problem is in getNextAdjVertex.

System.out.println("Go back to: " + theStack.peek()+","+lastVisited);

will give more useful information in finding the problem. But I think this should work:

public int getNextAdjVertex(int currentVertex, int vertexICameFrom) {
    for (int j = vertexICameFrom+1; j < nVerts; j++) {
        if (adjMat[currentVertex][j] == 1 && !vertexList[j].wasVisited) {
            return j;
        }
    }
    return -1;
}